Day 125-Q5 | 赤黒木（Red-Black Tree）への挿入と回転回数

問題

空の赤黒木に、$N$ 個の相異なる整数を与えられた順に挿入していく。挿入のたびに CLRS流の RB-INSERT-FIXUP アルゴリズムを実行し、木の性質（① 各ノードは赤か黒 ② 根は黒 ③ 葉(NIL)は黒 ④ 赤の子は必ず黒 ⑤ 任意ノードから子孫NILまでの黒ノード数が一致）を常に維持する。

$N$ 回の挿入を通して行われた回転（左回転・右回転）の総回数を出力せよ。

入力形式

N
a_1 a_2 ... a_N

制約

$1 \le N \le 200000$

$a_1,\dots,a_N$ は相異なる整数

$-10^9 \le a_i \le 10^9$

入出力例

入力例1

3
10 20 30

出力例1

30挿入時、20(赤)と30(赤)が衝突。叔父(10の左)はNIL(黒)、30は20の右の子で20も10の右の子(一直線)なのでCase3のみ→左回転1回

入力例2

3
30 10 20

出力例2

20挿入時、10(赤)と20(赤)が衝突。10は30の左の子だが20は10の右の子(ジグザグ)なのでCase2で右回転1回→Case3で左回転1回、計2回

概念図

ヒント（段階的開示）

ヒント1（方向性）

二分探索木としての挿入位置を決めて赤ノードとして挿入するところまでは通常のBSTと同じである。問題は挿入直後に「赤の連続」（性質4違反）が起きたときの修復（fixup）で、修復方法は挿入位置と周辺ノードの色・形によって場合分けされる。

ヒント2（アプローチ）

違反している赤ノード $z$ の親 $p$、祖父 $g$、叔父（$p$の兄弟）$y$ の色によって3ケースに分かれる：Case1（叔父も赤）は再彩色のみで回転不要、違反が祖父に持ち上がりループ継続。Case2（叔父黒・ジグザグ）は親を中心に1回転してCase3の形に整形。Case3（叔父黒・一直線）は色を入れ替えて祖父中心に1回転しループ終了。Case2は単独では終わらず必ずCase3に続くため、Case2発生時は回転2回、Case3のみなら1回、Case1のみなら0回になる。

ヒント3（誘導）

NILを表す共有の番兵ノードを1つ用意し、色は常に黒とすることで、境界条件（根の親やリーフの子）を特別扱いせずに済む。

RED, BLACK = 1, 0

NIL = Node.__new__(Node)
NIL.color = BLACK
NIL.left = NIL.right = NIL.parent = NIL  # 自己参照の番兵

def left_rotate(tree, x):
    tree.rotations += 1
    y = x.right
    x.right = y.left
    if y.left is not NIL:
        y.left.parent = x
    y.parent = x.parent
    if x.parent is NIL:
        tree.root = y
    elif x is x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x
    x.parent = y

模範解答 (Python)

import sys

RED, BLACK = 1, 0


class Node:
    __slots__ = ('key', 'color', 'left', 'right', 'parent')

    def __init__(self, key=None, color=BLACK):
        self.key = key
        self.color = color
        self.left = None
        self.right = None
        self.parent = None


NIL = Node.__new__(Node)
NIL.key = None
NIL.color = BLACK
NIL.left = NIL
NIL.right = NIL
NIL.parent = NIL


class RBTree:
    def __init__(self):
        self.root = NIL
        self.rotations = 0

    def left_rotate(self, x):
        self.rotations += 1
        y = x.right
        x.right = y.left
        if y.left is not NIL:
            y.left.parent = x
        y.parent = x.parent
        if x.parent is NIL:
            self.root = y
        elif x is x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    def right_rotate(self, x):
        self.rotations += 1
        y = x.left
        x.left = y.right
        if y.right is not NIL:
            y.right.parent = x
        y.parent = x.parent
        if x.parent is NIL:
            self.root = y
        elif x is x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y
        y.right = x
        x.parent = y

    def insert(self, key):
        z = Node(key, RED)
        z.left = NIL
        z.right = NIL
        z.parent = NIL

        y = NIL
        x = self.root
        while x is not NIL:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y is NIL:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

        self._insert_fixup(z)

    def _insert_fixup(self, z):
        while z.parent.color == RED:
            if z.parent is z.parent.parent.left:
                y = z.parent.parent.right
                if y.color == RED:
                    z.parent.color = BLACK
                    y.color = BLACK
                    z.parent.parent.color = RED
                    z = z.parent.parent
                else:
                    if z is z.parent.right:
                        z = z.parent
                        self.left_rotate(z)
                    z.parent.color = BLACK
                    z.parent.parent.color = RED
                    self.right_rotate(z.parent.parent)
            else:
                y = z.parent.parent.left
                if y.color == RED:
                    z.parent.color = BLACK
                    y.color = BLACK
                    z.parent.parent.color = RED
                    z = z.parent.parent
                else:
                    if z is z.parent.left:
                        z = z.parent
                        self.right_rotate(z)
                    z.parent.color = BLACK
                    z.parent.parent.color = RED
                    self.left_rotate(z.parent.parent)
        self.root.color = BLACK


def solve():
    data = sys.stdin.read().split()
    n = int(data[0])
    keys = data[1:1 + n]

    tree = RBTree()
    for k in keys:
        tree.insert(int(k))

    print(tree.rotations)


solve()

Step-by-Step 解説

1通常のBST挿入 + 赤で追加
新しいノード $z$ は普通の二分探索木と同じ手順で挿入位置を探し、常に赤で追加する。赤で追加するのは、性質5（黒高さの一致）を壊さないための工夫である。

2発生しうる違反は性質4のみ
赤で追加した直後に壊れうる性質は「赤の子は黒でなければならない」（性質4）だけである。よって修復ループは「親が赤である間」だけ回る。

3Case 1（再彩色のみ、回転0）
叔父も赤の場合、親・叔父を黒、祖父を赤にする再彩色だけで局所的な性質4違反は解消するが、祖父が赤になったことで新たな違反が起きる可能性があるため、$z$ を祖父に移してループを継続する。回転は発生しない。

4Case 2 → Case 3（回転1〜2回）
叔父が黒の場合、再彩色だけでは解決できず回転が必要になる。$z$ が親の「内側の子」（ジグザグ形）ならCase2で親を中心に1回転させて「外側の子」（一直線）の形に整形してからCase3に進む。Case3では親と祖父の色を交換し、祖父を中心に1回転させてループを終了する。

5計算量とループ回数
修復ループは高々 $O(\log N)$ 回反復するが、回転を伴うCase2・Case3はループを必ず終了させるため、1回の挿入で発生する回転はたかだか2回。全体の挿入は $O(N \log N)$。

よくあるミス

ミス	原因	正しい書き方
NILの色を初期化し忘れて未定義になる	番兵ノードは特別だという意識が薄い	`NIL.color = BLACK` を明示的に設定する（性質3の実装）
Case2で `z = z.parent` を忘れて直接回転してしまう	「回転対象がどのノードか」を誤解	Case2はまず `z` を親に更新してから、その新しい `z` を中心に回転する
Case1で `z = z.parent.parent` の代入を忘れ、無限ループになる	再彩色後に違反が上に伝播することを見落とす	Case1の最後に必ず `z = z.parent.parent` として次のループへ進める
最後に `root.color = BLACK` を忘れる	性質2（根は黒）の維持を怠る	ループを抜けたあと必ず根を黒にする

次のステップ

発展: 赤黒木からの削除（RB-DELETE-FIXUP）は挿入よりケース分岐が多く（二重黒の伝播）、回転回数の解析も複雑になる。
次回予告: フェーズローテーション継続（Master Level）

自己評価

完全理解おおむね理解要復習

Day 125-Q5 — 赤黒木（Red-Black Tree）への挿入と回転回数

問題