[C言語]二分探索木から要素を削除する関数の実装[コード付]

どうもー
今回も前回までの続きで二分探索木を扱っていきます！
前回までで要素の追加、探索、走査が完了しました。ぜひ以下の記事を読んでください↓

二分探索木から要素を削除する際の問題
二分探索木から要素を削除するアルゴリズム
コードの実装
実際に使ってみた
まとめ
全体のコード

二分探索木から要素を削除する際の問題

二分探索木から要素を削除するとはどういうことか、から始めていきましょう。
といっても名前の通り、二分探索木のデータ構造の中の要素を削除する事です。
配列や線形リストでも要素を削除することは珍しい事ではないですよね。

こんな感じの親要素の値に対して小さい値を持つ子要素を左に、大きい子要素を右につける二分探索木から

1の値を持つ要素を削除して繋ぎかえると、

こんな感じになります。線形リストの時にやったようなポインタの繋ぎかえを行えばおk！ですね

では2の値を持つ要素を削除する場合を考えてみましょう、先ほどと同様に、、と思いきや、

あれ、、どっちの要素を繋げればいいんだろ？

こんな感じで子要素を２つ持つ親要素を削除するとどっちに繋げれば良いかわからなくなります。

適当につけてしまうとデータの順序が保存されませんし、小さい値を持つ子要素を左に、大きい子要素を右につけるというルールを破ってしまう可能性がありますね。

二分探索木は要素を追加する時に制約をつける事で探索の計算量を減らしていましたが、削除の時も同様で単純に要素を削除して繋ぎかえるだけだと二分探索木の構造が保てないんです。

二分探索木から要素を削除するアルゴリズム

て事で上の問題を解決するアルゴリズムを解説します。
いきなり答えを言うと、

削除する要素を、その右部分木に含まれる最小の値を持つ要素で置き換える

ことで上記の問題が解決できます。
先ほどの例で言うと、

削除する要素の右部分木の3の値を持つ要素が最小の要素です。
それを削除する要素と置き換えると、、

こんな感じ。
2の値を持つ要素が居た位置に3の値を持つ子要素が繰り上がっています。

この時小さい値を持つ子要素を左に、大きい子要素を右につけるというルールは守られていますね。
なんでこのような操作で二分探索木の構造を保てるかの説明はこの記事では解説しません、、（気になる方はぜひ調べてください）

今回はこのアルゴリズムを組み込んで削除を行う関数を作成していきます！

コードの実装

先ほども紹介しましたが今回の記事では前回までに作成した二分探索木のコードを用います。
この記事内では特に詳しく解説しないので、もしそこが気になる方がいれば以下の記事を参考にしてください↓

またポインタを多用するので、不安がある方はこちらの記事もどうぞ！

二分探索木の構造体

typedef struct node {
    int data;
    struct node* left;//親より小さい要素を指す
    struct node* right;//親より大きい要素を指す
} Node;

ざっくり説明すると構造体で二分探索木の各要素を表しています。
その要素より小さい値を持つ要素を指すleftと大きい値を持つrightをポインタ型で持っています。

二分探索木に要素を追加する関数

Node* insert(Node* pNode, int insert_data) {
    if (pNode == NULL) {
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->data = insert_data;
        new_node->left = NULL;
        new_node->right = NULL;
        return new_node;
    }
    if (insert_data < pNode->data) {
        pNode->left = insert(pNode->left, insert_data);
    } else if (insert_data > pNode->data) {
        pNode->right = insert(pNode->right, insert_data);
    }
    return pNode;
}

こちらは要素を追加する関数です。
引数のpNodeに追加する二分探索木の根要素へのポインタを、insert_dataに追加したい要素の値を入れることでその要素があるべき位置に挿入されます。

二分探索木の全要素を通りがけ順で表示する関数

void in_order(Node* root) {
    if (root == NULL) {
        return;
    }
    in_order(root->left);
    printf("%d", root->data);
    in_order(root->right);
}

部分木の中で最小の値を持つ要素を求める関数

先ほどのアルゴリズムの説明でもあったように、削除する要素の右側の部分木の中の最小の値を持つ要素を探索する必要があります。ここではその機能だけを関数化したもののコードを解説していきます。

struct node* minValueNode(struct node* node) {
    struct node* current = node;
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

関数の型は要素を表す構造体のポインタ型です。これは最小の値を持つ要素を指すポインタを返すためですね。
引数も同様に要素を表す構造体のポインタ型です。これは削除する要素を指すポインタを受け取るためですね。

本文ではまず現在注目している要素を指すためのポインタを定義して、引数で受け取ったポインタを代入します。

ここから最小の値を探していきます。
流れとしてはwhile文を用いてどんどんポインタを移していき最小の値でループを止めるといった感じです。

    while (current && current->left != NULL)
        current = current->left;

このwhileの条件は(current && current->left != NULL)です。
つまり現在指している要素が存在かつその要素に左側の子要素が存在していれば継続ってわけですね。

一つ目の条件はもちろんですね。

二つ目の条件ですが、二分探索木の小さい値を持つ子要素を左にというルールを利用しています。つまりある要素より小さい要素は左側、つまり構造体のメンバであるleftが指しているはずです。
そのleftが指す要素が存在しない時、その部分木に現在注目している要素より小さい値を持つ要素が存在しないって事になります。

もし存在していれば、current = current->left;として注目要素をずらしてまたループしていきます。

このwhileループを抜けた時にポインタが指している要素が最小の値を持つ要素になるのでそれをreturnで返して処理を終えます。

二分探索木から要素を削除する関数

ここからが二分探索木から要素を削除する機能を持つ関数です。

struct node* deleteNode(struct node* root, int key) {
    if (root == NULL)
        return root;
    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        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->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

関数の型は要素を表す構造体のポインタ型です。
一つ目の引数は同様に要素を表す構造体のポインタ型rootです。これは現在注目している要素を指すポインタを受け取ります。
二つ目の引数のint型keyは削除する要素の値を受け取ります。

if (root == NULL)

最初のif文では現在指している要素が存在するかを判定します。

    if (root == NULL)
        return root;

このif文の条件root == NULLが成り立つ時は削除する値を持つ要素が、その二分木構造の中に存在しなかった時です。なのでreturnでそのままポインタを返します。
この関数は再帰的の処理を行うので、一つ前に呼び出した関数に戻る感じですね。

if (key < root->data) else if (key > root->data)

次は削除する値を持つ要素までポインタを進める部分です。

if (key < root->data)
        root->left = deleteNode(root->left, key);
else if (key > root->data)
        root->right = deleteNode(root->right, key);

ここは前回まででのお馴染みの操作ですね。
小さい値を持つ子要素を左に、大きい子要素を右につけるというルールを利用して再帰的にその値までポインタを進めていきます。

そして以下からは削除する値が見つかった場合、つまりelse文のなかです。

if (root->left == NULL)

削除する値を持つ要素が見つかったとして、その要素がどのように子要素を持っているか別に処理を変えていきます。
まず右側にしか子要素を持たない場合ですね。

   else{

        if (root->left == NULL) {
            struct node* temp = root->right;
            free(root);//メモリの開放
            return temp;
        }
        //////////////////
        //////////////////
    }

if文の中の処理は
その要素が唯一持っている右の子要素root->rightをtempに代入し、そのままそれを返します

この処理によって今呼び出せれている関数の処理が終わり一つ前の関数に処理が移ります。
一つ前の関数では削除する位置までポインタを進めている段階、

if (key < root->data)
        root->left = deleteNode(root->left, key);
else if (key > root->data)
        root->right = deleteNode(root->right, key);

この処理が行われているはずです。
つまり削除した要素の親要素が指すポインタに、削除した要素が唯一持っている子要素へのポインタが代入されるってわけですね。

これにより削除した要素は二分探索木の構造の中から排除されます。

else if (root->right == NULL)

次は左側にしか子要素を持たない場合ですね。

   else{
        //////////////////
        else if (root->right == NULL) {
            struct node* temp = root->left;
            free(root);
            return temp;
        }
        //////////////////
    }

こちらも先ほどと同様の処理で削除する要素を二分探索木の構造の中から排除しています。

子要素を二つ持つ場合

最後は子要素を二つ持つ場合の処理です。

   else{
        //////////////////
        //////////////////
        struct node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }

一文目ではまず先ほど作成した右部分木内で最小の値を持つ要素を求める関数を用いて、その要素へのポインタをtempに代入します。

二文目では削除される要素の値をtempの値で上書きしています。

三文目で上書きした要素の右部分木からtempの値を削除します。

これにより二分探索木の構造を保つ削除方法、

削除する要素を、その右部分木に含まれる最小の値を持つ要素で置き換える

を実現できました。
要約すると

削除される要素を二分探索木の構造から排除して繋ぎかえるのではなく、
削除される要素を「その右部分木に含まれる最小の値を持つ要素」の値で上書きして、「その右部分木に含まれる最小の値を持つ要素」を削除関数を用いて排除する

って感じですかね。
子要素が1つの時の削除と全然違う方法で対応していますね。

return root

最後にreturnでrootを返します。

    return root;

再帰的に戻っていき、最終的に関数全体としては要素を削除した二分木の根要素へのポインタが返ります。

実際に使ってみた

このようなmain関数で使ってみた結果

int main(void){
    Node* root = NULL;
    root = insert(root, 7);
    root = insert(root, 2);
    root = insert(root, 1);
    root = insert(root, 0);
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 4);
    root = insert(root, 6);
    root = insert(root, 8);
    root = insert(root, 9);

    printf("\npre＿order: ");
    in_order(root);
    root = deleteNode(root, 2);
    printf("\npre＿order: ");
    in_order(root);
    printf("\n");

    return 0;
}

こんな感じで削除できていますね。

まとめ

いやー思ったよりがっつりした記事になってしまいました。
再帰的な処理がゴリゴリですし、二分探索木の構造を保つ削除の処理の部分がややこしいですが頑張って実装してください。

ではまた

全体のコード

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} Node;

Node* insert(Node* pNode, int insert_data) {
    if (pNode == NULL) {
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->data = insert_data;
        new_node->left = NULL;
        new_node->right = NULL;
        return new_node;
    }
    if (insert_data < pNode->data) {
        pNode->left = insert(pNode->left, insert_data);
    } else if (insert_data > pNode->data) {
        pNode->right = insert(pNode->right, insert_data);
    }
    return pNode;
}

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->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        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->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

Node* search(Node* pNode, int search_data) {
    if (pNode == NULL || pNode->data == search_data) {
        return pNode;
    }
    if (search_data < pNode->data) {
        return search(pNode->left, search_data);
    } else {
        return search(pNode->right, search_data);
    }
}

void in_order(Node* root) {
    if (root == NULL) {
        return;
    }
    in_order(root->left);
    printf("%d", root->data);
    in_order(root->right);
}

int main(void){
    Node* root = NULL;
    root = insert(root, 7);
    root = insert(root, 2);
    root = insert(root, 1);
    root = insert(root, 0);
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 4);
    root = insert(root, 6);
    root = insert(root, 8);
    root = insert(root, 9);

    printf("\npre＿order: ");
    in_order(root);
    root = deleteNode(root, 2);
    printf("\npre＿order: ");
    in_order(root);
    printf("\n");

    return 0;
}