[C言語]ポインタを用いて二分探索木を実装しよう[コード付]

どうもー
今回はデータ構造の一つである二分探索木を実装したいと思います！

データ構造と計算量
二分探索木のアルゴリズム
コードの実装
実行した結果
まとめ

データ構造と計算量

まずはデータ構造とはなんぞや、からいきます。
0から9までの値を持つデータの集合があるとします。
これらをコード上でどのようにまとめるか？がデータ構造です。
簡単に思いつくものとしては配列と線形リストが挙げられますね。

こんな感じですね。

ここから特定の値の取り出したい！って思ったとします。
上の例ですと3や５ならすぐ取り出せますが、逆に６を取り出したいときは配列や線形リストを最後まで走査する必要があります。
つまり要素数がnの配列や線形リストから特定の要素を探索するときは平均でn/2個の要素を走査する必要があるということです。
この時の計算量はO(n)になりますね。

対して今回扱う二分探索木では特定の要素を探索する時の計算量がO(log n)で済みます。
以下でなぜそうなるのかを解説していきます！

二分探索木のアルゴリズム

まず二分木は名前の通り二つに分岐する木構造のことです。

こんな感じで一つの親要素に対して、最大二つの子要素がついている構造のことです。このルールに従うとこんな感じの構造体が出来上がります。

毎回大体半々ぐらいに要素が分かれるとしたらこの二分木の高さ（一番上の要素から下の要素までの距離）は大体log2nになることが分かっています。

まあ確かに高さは一列に並べる配列や線形リストより小さくなるね。でも要素の数自体はnだから探索の計算量もO(n)になるんじゃないの？

もちろんこのままではO(log n)にはなりません。
そこでこの木構造にある制約を入れます。それが

親要素の値より大きい値を持つ子要素は右に、小さい値を持つ子要素は左に付ける

ということです。
どういうことかというと値として7を持つ要素の下に、値として5と9を持つ要素をつける時

このように付けなければならないという事です。
これを先ほどの例に適用すると、

こんな感じになります。どの親要素ー子要素の関係をみてもルールを守っていますね。
このルールで二分木を作成した上で一番上の要素（根要素）から特定の値を持つ要素を探索する際に、一つずつ要素の値を着目して

特定の要素の値が注目要素の値より小さければ右に、大ききれば左に

といったように走査をしていけば特定の要素を探し出すことができます。
この時の計算量は木構造の根要素から一番下までの長さに比例します。木の長さは平均でlog nになるので計算量もO(log n)になるわけですね。

コードの実装

今回の記事ではゴリゴリに構造体やポインタを用います。
もしそれらに不安な方は以下の記事もぜひ併せてお読みください。

また再帰的な処理も用いてコードを組んでいます。よければこちらの記事も参考にしてください。

構造体で二分木の要素を定義

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

int dataがその要素が持つ値、
ポインタ型の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;
}

まず関数自体の型は、先ほど定義した要素を表す構造体Nodeのポインタ型です。
引数として、現在注目している要素を指すポインタpNodeと追加する要素の値insert_dataを渡します。

if(pNode == NULL)

    if (pNode == NULL) {
       //////////////////////
    }

そして本文では最初に現在注目している要素が存在するか？を判定するif文があります。
このif文の条件(pNode == NULL)が成り立つときは

最初に要素を挿入するとき
追加する要素が挿入されるべき位置までポインタが移動したとき

です。
一つ目の最初に要素を挿入するときはそうですよね。
二分木にまだ何も要素がないのでもちろんpNodeはNULLです。

そして二つ目の追加する要素が挿入されるべき位置までポインタが移動したときというのは二分木のルールに沿って値が入るべき位置までポインタをどんどん移動していき、その要素が入るべき位置まで移動したときにその位置には要素がないはず、つまりNULLを指すはずなのでこの条件が成り立つというわけですね。

そしてif文の中です。

        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->data = insert_data;
        new_node->left = NULL;
        new_node->right = NULL;
        return new_node;

ここではmalloc関数でメモリを確保して、そこにNode型を定義して、子要素を指すポインタleft,rightをNULLにして、dataにdataを代入して、、、といった作業をしています。
まあ線形リストの時と同じですね。詳しく知りたい方はこちらの記事もぜひ読んでください。

返り値はその新しく追加した要素を指すポインタです。

if (data < pNode->data)

そして次のif文です。

if (insert_data < pNode->data) {
        ///////////////
    }

ここでは追加する要素の値が、注目している要素より小さいかを判定しています。
もし小さければその要素が挿入されるべき位置は注目要素より左側にあるはずです。
なので再帰的に

pNode->left = insert(pNode->left, insert_data);

とすることで、次はその注目要素の左の子要素を新たな注目要素として同じ作業を行います。

else if (data > root->data)

このelse if文では同様に、追加する要素の値が、注目している要素より大きいかを判定しています。

else if (insert_data > pNode->data)

もし大きければその要素が挿入されるべき位置は注目要素より右側にあるはずです。です。なのでこちらも同様に以下のような処理にします。

pNode->right = insert(pNode->right, insert_data);

return pNode;

最後に返り値として注目要素を指すポインタを返します。
ここに辿り着くには上記のif文else文を抜けてくる、つまりdata==pNode->dataの場合なので、この時のpNodeは追加された要素を指しています。

二分木の要素を探索する関数

次は二分木の中から特定の値を持つ要素を探索して、その要素へのポインタを返す関数です。

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);
    }
}

関数の型は要素を表す構造体のポインタ型。引数は先ほどと同じですね。

if (pNode == NULL || pNode->data == search_data)

まずは最初のif文から。

    if (pNode == NULL || pNode->data == search_data) {
        return pNode;
    }else {
        return search(pNode->right, search_data);
    }

ここでは要素が見つからなかった場合と要素が見つかった場合の判定を行います。

pNode==NULLが成り立つのは要素をポインタで辿っていったけれども探索している値が見つからずにNULLを指してしまった場合ですね。この時、if文の処理文のreturn pNodeではNULLを返すことになります。

pNode->data==search_dataが成り立つのはは要素をポインタで辿っていき、注目している要素の持つ値が探索している値と一致している場合ですね。この時、if文の処理文のreturn pNodeではその要素を指すポインタを返すことになります。

同じreturn pNodeでも返す値は全然違うね

if (data < pNode->data)

次は要素を探す部分ですね。

if (search_data < pNode->data) {
        return search(pNode->left, search_data);
    }

先ほどの関数と同じように注目要素と探索している要素の値の大きさを比較して、それに応じて再帰処理している感じです。

二分探索木の全ての要素を出力する関数

二分木に含まれる要素の値を出力関数を作ります。
ここに関しては後日に詳しく解説した記事を出すつもりなのでコードだけ貼っておきます。

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

main関数

次は使い方を含めてmain関数を紹介します。

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

    printf("Inorder traversal: ");
    traverse(root);
    printf("\n");

    int search_data = 7;
    Node* result = search(root, search_data);
    if (result == NULL) {
        printf("%d not found.\n", search_data);
    } else {
        printf("%d found.\n", result->data);
    }

    return 0;
}

まずは二分木の最小の要素(根要素)を定義します。

    Node* root = NULL;

そこからはinsert関数にrootと追加したい値を渡すことでどんどん二分木のデータ構造を構築してくれます。

　　 root = insert(root, 6);
    root = insert(root, 8);
    root = insert(root, 9);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 4);
    root = insert(root, 1);
    root = insert(root, 0);
    root = insert(root, 2);
    root = insert(root, 5);

そして次は探索です。

    int search_data = 7;
    Node* result = search(root, search_data);
    if (result == NULL) {
        printf("%d not found.\n", search_data);
    } else {
        printf("%d found.\n", result->data);
    }

search関数にrootと探したい値を渡し、その返り値をresultに代入しています。
もし見つからなければNULLが返ってくるのでその場合はif文の処理が発生します。
見つかった場合はelse文の処理が発生します。