二分探索木と平衡二分探索木 入門 - AVL木・赤黒木がなぜ必要かを実装で理解する

ソート済みの配列に対する二分探索は、要素数nに対してO(log n)で目的の値を見つけられます。ところが、その配列に新しい要素を1つ挿入しようとした途端に話が変わります。挿入位置は二分探索ですぐ分かるのに、そこから後ろの要素を全部ずらす必要があるため、挿入も削除もO(n)かかってしまうのです。データが固定なら配列で十分ですが、要素が絶えず出入りする集合を扱いたいときには別の道具が要ります。二分探索木（binary search tree、BST）は、配列の「順序を保つ」という性質を木の形に写し替えることで、探索・挿入・削除をすべて木の高さに比例する時間で行えるようにしたデータ構造です。この記事では素朴なBSTの実装から、それが簡単に一直線へ退化してしまう問題、そしてそれを防ぐAVL木と赤黒木という2つの古典的な解法までを、実際に動かして出力を確認したPythonコードで順に追います。二分探索入門やハッシュテーブルの仕組みと同じアルゴリズム/データ構造入門シリーズの1本です。

ソート済み配列の限界 — 探索は速いが更新が遅い

まず出発点を確認します。ソート済み配列に対する操作の計算量は次の通りです。

ソート済み配列は探索が速い代わりに更新が遅く、連結リストは更新が速い代わりに探索が遅い。この両者のいいとこ取りをしたいというのが、二分探索木の動機です。Pythonの標準ライブラリbisectのドキュメントにも、insort()について「対数時間の探索はO(n)の遅い挿入処理に支配される（theO(log n)search is dominated by the slowO(n)insertion step）」という注意が明記されています。ソート済みリストとbisectの組み合わせが万能ではないのは、まさにこの点です。

なお「最小値・最大値だけが欲しい」のであれば木は過剰で、ヒープのほうが適しています。用途の違いはヒープと優先度付きキュー入門にまとめています。

二分探索木とは — 左は小さく、右は大きい

二分探索木は、各ノードが高々2つの子（左の子・右の子）を持つ二分木のうち、次の不変条件（BST条件）を満たすものです。

• あるノードの左部分木に含まれるキーは、すべてそのノードのキーより小さい
• あるノードの右部分木に含まれるキーは、すべてそのノードのキーより大きい
• 左右の部分木も、それぞれ二分探索木である

言葉より図のほうが早いので、50, 30, 70, 20, 40, 60, 80をこの順に挿入した木を示します。

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

根が50で、左部分木{20, 30, 40}はすべて50未満、右部分木{60, 70, 80}はすべて50より大きい。この条件が全ノードで再帰的に成り立っています。

重要なのは、条件が「親と子」だけでなく「ノードと部分木全体」について課される点です。よくある誤解として、30の右の子に55を置いても親子関係だけ見れば30より大きく矛盾しないように見えますが、55は根50の左部分木に属するため50未満でなければならず、BST条件を破ります。この場合、55の探索は根で右に折れてしまうので永遠に見つかりません。

キーの重複をどう扱うかは実装の選択です。ここでは重複を許さない集合（set）として扱い、同じキーの挿入は無視します。重複を許したい場合は、片側（たとえば右部分木）に等しいキーを寄せる、あるいはノードに出現回数のカウンタを持たせる、といった方法を取ります。

基本操作の実装 — 探索と挿入

探索は「根から始めて、目的のキーが現在のノードより小さければ左へ、大きければ右へ進む」だけです。二分探索で配列の探索範囲を半分にしていたのと同じことを、木の枝をたどる形で行っています。

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
 
class BST:
    def __init__(self):
        self.root = None
 
    def search(self, key):
        node = self.root
        while node is not None:
            if key == node.key:
                return True
            node = node.left if key < node.key else node.right
        return False
 
    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
            return
        node = self.root
        while True:
            if key == node.key:
                return  # 重複は無視する
            if key < node.key:
                if node.left is None:
                    node.left = Node(key)
                    return
                node = node.left
            else:
                if node.right is None:
                    node.right = Node(key)
                    return
                node = node.right
 
    def height(self):
        def rec(node):
            if node is None:
                return -1
            return 1 + max(rec(node.left), rec(node.right))
        return rec(self.root)
 
 
bst = BST()
for k in [50, 30, 70, 20, 40, 60, 80]:
    bst.insert(k)
 
print(bst.search(40))
print(bst.search(45))
print(bst.height())

実行結果です。

True
False
2

挿入は探索とほぼ同じで、進んだ先がNone（空）になったところに新しいノードをぶら下げるだけです。探索も挿入も、根から葉に向かって1本の経路をたどるだけなので、コストは木の高さに比例します。ここでは葉の高さを0、根から葉までの最長経路の長さを木の高さと定義しています（7ノードの完全に詰まった木なので高さは2）。

削除の3ケース — 子なし・子1つ・子2つ

削除だけは少し面倒です。ノードを取り除いたあともBST条件を保たなければならないため、対象ノードが持つ子の数によって3通りの処理に分かれます。

1. 子なし（葉）: そのまま取り除く。親の該当ポインタをNoneにする
2. 子が1つ: そのノードを削除し、唯一の子を親に直接つなぐ（「持ち上げる」）
3. 子が2つ: 削除対象のキーを中順後継（in-order successor、右部分木の最小値）のキーで上書きし、その中順後継を右部分木から削除する

3番目が肝心なところです。中順後継は「削除対象より大きいキーの中で最小のもの」なので、そこに置き換えれば左部分木の全要素より大きく、右部分木の残り全要素より小さいという条件がそのまま保たれます。しかも中順後継は右部分木の最左端にあるため、定義上左の子を持ちません。つまりその削除はケース1かケース2に帰着し、再帰は1段で止まります。中順後継の代わりに中順先行（左部分木の最大値）を使う実装も同様に正しく、こちらは右の子を持ちません。

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
 
def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    return node
 
 
def min_node(node):
    while node.left is not None:
        node = node.left
    return node
 
 
def delete(node, key):
    if node is None:
        return None
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        # ケース1: 子なし / ケース2: 子1つ
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        # ケース3: 子2つ -> 右部分木の最小値（中順後継）で置き換える
        succ = min_node(node.right)
        node.key = succ.key
        node.right = delete(node.right, succ.key)
    return node
 
 
def inorder(node, out):
    if node is None:
        return out
    inorder(node.left, out)
    out.append(node.key)
    inorder(node.right, out)
    return out
 
 
root = None
for k in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, k)
 
root = delete(root, 20)          # 子なし
print("del 20   :", inorder(root, []))
root = delete(root, 30)          # 子1つ（右に40）
print("del 30   :", inorder(root, []))
root = delete(root, 50)          # 子2つ（根）
print("del 50   :", inorder(root, []))
print("new root :", root.key)

実行結果です。

del 20   : [30, 40, 50, 60, 70, 80]
del 30   : [40, 50, 60, 70, 80]
del 50   : [40, 60, 70, 80]
new root : 60

根50を削除したあと、右部分木の最小値である60が新しい根になっています。ケース1とケース2を「子がNoneならもう片方を返す」という2行で書けているのは、Noneを返す処理が呼び出し元でnode.left = ...のように代入されるからです。この「再帰関数が新しい部分木の根を返す」という書き方は、後述する平衡木の実装でも同じ形で効いてきます。

走査（traversal） — 中順・前順・後順

二分探索木の嬉しい性質のひとつが、中順走査（in-order traversal）でキーが昇順に並ぶことです。左部分木を先に、次に自分、最後に右部分木という順で訪れると、BST条件からその並びは必ずソート順になります。上のコードでinorderの結果が常に昇順になっているのはこのためです。

訪問順の違いは3種類あります。

前順は「自分を先に確定させる」ので、同じ順番で挿入し直せば同じ形の木が復元できます（木の保存・復元に向く）。後順は「子を全部片付けてから自分を処理する」ので、メモリ解放や部分木のサイズ集計に向きます。これらは幅優先探索・深さ優先探索の一種でもあり、より一般のグラフでの扱いはグラフ探索アルゴリズム入門を参照してください。

そして、この中順走査こそが「ハッシュテーブルにはできないこと」の正体です。ハッシュテーブルは平均O(1)で完全一致検索ができますが、キーがハッシュ値の順に散らばっているため、ソート順の列挙も範囲検索（「30以上60以下のキーを全部」）もできません。

最悪ケース — ソート済みデータで一直線に退化する

ここまでの操作はすべて「木の高さに比例するコスト」でした。ではその高さはどれくらいでしょうか。ノード数nの二分木の高さは、うまく詰まっていればlog2(n)程度ですが、素朴なBSTは入力の順序次第で簡単に一直線に退化します。

昇順に1, 2, 3, 4, 5を挿入すると、新しいキーは常に「今いるノードより大きい」ので必ず右へ右へと進み、こうなります。

  1
   \
    2
     \
      3
       \
        4
         \
          5

これはもう木ではなく連結リストで、探索はO(n)です。実際に測ってみます。

import math
import random
 
class Node:
    __slots__ = ("key", "left", "right")
 
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
 
def insert_iter(root, key):
    if root is None:
        return Node(key)
    node = root
    while True:
        if key < node.key:
            if node.left is None:
                node.left = Node(key)
                return root
            node = node.left
        elif key > node.key:
            if node.right is None:
                node.right = Node(key)
                return root
            node = node.right
        else:
            return root
 
 
def height_iter(root):
    """再帰だと退化した木でスタックが溢れるので明示スタックで測る"""
    if root is None:
        return -1
    best = 0
    stack = [(root, 0)]
    while stack:
        node, d = stack.pop()
        if d > best:
            best = d
        if node.left is not None:
            stack.append((node.left, d + 1))
        if node.right is not None:
            stack.append((node.right, d + 1))
    return best
 
 
def build(keys):
    root = None
    for k in keys:
        root = insert_iter(root, k)
    return root
 
 
n = 10000
sorted_keys = list(range(n))
random_keys = list(range(n))
random.seed(42)
random.shuffle(random_keys)
 
print(f"n = {n} / 完全平衡な二分木の高さ = {math.floor(math.log2(n))}")
for label, keys in [("sorted", sorted_keys), ("random", random_keys)]:
    print(f"  {label:>6} 順に挿入 -> 高さ {height_iter(build(keys))}")

実行結果です。

n = 10000 / 完全平衡な二分木の高さ = 13
  sorted 順に挿入 -> 高さ 9999
  random 順に挿入 -> 高さ 31

ランダム順なら高さ31で済むのに、昇順に入れただけで高さ9999、つまり完全に一直線になっています。しかも「ソート済みのデータを順に投入する」というのは、DBからORDER BY付きで取り出したレコードを入れる、タイムスタンプ順のログを入れる、連番のIDを入れるなど、実務ではむしろありふれた入力パターンです。平均計算量O(log n)という説明を鵜呑みにできない理由がここにあります。計算量の平均と最悪の違いについては計算量とBig-O記法 入門も合わせてどうぞ。

まとめると、素朴なBSTの計算量は次の通りです。

平衡と回転 — 木の形を組み替える

この退化を防ぐのが平衡二分探索木（self-balancing binary search tree）です。基本的な考え方は「挿入・削除のたびに木の形を少し組み替えて、高さをO(log n)に保つ」というもの。その組み替えの道具が回転（rotation）です。

回転は、親子関係にある2つのノードの上下を入れ替える操作で、BST条件を壊さずに木の高さのバランスを移動できるという性質を持ちます。

右回転（root を y から x へ移す）
 
        y                      x
       / \                    / \
      x   C     ------>      A   y
     / \        <------          / \
    A   B        左回転          B   C

この図でAのキーはすべてx未満、Bのキーはxより大きくy未満、Cのキーはyより大きい、という関係にあります。回転後もこの大小関係は保たれます。中順走査した結果はどちらの形でもA, x, B, y, Cで変わりません。回転は木の形だけを変え、キーの並び順は一切変えないのがポイントです。

回転そのものは、いくつかのポインタを付け替えるだけなのでO(1)で終わります。実装は次の通りです（updateは部分木の高さを再計算するヘルパーで、次節で使います）。

def rotate_right(y):
    """y を右回転して、左の子 x を新しい根にする"""
    x = y.left
    y.left = x.right
    x.right = y
    update(y)
    update(x)
    return x
 
 
def rotate_left(x):
    """x を左回転して、右の子 y を新しい根にする"""
    y = x.right
    x.right = y.left
    y.left = x
    update(x)
    update(y)
    return y

「どういう条件で、どこを回転させるか」の決め方が平衡木の設計そのもので、代表的な答えがAVL木と赤黒木です。

AVL木 — 平衡因子を -1, 0, 1 に保つ

AVL木は、Georgy Adelson-Velsky と Evgenii Landis が1962年の論文「An algorithm for the organization of information」（ソ連科学アカデミー報告 Doklady Akademii Nauk SSSR, vol.146, pp.263-266。英訳は Soviet Mathematics Doklady, vol.3, pp.1259-1263）で発表した、史上初の自己平衡二分探索木です。名前は2人の頭文字から取られています。

不変条件はきわめてシンプルで、全ノードについて平衡因子（balance factor）が-1, 0, 1のいずれかに収まることです。平衡因子は「右部分木の高さ引く左部分木の高さ」と定義されます（符号の向きは文献によって逆のこともあります）。

挿入によってどこかのノードの平衡因子が2や-2になったら、そのノードを根とする部分木を回転で直します。壊れ方は4パターンあります。

LL: 左の子の左に挿入        LR: 左の子の右に挿入
      z                          z
     /                          /
    y          -> 右回転       y        -> yを左回転してからzを右回転
   /                            \
  x                              x
 
RR: 右の子の右に挿入        RL: 右の子の左に挿入
  z                          z
   \                          \
    y      -> 左回転           y        -> yを右回転してからzを左回転
     \                        /
      x                      x

LLとRRは1回の回転（単回転）、LRとRLは2回の回転（二重回転）で直ります。判定は「自分の平衡因子の符号」と「重い側の子の平衡因子の符号」が一致するか否かで、一致すればLLかRR、食い違えばLRかRLです。

高さの上界も分かっています。高さhのAVL木が持ちうる最小のノード数はフィボナッチ数列と同じ漸化式m(h) = 1 + m(h-1) + m(h-2)に従うため、ノード数nのAVL木の高さhには次の上界が成り立ちます（φは黄金比1.618...、bはおよそ-0.328）。

log2(n + 1)  <=  h  <  log_φ(n + 2) + b
             ただし 1 / log2(φ) = 1.4405...

つまりAVL木の高さは、完全平衡な木のおよそ1.44倍を超えません。実装と検証コードは次の通りです。

import math
 
class AVLNode:
    __slots__ = ("key", "left", "right", "height")
 
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 0  # 葉の高さを0とする
 
 
def h(node):
    return -1 if node is None else node.height
 
 
def update(node):
    node.height = 1 + max(h(node.left), h(node.right))
 
 
def balance_factor(node):
    return h(node.right) - h(node.left)
 
 
def rebalance(node):
    update(node)
    bf = balance_factor(node)
    if bf < -1:                                    # 左に重い
        if balance_factor(node.left) > 0:
            node.left = rotate_left(node.left)     # LR ケース
        return rotate_right(node)                  # LL ケース
    if bf > 1:                                     # 右に重い
        if balance_factor(node.right) < 0:
            node.right = rotate_right(node.right)  # RL ケース
        return rotate_left(node)                   # RR ケース
    return node
 
 
def avl_insert(node, key):
    if node is None:
        return AVLNode(key)
    if key < node.key:
        node.left = avl_insert(node.left, key)
    elif key > node.key:
        node.right = avl_insert(node.right, key)
    else:
        return node
    return rebalance(node)
 
 
def check_avl(node):
    """全ノードで平衡因子が -1/0/1 に収まっているか検証する"""
    if node is None:
        return True
    if abs(balance_factor(node)) > 1:
        return False
    return check_avl(node.left) and check_avl(node.right)
 
 
n = 10000
root = None
for k in range(n):          # わざと昇順に挿入する
    root = avl_insert(root, k)
 
print("AVL: 昇順に", n, "件挿入")
print("  高さ      =", h(root))
print("  完全平衡なら", math.floor(math.log2(n)))
print("  AVLの高さ上限 =", math.floor(1.4405 * math.log2(n + 2) - 0.3277))
print("  平衡条件OK =", check_avl(root))

実行結果です。

AVL: 昇順に 10000 件挿入
  高さ      = 13
  完全平衡なら 13
  AVLの高さ上限 = 18
  平衡条件OK = True

素朴なBSTでは高さ9999だった同じ入力が、AVL木では高さ13、つまり完全平衡と同じ値に収まりました。探索コストの差も測ってみます。

def steps_to_find(root, key):
    node, cnt = root, 0
    while node is not None:
        cnt += 1
        if key == node.key:
            return cnt
        node = node.left if key < node.key else node.right
    return cnt

n = 2000件を昇順に挿入した素朴なBSTとAVL木に対し、200件をランダムに検索した平均比較回数は次のようになりました。

昇順に 2000 件挿入して 200 件をランダムに検索したときの平均比較回数
  素朴なBST :   1061.6 回
  AVL木     :      9.9 回

100倍以上の差です。素朴なBSTの平均比較回数がおよそn/2になっているのは、まさに連結リストを線形探索しているからです。

赤黒木 — 5つの性質と、より緩い平衡

もう一方の代表格が赤黒木（red-black tree）です。起源は Rudolf Bayer が1972年に発表した論文「Symmetric binary B-Trees: Data structure and maintenance algorithms」（Acta Informatica, vol.1, pp.290-306）の対称二分B木で、これに赤と黒の色という枠組みと現在の名前を与えたのが Leonidas J. Guibas と Robert Sedgewick の1978年の論文「A Dichromatic Framework for Balanced Trees」（19th Annual Symposium on Foundations of Computer Science, pp.8-21）です。

赤黒木は、各ノードに赤か黒の色を持たせ、次の性質を保ちます。

1. すべてのノードは赤か黒のいずれかである
2. 根は黒である
3. すべての葉（NIL、空の子）は黒とみなす
4. 赤いノードの子は赤であってはならない（赤が2つ連続しない）
5. あるノードからその下の葉に至るどの経路も、通過する黒いノードの数が等しい（黒高さが一定）

この5条件から高さの上界が導けます。あるノードの黒高さをbhとすると、その部分木のノード数nは2^bh - 1以上であり、また性質4から黒でないノードは連続しないので木の高さhは2 * bh以下です。この2つを組み合わせると、ノード数nの赤黒木の高さは高々2 * log2(n + 1)に収まります。

AVL木の1.44 * log2(n)と比べると、赤黒木の平衡はゆるいということになります。この違いが実務上のトレードオフを生みます。Linuxカーネルの公式ドキュメント「Red-black Trees (rbtree) in Linux」は、この点を次のように説明しています。

Red-black trees are similar to AVL trees, but provide faster real-time bounded worst case performance for insertion and deletion (at most two rotations and three rotations, respectively, to balance the tree), with slightly slower (but still O(log n)) lookup time.

つまり赤黒木は挿入で高々2回、削除で高々3回の回転で平衡を回復できるのに対し、AVL木は削除時に根まで遡って最悪O(log n)回の回転が必要になり得ます。代わりにAVL木のほうが木が浅いので探索はわずかに速い、という関係です。

Sedgewick が2008年に提案した左傾赤黒木（left-leaning red-black tree、LLRB）は、「赤いリンクは常に左側」という追加制約を課すことでコード量を大幅に減らした変種です。挿入部分だけなら次のように短く書けます。

RED, BLACK = True, False
 
 
class RBNode:
    __slots__ = ("key", "left", "right", "color")
 
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.color = RED       # 新しいノードは常に赤で挿入する
 
 
def is_red(node):
    return node is not None and node.color is RED
 
 
def flip_colors(node):
    node.color = RED
    node.left.color = BLACK
    node.right.color = BLACK
 
 
def rb_insert(node, key):
    if node is None:
        return RBNode(key)
    if key < node.key:
        node.left = rb_insert(node.left, key)
    elif key > node.key:
        node.right = rb_insert(node.right, key)
 
    # 左傾赤黒木（LLRB）の3つの整形規則
    if is_red(node.right) and not is_red(node.left):
        node = rotate_left(node)
    if is_red(node.left) and is_red(node.left.left):
        node = rotate_right(node)
    if is_red(node.left) and is_red(node.right):
        flip_colors(node)
    return node
 
 
def insert(root, key):
    root = rb_insert(root, key)
    root.color = BLACK          # 性質2: 根は黒
    return root

新しいキーは常に赤で挿入し、帰りがけに3つの規則を上から順に適用するだけで性質が保たれます（回転関数はAVL木で使ったものから色の付け替えを加えたものを使います）。実際に昇順で挿入し、性質と高さを検証した結果が次です。

n=  1000  高さ=  9  黒高さ=9  赤赤なし=True  上限 2*log2(n+1)=19.9
n= 10000  高さ= 13  黒高さ=13  赤赤なし=True  上限 2*log2(n+1)=26.6
n=100000  高さ= 16  黒高さ=16  赤赤なし=True  上限 2*log2(n+1)=33.2
ランダム順 n=100000 高さ=23 黒高さ=13

昇順挿入でも高さは上限の半分以下に収まり、性質4（赤が連続しない）と性質5（黒高さが一定）が全ノードで成立していることが確認できます。

3種類を並べると次のようになります。

実務での使われ方 — 各言語とOSカーネルの事情

「順序を保つ連想コンテナ」を標準で持つかどうかは言語によって大きく違います。ここは誤解が多いところなので、公式ドキュメントとソースで確認した内容を整理します。

C++について正確に書いておきます。C++規格がstd::mapに要求しているのは、キー順にイテレートできることと、find・insertが対数時間、erase(k)がlog(a.size()) + a.count(k)であることだけで、赤黒木を使えとは書かれていません。ただし実装を見ると、GCCのlibstdc++のbits/stl_tree.hには「Red-black tree class, designed for use in implementing STL associative containers (set, multiset, map, and multimap).」というヘッダコメントがあり、LLVMのlibc++の__treeにも「__tree is a red-black-tree implementation used for the associative containers」とあります。つまり「規格上は実装依存だが、主要な実装は赤黒木」というのが正確な言い方です。cppreferenceも「Maps are usually implemented as Red-black trees.」と、あくまで"usually"という表現をしています。

Javaは明快で、TreeMapのJavadocは冒頭で「A Red-Black tree based NavigableMap implementation.」と述べ、「containsKey・get・put・removeについてlog(n)時間を保証する」と明記しています。アルゴリズムは Cormen, Leiserson, Rivest の『Introduction to Algorithms』に基づくとも書かれています。

RustのBTreeMapは名前の通りB木で、公式ドキュメントは二分探索木を選ばなかった理由を明確に説明しています。「理論上は完全平衡なBSTが比較回数を最小化する最適解だが、実際にはこのやり方は現代の計算機アーキテクチャにとって非常に非効率である」「あらゆる要素がヒープ上に個別確保されたノードに格納されるため、挿入のたびにヒープ確保が起き、比較のたびに間接参照によるキャッシュミスの可能性がある」。B木は1ノードにB-1から2B-1個の要素を連続配列で持つことで、確保回数をB分の1にしキャッシュ効率を上げています。

Pythonには標準の平衡木がありません。実務ではbisectとリストの組み合わせか、外部ライブラリのsortedcontainersを使います。ここも誤解されがちですが、sortedcontainersは平衡木ではなく「リストのリスト」です。公式ドキュメントは「従来の木ベースの設計はビッグO記法上は優れているが、今日のソフトウェアとハードウェアの現実を無視している」とし、短いリストへの挿入・削除がほとんどメモリ確保を伴わないこと、要素へのポインタが密に詰まっていてキャッシュ効率が良いことを理由に挙げています。

Goは標準ライブラリに順序付きマップを持たず、github.com/google/btreeのような外部パッケージで代用するのが一般的です。標準にordered.Map/ordered.Setを追加する提案（golang/go issue 60630、2023年提出）はありますが、本記事執筆時点（2026年8月）でオープンのままです。

Linuxカーネルは赤黒木（rbtree）の代表的な利用例です。lib/rbtree.cに実装があり、各データ構造にstruct rb_nodeを直接埋め込むことでポインタの間接参照を1段減らしている点が特徴です。現行カーネルのソースで確認できる利用箇所としては、epollの監視対象ファイルディスクリプタの管理（fs/eventpoll.cのstruct rb_root_cached rbr）、高分解能タイマーの期限管理（include/linux/timerqueue.hがrbtreeの上に構築されている）、そしてスケジューラがあります。カーネル6.6でCFSから移行が始まったEEVDF（Earliest Eligible Virtual Deadline First）スケジューラも、実行可能タスクを仮想実行時間をキーとしたrbtreeで保持し、各ノードに部分木の最小仮想デッドラインを持たせた拡張赤黒木（augmented rbtree）として管理しています。

一点、古い資料を読むときの注意があります。カーネル公式のrbtreeドキュメントは2007年執筆で、利用例として「Virtual memory areas (VMAs) are tracked with red-black trees」と挙げていますが、VMAの管理は Linux 6.1 で maple tree に置き換えられました。maple treeはRCU安全な範囲ベースのB木で、分岐数が大きいぶんrbtreeより木が浅くキャッシュミスが少ない、範囲を扱いやすい、といった理由で導入されています。「赤黒木は範囲クエリやロックレス操作が苦手」という弱点が実際に効いた例です。

ハッシュテーブル・B木との使い分け

平衡二分探索木を選ぶべきかどうかは、次の3つの問いで大体決まります。

1. 順序が必要か: ソート順の列挙、最小値・最大値、前後の要素（predecessor / successor）が要るならハッシュテーブルでは無理
2. 範囲検索が必要か: 「30以上60未満」のような区間問い合わせが要るなら木
3. 最悪計算量の保証が要るか: 悪意ある入力でハッシュ衝突を意図的に起こされる可能性があるなら、O(log n)が保証される木のほうが安全

ハッシュテーブル側の詳細（衝突解決や負荷率）はハッシュテーブルの仕組みに、文字列の接頭辞検索に特化した木はトライ木入門にまとめています。

もうひとつの分岐がB木・B+木です。二分探索木は1ノードにキーを1つしか持たず、比較のたびにポインタを1回たどります。これはデータがメモリ上にあるうちはよいのですが、データがディスクにあると、ポインタを1回たどるたびにディスクI/O（あるいはページ読み込み）が発生してしまいます。そこでB木は1ノードにキーを数十から数百個詰め込み、ノードのサイズをディスクのページサイズに合わせます。分岐数がBになるので木の高さはlog_B(n)となり、100万件でも数段で済みます。RustのBTreeMapやLinuxのmaple treeがB木を採用しているのも、ディスクではなくCPUキャッシュラインという「現代のページ」に合わせた同じ発想です。データベースのインデックスがB+木で作られている理由はデータベースインデックス入門で詳しく扱っています。

よくある落とし穴

• 「BSTはO(log n)」と暗記してしまう: 素朴なBSTのO(log n)はあくまで平均であり、しかも「挿入順がランダムなら」という前提付きです。昇順・降順のデータを入れればO(n)に退化します。保証が欲しいなら平衡木を使ってください
• BST条件を親子だけでチェックする: 「左の子は親より小さい」だけを再帰的に確認しても不十分で、部分木全体が範囲に収まっているかを見る必要があります。検証は各ノードに許される(下限, 上限)を伝播させながら再帰するか、中順走査の結果が昇順になっているかを確認するのが確実です
• 削除で中順後継の削除を忘れる: 子2つのケースで、中順後継のキーをコピーしたのに元の中順後継ノードを削除し忘れると、同じキーが2箇所に存在する壊れた木になります
• 削除で右部分木の最小値ではなく「右の子」を持ち上げる: 子2つのノードを消すときに単純に右の子を親につなぐと、左部分木の行き場がなくなるかBST条件が壊れます
• 回転後に高さの更新を忘れる: AVL木では回転で入れ替わった2ノードの高さを、必ず下から順に更新する必要があります。順番を間違えると平衡因子の計算が狂い、以後の判定がすべて誤ります
• 再帰実装でスタックが溢れる: 退化したBSTに対して再帰で高さを測ったり走査したりすると、Pythonの再帰上限に容易に達します。上の実測コードで明示スタックを使ったのはこのためです
• とりあえず自前で赤黒木を書く: 赤黒木の削除は場合分けが多く、教科書を見ながらでもバグらせやすい部分です。標準ライブラリに順序付きコンテナがあるならそれを、なければ実績のあるライブラリを使うのが基本で、自作は学習目的に留めるのが無難です
• 順序が要らないのに木を選ぶ: 完全一致検索しかしないならハッシュテーブルのほうが速く、実装も単純です。木を選ぶ理由は「順序」か「最悪計算量の保証」のどちらかであるべきです

まとめ

• 二分探索木（BST）は「左部分木のキーはすべて自分より小さく、右部分木のキーはすべて自分より大きい」という不変条件を持つ二分木。探索・挿入・削除はいずれも木の高さに比例するコストで行える
• 削除は子なし・子1つ・子2つの3ケースに分かれ、子2つの場合は中順後継（右部分木の最小値）のキーで置き換えてから、その中順後継を削除する
• 中順走査でキーが昇順に取り出せるのがBSTの本質的な強みで、ハッシュテーブルには真似できない。前順は木の復元、後順はメモリ解放や集計に向く
• 素朴なBSTは入力順に脆く、昇順のデータを挿入すると一直線に退化してO(n)になる。実測ではn = 10000の昇順挿入で高さ9999、ランダム順で高さ31だった
• 回転（rotation）はBST条件を保ったまま木の形だけを組み替えるO(1)の操作で、あらゆる平衡木の基礎になる
• AVL木（Adelson-Velsky と Landis、1962年）は平衡因子を-1, 0, 1に保つ最初の自己平衡二分探索木。挿入時の壊れ方はLL・LR・RR・RLの4ケースで、高さは1.44 * log2(n)程度に収まる
• 赤黒木（Bayer の1972年の対称二分B木が起源、Guibas と Sedgewick が1978年に現在の枠組みを与えた）は5つの性質を持ち、高さは2 * log2(n + 1)以下。AVLより平衡は緩いが、挿入は高々2回・削除は高々3回の回転で済む
• 実務では、JavaのTreeMap/TreeSetが赤黒木と明記されており、C++のstd::mapは規格上は実装依存ながらlibstdc++・libc++とも赤黒木。RustのBTreeMapはB木で、Python・Go・JavaScriptは標準に順序付きコンテナを持たない
• Linuxカーネルはepoll・高分解能タイマー・EEVDFスケジューラなどでrbtreeを使う一方、VMA管理はカーネル6.1でmaple tree（B木の一種）に置き換えられている
• 順序も範囲検索も要らないならハッシュテーブル、ディスクやキャッシュのページ単位を意識するならB木、という使い分けになる

まずは本記事のBST実装をそのまま動かし、1, 2, 3, 4, 5を昇順に挿入して高さを測ってみてください。一直線になる様子を自分の目で見てからrebalanceを1行ずつ足していくと、「なぜ回転が必要か」「なぜ平衡因子を持つのか」が腑に落ちるはずです。そのうえで標準ライブラリのTreeMapやstd::mapのドキュメントを読み直すと、何が保証されていて何が実装依存なのかが見えてきます。

参考リンク

• AVL tree - Wikipedia
• Red-black tree - Wikipedia
• Rudolf Bayer, Symmetric binary B-Trees: Data structure and maintenance algorithms（Acta Informatica 1: 290-306, 1972）- dblp
• Leonidas J. Guibas, Robert Sedgewick, A Dichromatic Framework for Balanced Trees（FOCS 1978: 8-21）- dblp
• Left-Leaning Red-Black Trees（Robert Sedgewick, 2008 スライド）
• AVL Trees（CMSC 420 講義ノート, University of Maryland）
• AVL Trees: Proof of Height Bound（MIT 6.006 補足資料）
• Red-black Trees (rbtree) in Linux - Linux Kernel Documentation
• Maple Tree - Linux Kernel Documentation
• EEVDF Scheduler - Linux Kernel Documentation
• Introducing the Maple Tree（LWN.net）
• TreeMap（Java SE 21 API ドキュメント）
• TreeSet（Java SE 21 API ドキュメント）
• std::map - cppreference.com
• C++ 規格草案 associative.reqmts（連想コンテナの要件）
• libc++ の __tree ヘッダ（赤黒木実装）
• std::collections::BTreeMap - Rust 標準ライブラリ
• bisect - 配列二分法アルゴリズム（Python 公式ドキュメント）
• Sorted Containers Implementation（実装解説）
• proposal: container: add tree-based ordered.Map/Set（golang/go issue 60630）
• btree package - github.com/google/btree