【C++】二分探索木の実装

概要

二分探索木の説明と、節点の挿入、探索、削除等の基本的な操作の実装を紹介します。
もし、間違い等ありましたらコメントで教えて頂けると助かりますm._.m

二分探索木とは?

種類

木構造 ⊇ 探索木 ⊇ 二分探索木

制約

任意の節点は最大2つまでの子を持ち、左の部分技の値 < ノードの値 < 右の部分技の値　を満たす

すなわち、以下の画像にある赤い節点は制約を満たしていないことになります。

メリット

中間巡回順で探索すると昇順で値を得られる。

操作

節点の構造体

節点(Node)を以下の構造体として勧めていきます。

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

int keyは、この節点の持っている値
Node *parentは、この節点を子として持つ節点のポインタ(字の如く親)
Node *left, *rightは、この節点が子として持つ節点のポインタ

また、ヌルポインタを区別するため、グローバル変数にNILを定義します。
これは、根の親など存在しない節点へのポインタのために使用します。

挿入

節点の挿入は、木の根から末端まで、挿入したい節点の値との大小関係の比較を行うことで可能。
キーkを持つ節点を挿入する場合、

void insert(int k) {
    Node *x = root;     // xは比較する対象となる節点、初期値は根であり、kとの比較によってx->left や x->rightが新たに代入される
    Node *y = NIL;      // 新たに挿入される節点の親のポインタの保存目的
    Node *z = new Node; // 新たに挿入される節点

    // 節点の初期化
    z->val = k;
    z->left = NIL;
    z->right = NIL;

    while( x != NIL ) {
        y = x;
        if (x->val < z->val) {
            x = x->right; // 挿入する節点の値が、xの節点の値より大きい場合、xの右側へと進む
        } else {
            x = x->left;  // 挿入する節点の値が、xの節点の値より小さい場合、xの左側へと進む
        }
    }

    z->parent = y;
    if (y != NIL) { // y != NIL => zは親を持つ
        if (y->val < z->val) {
            y->right = z;
        } else {
            y->left = z;
        }
    } else {        // y == NIL => zは親を持たない => zは根である
        root = z;
    }
}

探索

特定の値kを持つ節点の探索は、根から探索を始め、大小関係からどちらの子へと探索を進めるかを決定します。
終了条件は、最下層まで到達した場合 || kを持つ節点を見つけた場合です。

Node* find(Node* u, int k) {
    while(u != NIL && k != u->val) {
        if ( k < u->val ) u = u->left;
        else u = u->right;
    }
    return u;
}

ここでは、見つからなかった場合は、NILへのポインタが返ってくる設計になっています。

削除

特定の節点を削除する場合、以下の3つのパターンに分けて考えます。

1. 削除対象の節点に子がない場合
2. 削除対象の節点に子が一つある場合
3. 削除対象の節点に子が2つある場合

手順

1. 単純にその節点の削除で完了します。
2. 削除対象の節点を、その子で置き換える完了します。
3. 削除対象の節点を、中間順巡回で次に訪問される節点で置き換えることで完了します。

void del(Node *z) {
    Node* y; // 
    Node* x;

    if (z->left == NIL || z->right == NIL) y = z;
    else y = treeSuccessor(z);

    if (y->left != NIL) x = y->left;
    else x = y->right;

    if (x != NIL) x->parent = y->parent;

    if (y->parent == NIL) {
        root = x;
    } else {
        if (y == y->parent->left) y->parent->left = x;
        else y->parent->right = x;
    }

    if (y != z) z->val = y->val;

    delete y;
}