赤黒木

二分探索木（BST: Binary Search Tree）は、setやmapなどの連想コンテナを実装するために使用されるデータ構造です。 しかし、BSTは挿入順序によってはツリーが不均衡になることがあります。要素を昇順または降順で挿入すると、 二分木は通常の双方向リンクリストに変わってしまい、挿入や探索にかかる時間が$O(n)$となり、 $O(\log(n))$に比べて効率が悪くなります。そこでBSTのバランスを常に保つために、要素の取り扱いにいくつかのルールを設けた 赤黒木（RBT: Red-Black Tree） が生まれました。

• ノードは赤か黒のいずれかである。
• ルートノードおよびリーフノードは黒である。
• 赤いノードの子は必ず黒である。
• ある同じレベルのノードからリーフノードまでのすべての経路は、同じ数の黒いノードを含まなければならない。

上記のルールに従うことで、赤黒木はバランスを保つことができます。（ここでいうリーフノードは、黒とみなされるnullノードです。） 色のプロパティ（0や1で表現される）を導入するため、追加の情報を保存する必要がありますが、これらのルールにより、 最長な経路が最短な経路の2倍以下となり、比較的バランスの取れたBSTとなります。以下は、赤黒木におけるノードの定義方法です。

// Enum to represent the color of the nodes in the Red-Black Tree
enum Color {RED, BLACK};
 
template <typename T>
class Node {
public:
    T data;
    Color color;
    Node<T>* left;
    Node<T>* right;
    Node<T>* parent;
 
    Node(T data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

回転

三つの主要な操作である検索、挿入、削除のうち、挿入と削除の操作では赤黒木のルールが破られる可能性があります。 これらの違反を防ぐために、挿入や削除後に木を再配置するための回転操作が使用されます。

• 左回転では、あるノードをその右の子ノードの左の子にし、右の子ノードの左の子をそのノードの右の子にします。
• 右回転では、あるノードをその左の子ノードの右の子にし、左の子ノードの右の子をそのノードの左の子にします。

void leftRotate(Node<T>* x) {
    Node<T>* y = x->right;
    // make left child of the right child be the right child of x
    x->right = y->left;
    if (y->left != nullptr) {
        y->left->parent = x; 
    }
 
    // Take care of parent pointer of right child
    y->parent = x->parent;
 
    // Take care of x's parent
    if (x->parent == nullptr) {
        root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y; 
    } else {
        x->parent->right = y;
    }
 
    // make x the left child of the right child
    y->left = x;
    x->parent = y;
};

上のコードは左回転の実装です。見ての通りポインタのいくつかの変更だけで済むため、時間計算量は$O(1)$です。 回転操作は、ノードを再配置しつつ、BSTのプロパティを維持することができ、違反を修正する際に便利です。

挿入

赤黒木にノードを挿入する際、最初にノードを赤くした後、二つ目と三つ目のルール違反を修正します。 これらは色の変更や回転で比較的簡単に修正できます。違反を修正するために、挿入時に起こりうるシナリオを考慮する必要があります。 以下の図に示されているように、4つのシナリオが考えられます。

• ケース1: 挿入したノードがルートの場合、単にそのノードを黒に変更します。
• ケース2: 挿入したノードの親が赤の場合、親と祖父ノード、および叔父ノードを反対の色に変更します。これにより、赤と黒のノードが交互になり、三つ目のルールに従います。
• ケース3: 挿入したノードが親の左/右の子で、親が祖父の左/右の子であり、一直線を形成している場合、挿入ノードの方向とは逆に祖父ノードを回転させ、親と祖父の色を交換します。
• ケース4: 挿入したノードが親の左/右の子で、親が祖父の右/左の子であり、三角形を形成している場合、まず親を挿入ノードの方向とは逆に回転させてケース3に変え、ケース3の修正を適用します。

以下は、赤黒木の挿入操作の実装です。

int insert(T data) {
    Node<T>* node = new Node<T>(data);
    Node<T>* y = nullptr;  // Variable to keep track of the parent
    Node<T>* x = root;
    // BST insertion
    while (x != nullptr) {
        y = x;  // Keep track of the parent
        if (node->data < x->data) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    node->parent = y;
 
    if (y == nullptr) {
        root = node; // Case 1
        return 1;
    } else if (node->data < y->data) {
        y->left = node;
    } else {
        y->right = node;
    }
 
    // Step 3: Fix violations
    fixInsert(node);
    return 1;
};
 
void fixInsert(Node<T>* k) {
    while (k->parent != nullptr && k->parent->color == RED) {
        Node<T>* grandparent = k->parent->parent;
        if (k->parent == grandparent->left) {
            Node<T>* uncle = grandparent->right;
 
            // Case 2: Uncle is red (Recoloring)
            if (uncle != nullptr && uncle->color == RED) {
                k->parent->color = BLACK;      // Recolor parent
                uncle->color = BLACK;          // Recolor uncle
                grandparent->color = RED;      // Recolor grandparent
                k = grandparent;               // Move up to grandparent
            } else {
                // Case 4
                if (k == k->parent->right) {
                    k = k->parent;
                    leftRotate(k);
                }
                // Case 3
                k->parent->color = BLACK;
                grandparent->color = RED;
                rightRotate(grandparent);
            }
        } else {
            // Symmetric to the above, k's parent is the right child
            Node<T>* uncle = grandparent->left;
 
            // Case 2: Uncle is red (Recoloring)
            if (uncle != nullptr && uncle->color == RED) {
                k->parent->color = BLACK;      // Recolor parent
                uncle->color = BLACK;          // Recolor uncle
                grandparent->color = RED;      // Recolor grandparent
                k = grandparent;               // Move up to grandparent
            } else {
                // Case 4
                if (k == k->parent->left) {
                    k = k->parent;
                    rightRotate(k);
                }
                // Case 3
                k->parent->color = BLACK;
                grandparent->color = RED;
                leftRotate(grandparent);
            }
        }
    }
    root->color = BLACK;
};

要素を木に挿入する際、木全体が有効な赤黒木になるまで、違反を修正する必要があります。 ノードを最下部に挿入するにはツリーの探索が必要であり、それには$O(\log (n))$の時間がかかります。 その後、ノードを赤に設定する操作は$O(1)$です。次に、違反を修正するために$O(1)$の色の変更や回転を行い、 下から上に向かって修正します ($O(log(n))$)。その結果、挿入の全体の時間計算量は$O(\log (n))$となり、 BSTの平均時間計算量と同じです。

削除

削除のプロセスは非常に複雑で、いくつかのステップとシナリオに対処する必要があります。 このプロセスを理解するために、3つのステップに分けて説明します：置換、削除、そして削除修正です。

ステップ1. 置換

RBTからノードを削除する際、まず削除されるノードをどのノードで置き換えるかを決定する必要があります。 ここでは3つのシナリオを考える必要があります。1つ目のケースは、削除されるノードに2つのNIL子ノードがある場合で、 どちらかのNILノード（デフォルトでは右側のNIL子）で置き換えます。2つ目のケースは、 削除されるノードに1つのNIL子ノードと1つの非NIL子ノードがある場合で、この場合、非NIL子ノードで置き換えます。 3つ目のケースは、削除されるノードに2つの非NIL子ノードがある場合で、右部分木の最も左にあるノードで置き換えます。 これは、削除されるノードに最も近い値を持っている可能性が高いためです。

最初の2つのケースでは、RBTのルールにより、置換されるノードにはNILの子があるとわかっています。 したがって、ノードを置き換える際に、そのノードの子を追跡する必要はありません。しかし、3番目のケースでは、 右側に非NIL子（右部分木の最も左のノードを選ぶため左側はNILの子であることがわかっています）がある可能性があるため、 これを適切な場所に後で接続する必要があります。そのため、最初の2つのケースでは置換ノードに$x$ポインタを割り当てますが、 3番目のケースでは置換ノードの右の子に割り当て、適切な場所に接続します。

ステップ2. 削除

置換ノードが決まったら、次に実際にノードを削除する操作に進みます。削除は単に、削除されるノードの子ポインタを置換ノードに変更し、 置換ノードの親ポインタを削除されるノードの親に変更し、削除されたノードが占めていたメモリを解放することです。 ステップ1の3番目のケースでは、$x$のポインタを変更して置換ノードがいた場所に接続する必要があるかもしれません。 この時点で、RBTのルール違反がほとんど発生しないケースと、重大な修正が必要なケースがあります。

削除されるノードが赤で、置換ノードが赤またはNILの場合、削除操作はこれで完了です。しかし削除されるノードが赤で、 置換ノードが黒で非NILの場合、置換ノードを赤に再着色する必要があります。これにより第3ルールの違反を防ぎますが、 第4ルールの違反が残る可能性があります。そのため、この2番目のケースでは、ステップ3に進む必要があります。

削除されるノードが黒で、置換ノードが赤の場合、置換ノードを黒に再着色するだけで削除は完了です。 削除されるノードと置換ノードが両方黒で、置換後に$x$がツリーのルートになる場合は、 ツリーには元々1つのルートノードしかなかったことになります。従ってこのケースでも、削除はこれで完了です。 一方で、削除されるノードと置換ノードが両方黒で、$x$がルートにならない場合、ルールに違反する可能性があるため、 ステップ3に進む必要があります。

ステップ3. 削除修正

ステップ2の後、削除されるノードが赤で置換ノードが黒で非NILの場合、または削除されるノードと置換ノードが両方黒で$x$がルートにならない場合にステップ3を行います。 どちらのケースでも、第4ルールに違反する可能性があるため、これを修正する必要があります。このようなケースでは、違反を修正するために考慮すべき5つのシナリオがあります。

1つ目のケースは、$x$が赤であり、$x$を含むパスの黒ノードの数が他のパスより1つ少ない場合です。この場合、$x$を黒に再着色することで修正できます。 2つ目以降のケースは、操作がより複雑であり、$x$の兄弟ノード$w$が関与します。違反の修正がすぐに行われない可能性があるため、 正しいケースを特定し、それに対応する操作を繰り返す必要があります。

• 2つ目のケース：$x$が黒で$w$が赤の場合。この場合、$w$を黒に再着色し、$x$の親を赤に再着色し、親を$x$の方向に回転させ、再び$w$を$x$の兄弟として設定します。
• 3つ目のケース：$x$、$w$、および$w$の子がすべて黒の場合。この場合、$w$を赤に再着色し、$x$をその親に設定します。$x$を親に設定した後、新しい$x$が赤であるか、黒でルートであるかを確認する必要があります。$x$が赤であれば、再着色して黒にするだけでよく、ルートであればそれ以上の操作は不要です。
• 4つ目のケース：$x$と$w$が黒で、$w$の子のうち$x$と同じ側にある子が赤、もう一方の子が黒の場合。この場合、$w$の$x$と同じ側の子を黒に再着色し、$w$を赤に再着色し、$w$を$x$の反対方向に回転させ、再び$w$を$x$の兄弟として設定します。
• 5つ目のケース：$x$と$w$が黒で、$w$の子のうち$x$の反対側にある子が赤の場合。この場合、$x$を親と同じ色に再着色し、$x$の親を黒に再着色し、$w$の子を黒に再着色して$x$の親を$x$の方向に回転させます。この操作によって、最終的に有効なRBTになります。

これらのステップからわかるように、ステップ1では置換ノードを見つけるために木を探索する必要があり、 これは$O(\log (n))$です。ステップ2では、条件をチェックし、必要に応じて再着色を行うだけで、$O(1)$です。 ステップ3では、再着色と回転のプロセスが最大で$\log (n)$回繰り返される可能性があり、これも$O(\log (n))$です。 したがって、全体の時間計算量は$O(\log (n))$であり、これはBSTの平均時間計算量と同じです。

注意：削除ステップには多くのシナリオがあり、一部の操作は複雑であるため、これらのステップがどのようにして違反を修正するのか理解するのが難しい場合があります。 私自身もアルゴリズムの一部についてはまだ完全に理解していませんが、内容を何度も読み、具体的なRBTの例で削除を視覚化することである程度理解できました。 あなたも同じように、プロセスを繰り返し学び、何度も練習することをお勧めします。また、自分でRBTクラスに削除機能を実装してみる挑戦をしてみてください！

結論

ここまで見てきたように、いくつかのルールを導入し、操作を修正する"だけ"で、RBTは常にバランスの取れたBSTを保証し、 挿入および削除の最悪の時間計算量を通常のBSTの平均時間計算量と同等にすることができます。RBTは、各ノードに追加のポインタと整数が必要なため、 より多くのスペースを消費し、挿入および削除の操作が複雑になるというトレードオフがあるものの、 現代のシステムでは十分なスペースがあるため、これは許容範囲内です。次の記事では、他のツリー構造を探索し、 連想コンテナを実装するための代替データ構造を検討します。

クイズ

この記事では、学習した内容を確認するためのクイズを設けます。記事のメイン部分を読んだ後に、ぜひ自分で問題を解いてみることを強くお勧めします。各問題をクリックすると答えが表示されます。

リソース

• Chang, A. 2022. Red-black tree deletion: steps + 10 examples. YouTube.
• Sambol, M. n.d. Red-Black Trees // Michael Sambol. YouTube.