2分探索木挿入とはなにかをALDS 1_8_Aを題材にc++で学ぶ

2分探索木の挿入に関して、ALDS 1_8_A:Binary Search Tree1を題材にして学びます。

2分探索木の挿入

今回の問題では、右の木よりも左の木の方が値が小さいという条件のもと、
2分探索木を構築していきます。
30,88,12,1,20,17,25の値を空の木に挿入し、木が構築される例を見ていきます。

2分木の根から挿入するキーが対象のノードに対し、大きいか小さいかを判定し、
対象の根が空になった時点で空となった対象の親に左または右に挿入します。

key30を挿入

            30

木が空なので、そのまま挿入します。

key88を挿入

            30

                     88

rootのキー30を対象にして、挿入位置をチェックします。
rootのキー30よりも挿入キーが大きいので、30の右側に挿入します。

key12を挿入

            30

  12               88

12はrootの30よりも小さいので、30の左に挿入します。

key1を挿入

            30

  12               88

1  

対象を30,12と移動して1を挿入します。

key20挿入

            30

  12               88

1  20

key17挿入

            30

  12               88

1  20
 
  17

key25を挿入

            30

  12               88

1  20
 
    7  25

挿入手順として、根のキーを始点として探索します。
自身のキーが根のキーよりも小さければ左の子、
大きければ右の子を次の探索の節点として変えていき、
節点が空になったら挿入します。
また、その時に挿入する位置となる親を節点を変更するごとに保持・変更しておき、挿入位置が空になった時に、
親として代入することができるようにしておきます。

2分探索木挿入のプログラム

2分探索木を動的に実装するために以下の構造体を定義します。

struct Node {
    int key;
    Node *left,*right,*parent;
};

Node *gRoot,*NIL;

続いて、挿入するプログラムを見ていきます。

void insert(int value){
    Node *y = NIL;
    // 親
    Node *x = gRoot;
    // 自身
    Node *z;
    z = (Node*)malloc(sizeof(Node));
    z->key = value;
    z->left = NIL;
    z->right = NIL;
    
    // rootから自身を挿入する場所を探す
    while(x != NIL){
        // rootから検索
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    
    z->parent = y;
    // 親に子を持たせる
    if(y == NIL){
        gRoot = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}

上記の図で説明したことをそのままプログラムにしています。
では、全体のソースです。

#include <stdio.h>
#include <iostream>
#include <cstdlib>
using namespace std;

struct Node {
    int key;
    Node *left,*right,*parent;
};

Node *gRoot,*NIL;

void insert(int value){
    Node *y = NIL;
    // 親
    Node *x = gRoot;
    // 自身
    Node *z;
    z = (Node*)malloc(sizeof(Node));
    z->key = value;
    z->left = NIL;
    z->right = NIL;
    
    // rootから自身を挿入する場所を探す
    while(x != NIL){
        // rootから検索
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    
    z->parent = y;
    // 親に子を持たせる
    if(y == NIL){
        gRoot = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}
// 先行順巡回
void preOrder(Node *u){
    if(u == NIL)return;
    printf(" %d",u->key);
    preOrder(u->left);
    preOrder(u->right);
}

// 中間順巡回
void inOrder(Node *u){
    if(u == NIL)return;
    inOrder(u->left);
    printf(" %d",u->key);
    inOrder(u->right);
}

int main(){
    int n,x;
    string com;
    
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> com;
        if(com == "insert"){
            cin >> x;
            insert(x);
        }
        else if(com == "print"){
            inOrder(gRoot);
            cout << "\n";
            preOrder(gRoot);
            cout << "\n";
        }
    }
    return 0;
}