LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@kuwa312(kuwa)

C言語で二分探索木を実装してみた

Last updated at Posted at 2025-05-27

はじめに

こんにちは、kuwaです。

本記事では、C言語による 二分探索木（Binary Search Tree） のサンプルコードを紹介します。

⚠️ 本記事は個人的な学習メモとして作成したものであり、内容に誤りが含まれている可能性があります。参考にされる際はご注意ください。

二分探索木（Binary Search Tree）

探索木は、挿入・検索・削除などの操作が可能なデータ構造であり、辞書や優先度付きキューなどに利用されます。中でも最も基本的なものが 二分探索木（Binary Search Tree, BST） です。

BSTは各ノード（節点）にキーを持ち、以下の 二分探索木の条件（Binary Search Tree Property） を常に満たすように構築されます：

  • 節点 x をBST上のあるノードとし、y を x の左部分木に属する節点とする。このとき、y のキー ≤ x のキーである
  • 同様に、y を x の右部分木に属する節点とする場合、x のキー ≤ y のキーである

次の図は二分探索木の例です。

           35
         /    \
       3       80
      / \     /  \
     1  14   42  86
        / \      / \
       7  21    81 99

例えば、キーが80の節点の左部分木に属する節点のキーは80以下であり、右部分木に属する節点のキーは80以上になっています。二分探索木に中間順巡回を行うと、昇順に並べられたキーの列を得ることができます。

BSTでは、データの挿入や削除を行っても、常にこの条件が全てのノードで成り立つように実装する必要があります。ノード同士はポインタで接続され、各ノードにはキーのほかに、親ノード、左の子、右の子へのポインタを持ちます。

対応する操作

BST T に対して、以下の命令を処理するC言語プログラムを作成します：

  • insert k: T にキー k を挿入する
  • find k: T にキー k が存在するかを判定する
  • delete k: キー k を持つノードを削除する
  • print: 中間順巡回（inorder）と先行順巡回（preorder）でキーを出力する

削除処理の3つのケース

キー k を持つノード z を削除する際には、以下のいずれかのケースに分類して処理します：

case1. z が子を持たない場合：z の親から z を削除する。
case2. z がちょうど1つの子を持つ場合：z の親の子を z の子に置き換え、子の親ポインタも更新する。
case3. z が2つの子を持つ場合：z の次節点（successor）　のキーを z にコピーし、そのノード y を削除する。y は高々1つの子を持つため、case1または2で削除可能。

※zの次節点（successor）とは、中間順巡回で z の次に訪れるノードのことを指します。

入出力仕様

入力形式

最初の行に命令の数 m が与えられます。続く m 行に以下のいずれかの命令が1行に1つずつ記述されます：

insert k
find k
delete k
print

出力形式

  • find k 命令ごとに、キー k が存在する場合は yes、存在しない場合は no を1行で出力
  • print 命令ごとに以下の2行を出力：
    • 中間順巡回（inorder）による出力
    • 先行順巡回（preorder）による出力

※どちらの行も、各キーの前にスペースを1つ付けて出力。

制約

  • 命令の数は最大 500,000
  • print 命令の回数は最大 10
  • −2,000,000,000 ≤ キー ≤ 2,000,000,000
  • 木の高さは最大 100
  • 同じキーが複数回挿入されることはない（重複なし）

入出力例

入力例 1

18
insert 8
insert 2
insert 3
insert 7
insert 22
insert 1
find 1
find 2
find 3
find 4
find 5
find 6
find 7
find 8
print
delete 3
delete 7
print

出力例 1

yes
yes
yes
no
no
no
yes
yes
1 2 3 7 8 22
8 2 1 3 7 22
1 2 8 22
8 2 1 22

サンプルコード

#include<stdio.h>
#include<stdlib.h>
#define NIL NULL

struct node {
    struct node *left;
    struct node *right;
    struct node *parent;
    int key;
};

typedef struct node * Node; 

Node root; //rootは根へのポインタ

Node getMinimum(Node node){ //nodeを根とする部分木の中で最小のキーを持つ接点を返す
    while (node->left != NIL) { 
        node = node->left; 
    }
    return node; 
}

Node treeSuccessor(Node node){ // nodeの次接点を返す．nodeの次接点とは，中間順巡回でnodeの次に訪問される接点
    if (node->right != NIL) { // 右の子が存在する場合
        return getMinimum(node->right); // 右の子の最小値を返す
    }

    // (以降は、このコードでは実行されることはないが、削除以外の用途でも使えるような汎用性を持たせるための実装)
    // 右の子が存在しない場合、親をたどっていき、最初に「左の子になっているような接点の親」が次接点となる
    Node parentNode = node->parent; // 親ノードを取得
    while (parentNode != NIL && node == parentNode->right) { // nodeが親の右の子である間
        node = parentNode; // nodeを親に更新
        parentNode = parentNode->parent; // 親ノードを更新
    }
    return parentNode; // 親ノードを返す（次接点）
    
}

void treeDelete(Node node) {
    Node delNode; // 削除するノード
    Node childNode; // delNodeの子

    // delNodeを設定
    if (node->left == NIL || node->right == NIL) { // nodeが葉 or 1つの子をもつ
        delNode = node;
    } else { // 2つの子をもつ
        delNode = treeSuccessor(node); // delNodeはnodeの次接点
        }

    // childNodeを設定
    if (delNode->left != NIL) { // 左の子が存在する場合
        childNode = delNode->left; // childNodeは左の子
    } else { // 左の子が存在しない場合
        childNode = delNode->right; // childNodeは右の子
    }

    if (childNode != NIL) { // childNodeが存在する場合
        childNode->parent = delNode->parent; 
    }
    if (delNode->parent == NIL) { // delNodeが根の場合
        root = childNode; // 根をchildNodeに更新
    } else if (delNode == delNode->parent->left) { // delNodeが親の左の子の場合
        delNode->parent->left = childNode; // 親の左の子をchildNodeに更新
    } else { // delNodeが親の右の子の場合
        delNode->parent->right = childNode; // 親の右の子をchildNodeに更新
    }

    if (delNode != node) { 
        node->key = delNode->key; 
    }

    free(delNode); 
}

Node find(Node node, int key) {
    while(node != NIL && key != node->key) {
        if (key < node->key) {
            node = node->left; // 左を探索
        } else {
            node = node->right; // 右を探索
        }
    }
    return node; // もし，keyが存在しないときは，NILを返す
}

void insert(int key) {
    Node parentNode = NIL; //挿入位置の親
    Node currentNode = root; //探索中の現在のノード
    Node newNode; // 挿入する新しいノード

    newNode = (Node)malloc(sizeof(struct node)); // 新しいノードのメモリを確保
    newNode->key = key; 
    newNode->left = NIL;// 新しいノードの左の子はNIL
    newNode->right = NIL;

    while(currentNode != NIL) { //currentNodeを挿入位置まで移動
        parentNode = currentNode;
        if (newNode->key < currentNode->key) { 
            currentNode = currentNode->left;
        } else {
            currentNode = currentNode->right;
        }
    }

    newNode->parent = parentNode; // 親ノードを設定
    if (parentNode == NIL) { // 親が存在しないとき，つまり木が空のとき
        root = newNode; // 新しいノードを根に設定
    } else if (newNode->key < parentNode->key) { // 左の子として挿入
        parentNode->left = newNode;
    } else { // 右の子として挿入
        parentNode->right = newNode;
    }
}

// 中間順巡回でprint
void printInorder(Node node) {
    if (node == NIL) return; // 空のノードのとき，何もしない
    // 左の子（再帰）→自分→右の子（再帰）
    printInorder(node->left); 
    printf(" %d", node->key);
    printInorder(node->right);
}

// 先行順巡回でprint
void printPreorder(Node node) {
    if (node == NIL) return; // 空のノードのとき，何もしない
    // 自分→左の子（再帰）→右の子（再帰）
    printf(" %d", node->key);
    printPreorder(node->left);
    printPreorder(node->right);
}   

int main (void) {
    int i;
    int n; // ノード数
    char cmd[10];
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
        scanf("%s", cmd);
        if (cmd[0] == 'i') { //1文字目がi，つまりinsert
            int key;
            scanf("%d", &key);
            insert(key); 
        } else if (cmd[0] == 'p') { // 1文字目がp，つまりprint
            printInorder(root); // 中間順巡回
            printf("\n");
            printPreorder(root); // 先行順巡回
            printf("\n");
        } else if (cmd[0] == 'f') { // 1文字目がf，つまりfind
            int key;
            scanf("%d", &key);
            if (find(root, key) != NIL) {
                printf("yes\n");
            } else {
                printf("no\n");
            }
        } else if (cmd[0] == 'd') { // 1文字目がd，つまりdelete
            int key;
            scanf("%d", &key);
            Node nodeToDelete = find(root, key); // 削除するノードを探す
            if (nodeToDelete != NIL) {
                treeDelete(nodeToDelete); 
            } else {
                printf("no\n"); // ノードが見つからない場合
            }
        }                                               
    }
    return 0;
}

コメント祭りになってしまいました😅

参考文献

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. The MIT Press.

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?