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

ハトムギです。

アルゴリズムの基礎、二分探索木について勉強したので、今回は新しいnodeの挿入について書きます。

二分探索木とは

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

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

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

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

struct node {
      int key;
      node* parent, * left, * right;

};

二分探索木・挿入

void insert (node* u, int newkey) ;   

主な方針としては、malloc またはcalloc 関数でstruct node分の新しいnode を用意します。

node* ｚ; //z=newnode　

z = (node*)malloc(sizeof(node));

z->key = k; z->p = NULL;

z->l = NULL;

z->r = NULL;

次に、key を比較して正しい位置に持って行きます。

ここで、keyと比較できないときがあるのに気がつきます。

まだ、二分探索木に一つもnodeが無いときは新しいnodeを根としておきます。

ここで、根を指しておくためのポインタがあれば便利だと気がつきます。

node * root; // root はグローバルに宣言しておくと便利です。

if (u == NULL) {

　root = z;

　return;

}

次に、二分探索木が一つ以上のnodeを持っているときです。

新しいnodeをあるnodeの下に付け加えるので、そのあるnodeを保存しておく struct node 型のポインタを確保します。

node * y = u ; 

あるnodeとは所謂、新しいnodeの親となるnodeです。

親がわかっても左の子なのか右の子なのかわかりません。そこで、右か左かの情報を保存しておく変数を宣言しておきます。

int rorl = 0: // le =0

準備が出来たので、二分探索木の端に到達するまで、keyの比較をしていきます。

端に到達したら、新しいnodeの親と子を設定して挿入完了です。

 while (1) {

   if (u->key > z->key) {

     u = u->l; 

     rorl = 0; 

   } else {

     u = u->r; 

     rorl = 1; 

   }

   if (u == NULL)break;

   y = u;

}

if (rorl)y->r = z;

else y->l = z;

z->p = y;