二分探索木とは？仕組み・コード・計算量をわかりやすく解説

二分探索木が解決する問題

ソート済み配列は高速な二分探索ができますが、新しい要素を挿入すると、それ以降の要素をすべてずらすことになります。ハッシュテーブルは検索と挿入が高速ですが、順序を保持しないので、「42より大きい最小のキーは？」や「10から20の間のキーを列挙したい」といった問いには答えられません。二分探索木は、キーをソートされた状態に保ちながら、挿入と削除も高速に行えます。JavaのTreeMapやC++のstd::mapのような順序付きのマップやセットの基盤であり、それらは自己平衡型の変種を使っています。

ルールをひとことで

各ノードは、キーと、省略可能な左の子、省略可能な右の子を持ちます。どのノードについても、左部分木のキーはすべてそれより小さく、右部分木のキーはすべてそれより大きくなります。キーを探すには、根から始めて比較します。キーが小さければ左へ、大きければ右へ進み、等しければ終了、木の外に出てしまったら見つからなかったことになります。

具体例：木の構築と検索

8、3、10、1、6、14、4をこの順に挿入します。新しいキーは根から下っていき、木から外れた位置で葉になります。

4を検索すると、8、3、6、そして4と比較します。7キーの木で4回の比較です。7を検索すると、8、3、6と比較したあと、6に右の子がないので、7は存在しないと分かります。

Pythonでの実装

挿入と検索は短いループで書けます。削除には3つのケースがあります。子がない（そのまま削除）、子が1つ（その子で置き換える）、子が2つ（通りがけ順の後続ノード、つまり右部分木の最小キーをコピーしてから、その後続ノードを削除する）です。

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None
def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                      # duplicates are ignored
def contains(root, key):
    while root and root.key != key:
        root = root.left if key < root.key else root.right
    return root is not None
def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root
def inorder(root):
    return inorder(root.left) + [root.key] + inorder(root.right) if root else []

root = None
for k in [8, 3, 10, 1, 6, 14, 4]:
    root = insert(root, k)
print(inorder(root))                 # [1, 3, 4, 6, 8, 10, 14]
print(contains(root, 4), contains(root, 7))  # True False
root = delete(root, 3)               # node with two children
print(inorder(root), root.left.key)  # [1, 4, 6, 8, 10, 14] 4

時間計算量と空間計算量

最悪の場合は、理論上の話ではなく現実に起こります。すでにソートされたキー（1, 2, 3, ...）を素のBSTに挿入すると、どのノードも右の子しか持たず、木は連結リストになってしまいます。ランダムな順序で挿入すれば、高さの期待値はO(log n)です。

平衡型の変種と、よくある間違い

自己平衡木は、挿入や削除のあとに回転で構造を組み替えることで、高さをO(log n)に保ちます。

• 親と子だけを調べてBSTを検証してしまう。代わりに、有効な（下限、上限）の範囲を引き継いでいきましょう。
• 再帰的な挿入や削除で、（新しくなった可能性のある）根を返し忘れ、変更が失われる。
• 偏った木での深い再帰：Pythonのデフォルトの再帰上限は約1000なので、5000ノードの鎖では再帰のコードがクラッシュします。ループを使うか、木を平衡に保ちましょう。
• 重複の扱いが未定義：重複を無視するのか、数えるのか、常に片側に入れるのかを決めておきます。

BSTを使う場面と、面接でよく出る問題

挿入と削除が頻繁にあり、順序付きのデータが必要なとき（範囲クエリ、floorやceilingの検索、順位統計、ソート順での反復）は、平衡BSTを使います。完全一致のキー検索だけでよければ、ハッシュテーブルを使います。Pythonの標準ライブラリにはツリーマップがありません。小規模またはほぼ静的なデータなら、bisectモジュールとソート済みリストを組み合わせる方法か、サードパーティのsortedcontainersパッケージがよく選ばれます。

面接でよく出る問題：BSTの検証、k番目に小さい要素の発見（通りがけ順の巡回）、最小共通祖先、ソート済み配列から平衡BSTへの変換（真ん中を根にする）、ノードの通りがけ順の後続ノードの発見などです。