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

# はじめに

こんにちは、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
```


---

## サンプルコード

```c
#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.