二分探索木（BST）の削除操作をC++で徹底解説｜3つの場合分けと実装例

二分探索木（BST）とは

二分探索木（Binary Search Tree：BST）は、以下のルールに従う特殊な木構造のデータ構造です。

• 左の子ノードの値は、常に親ノードの値より小さい
• 右の子ノードの値は、常に親ノードの値より大きい
• すべてのノードが個別に二分探索木の条件を満たす

二分探索木（BST）の例：

二分探索木は、検索や最小値・最大値の探索といった操作の計算量を削減するために用いられるデータ構造です。木の構造そのものが値の大小関係を保持しているため、効率的な探索が可能になります。

二分探索木（BST）の削除操作

削除操作とは、指定したノードを木から取り除くことです。ノードを削除する場合、削除対象のノードが持つ子の数によって、次の3つの場合に分けて考えます。

1. 葉（リーフ）ノードの削除

二分探索木における最も簡単な削除は、葉ノード（子を持たないノード）の削除です。葉ノードを削除する場合、影響を受けるのはその葉ノードのみで、木の他の部分を修正する必要はありません。

例：

葉ノードの「7」を削除すると、次のようになります。

2. 子を1つ持つノードの削除

子を1つだけ持つノードを削除する場合は、削除対象のノードをその子ノードで置き換えてから削除します。これにより、木の二分探索木としての性質が保たれます。

例：

BSTから「2」を削除します。

3. 子を2つ持つノードの削除

削除対象のノードが2つの子ノードを持つ場合は、木の中間順走査（inorder traversal）を利用します。削除する要素を取り除き、その位置に中間順での隣接ノード（右部分木の最小値ノード、または左部分木の最大値ノード）を配置し、残りの部分を再構成します。

例：

BSTから「5」を削除すると、次の木が得られます。

実装例（C/C++）

以下は、二分探索木の挿入・走査・削除を実装したサンプルコードです。

#include<stdio.h>
#include<stdlib.h>
struct node{
    int key;
    struct node *left, *right;
};
struct node *newNode(int item){
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
void inordertraversal(struct node *root){
    if (root != NULL){
        inordertraversal(root->left);
        printf("%d ", root->key);
        inordertraversal(root->right);
    }
}
struct node* insert(struct node* node, int key){
    if (node == NULL) return newNode(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);
    return node;
}
struct node * minValueNode(struct node* node){
    struct node* current = node;
    while (current && current->left != NULL)
        current = current->left;
    return current;
}
struct node* deleteNode(struct node* root, int key){
    if (root == NULL) return root;
    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else{
        if (root->left == NULL){
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL){
            struct node *temp = root->left;
            free(root);
            return temp;
        }
        struct node* temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}
int main(){
    struct node *root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);
    printf("Inorder traversal of the given tree \n");
    inordertraversal(root);
    printf("\nDelete 20\n");
    root = deleteNode(root, 20);
    printf("Inorder traversal of the modified tree \n");
    inordertraversal(root);
    printf("\nDelete 30\n");
    root = deleteNode(root, 30);
    printf("Inorder traversal of the modified tree \n");
    inordertraversal(root);
    printf("\nDelete 50\n");
    root = deleteNode(root, 50);
    printf("Inorder traversal of the modified tree \n");
    inordertraversal(root);
    return 0;
}

実行結果

Inorder traversal of the given tree
20 30 40 50 60 70 80
Delete 20
Inorder traversal of the modified tree
30 40 50 60 70 80
Delete 30
Inorder traversal of the modified tree
40 50 60 70 80
Delete 50
Inorder traversal of the modified tree
40 60 70 80

コードのポイント解説

• deleteNode関数： 削除対象のキーを再帰的に探索し、見つかったノードの子の数に応じて処理を分岐させます。
• 子が0個または1個の場合： 左の子がNULLなら右の子を、右の子がNULLなら左の子をその位置に返すことで、ノードを置き換えます。
• 子が2個の場合： minValueNode関数で右部分木の最小値ノード（中間順走査における次のノード）を取得し、その値を削除対象ノードにコピーした後、右部分木からその最小値ノードを再帰的に削除します。
• 計算量： バランスの取れた二分探索木では、削除操作の時間計算量はO(log n)となります。