二分探索木/Binary-Search-Tree 探索/Search c++

こんにちは、ハトムギです。

今回も前回に引き続き、二分探索木について書きます。

二分探索木とは

探索木の中でももっとも基本的なものが、二分探索木です

簡単に説明するとその名の通り、根から枝が二つに分かれ、また各節点から二つに分かれを繰り返します。

今回は、あるnodeのkeyより値の小さいnodeは左側に、大きいnodeは右側にくるように実装しました。

各nodeは、key, 親、左の子、右の子をメンバにもつ構造体により実装できます。

struct node {

      int key;

      node* parent, * left, * right;

};

二分探索木・探索

bool find ( node *u , int k) 

主な方針は、kの値と同じkeyを持つnodeを発見するまで、または二分探索木の葉（子を持たないnode）に到達するまでkey とk を比較して根から順に調べていきます。

今回の二分探索木は、左の子のkeyは親のkey より小さい右の子のkeyは親のkeyより大きい仕様になっているのでどちらの子に分岐すれば良いかもkeyとｋを比較することで考えられます。

bool find(int k, node* u) {

    while (u != NULL && k != u->key) {

        if (k < u->key)u = u->l;

        else u = u->r;

    }

    if (u == NULL)return false;

    else return true;

}

関数を呼び出す時は、node型ポインタu に根を指しているポインタ（root）を渡します。