LASSIC Media らしくメディア

監修・編集責任者：牛尾 昭昌（株式会社LASSIC 執行役員）

二分探索木という言葉は、データ構造の教科書だけでなく、JavaのTreeMapやC++のstd::mapの説明、Linuxカーネルのドキュメントにも出てきます。ハッシュ表と何が違うのか、どんなときに選ぶのかを聞かれて、すぐに答えられない方もいるのではないでしょうか。二分探索木とは、各ノードに1つのキーを持たせ、左側には小さいキー、右側には大きいキーを置くように組み立てた木構造です。

キーを順序どおりに保てるので、一致する値を探すだけでなく、範囲や前後のキーを取り出す処理が得意です。一方で、入れる順番によって木が一列に偏る弱点があります。本記事では、探索・挿入・削除の仕組み、Pythonのコードで見る偏り、平衡木との関係、実務での使いどころとつまずきやすい点を整理します。

二分探索木とは

SedgewickとWayneの教科書『Algorithms』第4版は、二分探索木を次のように定義しています。各ノードが比較できるキー（と、それに結びつく値）を持つ二分木で、どのノードのキーも、左の部分木にあるすべてのキーより大きく、右の部分木にあるすべてのキーより小さい。^*1 各ノードは、キーと値のほかに、左右の子への2本のリンクを持ちます。

この決まりから、便利な性質が生まれます。左の部分木、根、右の部分木の順にたどると、キーが小さい順に並んで出てきます。教科書も、広く使われる大きな理由としてこの点を挙げています。ある値以下でいちばん大きいキー（floor）、ある値以上でいちばん小さいキー（ceiling）、範囲に入るキーの一覧を、同じ仕組みで求められます。

よく比べられるのが、並べ替えた配列です。配列は探す処理こそ速いものの、途中に1件入れるたびに後ろの要素をずらさなければなりません。教科書は二分探索木を、連結リストの挿入のしやすさと、順序付き配列の探索の速さを組み合わせたものと紹介しています。処理の速さを件数との関係で表すO(log n)などの書き方は、「計算量とオーダー記法の読み方」で扱っています。

探索・挿入・削除の仕組み

探索は根から始めます。探すキーがそのノードのキーと等しければ見つかり、小さければ左の子へ、大きければ右の子へ進みます。子が無いところに行き着いたら、そのキーは木に入っていません。1回の比較ごとに、片方の部分木を丸ごと調べずに済む点が速さの源です。

挿入も、探索とほぼ同じ手順で進みます。探すキーの代わりに入れたいキーで木をたどると、子の無い行き止まりに着きます。そのリンクを新しいノードに付け替えれば挿入は終わりで、すでにあるノードは一つも動きません。

削除は、消すノードの子の数で3通りに分かれます。子が無ければそのまま外し、子が1つならその子を親に直接つなぎます。難しいのは子が2つある場合で、1962年にT. Hibbardが示した方法では、消すノードを後継（右の部分木で最も小さいキーを持つノード）で置き換えます。^*1 消すキーと後継のキーの間には他のキーが無いので、置き換えても左右の大小の決まりは崩れません。

ここで押さえたいのは、速さが何で決まるかです。教科書は、探索、挿入、floorとceiling、削除などの操作は、最悪の場合、木の高さに比例した時間がかかるとしています。^*1 同じ件数でも、背の低い木なら速く、背の高い木なら遅くなります。

具体例：Pythonで高さを比べる

入れる順番で木の高さがどう変わるかを、Pythonで確かめます。1から500までの整数を昇順のまま入れた木と、ばらばらの順に入れた木の高さ（根から最も深いノードまでの段数）を表示します。

import random
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
def height(node):
    return 0 if node is None else 1 + max(height(node.left), height(node.right))
for name, keys in [("昇順", list(range(1, 501))), ("ランダム", random.sample(range(1, 501), 500))]:
    root = None
    for k in keys:
        root = insert(root, k)
    print(name, height(root))

昇順のほうは、何度実行しても「昇順 500」と表示されます。新しいキーは毎回それまでのどのキーより大きいので、右の子だけが500段つながり、連結リストと同じ形になります。ランダムのほうは実行ごとに値が変わり、乱数の種を変えて1,000回試したところ、高さは15〜29段で、9割の回が17〜22段に収まりました。500個のキーは、理屈の上では9段の木に収まります（9段なら511個まで入る）。

教科書は、ランダムな順に入れたN個のキーの木で、見つかる場合の探索にかかる比較は平均で約2 ln N（約1.39 lg N）回だとしています。^*1 Nが500なら約12回で、500回かかる昇順の木とは大きな差です。なお、このコードで昇順の件数を2,000に増やすと、再帰の深さがPythonの上限を超えてRecursionErrorで止まります。偏った木は、再帰で書いた処理そのものを落とすこともあります。

偏りの問題と平衡木

図の左右は、同じ1から7のキーを持つ二分探索木です。入れる順番が違うだけで、左は3段、右は7段になります。会員番号や受付日時のように、業務のデータは昇順に近い順で届くことが少なくありません。平衡を取らない二分探索木にそのまま入れると、右の形に近づきます。

この弱点を補うのが平衡木です。挿入や削除のたびに、回転と呼ばれる付け替えで親子関係を組み直し、高さを低く保ちます。代表の一つが、1962年にAdelson-VelskiiとLandisが発表したAVL木で、どのノードでも左右の部分木の高さの差を1以内に保ちます。^*3

もう一つの代表が赤黒木です。1978年にGuibasとSedgewickが発表した論文は、各ノードに色と呼ぶ1ビットを持たせて平衡の情報を記録する枠組みを示し、赤と黒の2色を使いました。条件は、葉の先の空のノードは黒、どのノードから葉の先までたどっても黒の数が同じ、赤が2つ続かない、の3つです。^*3 教科書は、N個のノードを持つ赤黒木の高さは2 lg N以下で、探索・挿入・削除などが最悪の場合でも対数時間で済むとしています。^*2

AVL木と赤黒木の使い分けについて、Linuxカーネルのドキュメントは、赤黒木はAVL木に似ているが、挿入と削除の最悪の時間が短く、形を整える回転は挿入で多くて2回、削除で多くて3回で済むと説明しています。探索はわずかに遅くなるものの、O(log n)であることは変わりません。^*6

B木・ハッシュ表との違い

二分探索木はメモリ上で使う前提の構造です。ディスクから読み出す回数を減らしたいデータベースの索引では、1つのノードに多くのキーを持たせたB木やB+木が使われます。その話は「B木の仕組み」に譲り、ここではハッシュ表と比べます。

JavaのHashMapのドキュメントは、getとputが定数時間で動くのは、ハッシュ関数が要素を格納先にうまく散らす場合だとしたうえで、要素の順序については何も保証しないと明記しています。^*7 Linuxカーネルのドキュメントも、ハッシュ表は順序どおりにたどれるように並んでおらず、決まった大きさとハッシュ関数に合わせた調整が要る一方、赤黒木は任意のキーを入れても無理なく伸び縮みすると説明しています。^*6

一致する値を引くだけならハッシュ表で足ります。「この時刻より前で最も新しい記録」のように順序や範囲が要るなら、平衡した二分探索木を使います。

実務での使いどころ

業務で二分探索木を一から書くことは多くありません。主な言語の標準ライブラリに、平衡木を使った順序付きのマップがあるからです。JavaのTreeMapは赤黒木をもとにした実装で、ドキュメントはcontainsKey、get、put、removeにlog(n)の時間を保証しています。^*4 floorKeyやceilingKeyで前後のキーを、subMapで範囲を取り出せます。

C++のstd::mapについて規格の作業草案が定めるのは、内部の構造ではなく計算量と順序です。find、insert、lower_bound、upper_boundなどの計算量を対数と定め、反復子がキーの小さい順（等しいキーを含む並び）にたどることを基本の性質としています。^*5 どの構造で満たすかは各実装に委ねられています。

OSの内部でも使われ、Linuxカーネルの赤黒木について2007年に書かれたドキュメントは、I/Oスケジューラーの要求の管理、高分解能タイマーの要求の整理、仮想メモリ領域の管理などを使用例に挙げています。^*6

業務システムでは、指定時刻の直前のイベントを引く処理、期限が近い順にタスクを取り出す処理、得点順のランキングなど、メモリ上で順序を保ったまま頻繁に更新したい場面が使いどころです。

つまずきやすい点

最も多いのは、平衡を取らない二分探索木を自前で書き、ランダムなテストデータだけで確かめて済ませることです。本番のデータが昇順に近い順で届くと、木が一列になって遅くなります。テストには昇順、降順、同じ値の連続、件数の多いデータも入れておきます。

削除をくり返すと偏る点も見落とされがちです。教科書は、150個のノードを持つ木でHibbardの方法による削除とランダムな挿入をくり返すと、木が左に偏っていく様子を示しています。^*1 挿入の順番だけでなく、更新が長く続いた後の形も考えておく必要があります。

比較のしかたの定義も落とし穴になります。TreeMapのドキュメントは、キーが同じかどうかをequalsではなく、compareToやcompareによる比較で判断すると説明し、その順序がequalsと整合していないとMapの一般的な約束を満たさないとしています。大文字と小文字を区別しない比較を渡せば、「Tokyo」と「tokyo」は同じキーになります。また、TreeMapは同期化されておらず、複数のスレッドから使い、その一つでも追加や削除をするなら、呼び出す側で同期を取る必要があります。^*4

外部に委託するときに確認しておきたい点

順序付きのデータを扱う開発を外部に頼むときは、まず標準ライブラリで足りるのか、自前の実装が要るのかを確かめます。自前で書く提案なら、その理由と平衡の方式を説明してもらいます。標準で済む処理を独自に作ると、保守の手間が後から積み上がります。

次に、テストと性能の測り方です。昇順や降順、重複の多いデータ、上限に近い件数を試験に含め、本番に近い並びのデータで性能を測っているかを見ます。比較の決まり（大文字と小文字、タイムゾーンの扱い）とロックの方針も、設計書に書いてもらいます。

最後に、データベースとの役割分担です。メモリ上に載せる件数とメモリ量、再起動時の作り直し方、データベースの索引で代わりが利かないのかを、提案の段階で確かめます。

まとめ：二分探索木で確かめておきたい3つの点

二分探索木を業務で使ううえで、確かめておきたい点は3つです。第一に、探索・挿入・削除の速さは木の高さで決まり、昇順に近いデータをそのまま入れると一列に偏ること。第二に、偏りを防ぐにはAVL木や赤黒木などの平衡木を使い、多くの場合は標準ライブラリの順序付きマップで足りること。第三に、完全一致の検索だけならハッシュ表、順序や範囲が要るなら平衡した二分探索木、ディスク上の大量データならB木系の索引と、用途で使い分けることです。この3点を押さえておけば、本番のデータで急に遅くなる事態を避けやすくなります。

よくある質問

出典

1. *1　参考：Robert Sedgewick, Kevin Wayne『Algorithms, 4th Edition』公式サイト「3.2 Binary Search Trees」（https://algs4.cs.princeton.edu/32bst/）。出典：二分探索木の定義、探索・挿入・Hibbardの削除（1962年）、ランダムな順に入れた木の平均比較回数（約2 ln N）、操作の時間が木の高さに比例するという命題、削除と挿入をくり返した木の偏りの記述を参照（2026年10月確認）
2. *2　参考：Robert Sedgewick, Kevin Wayne『Algorithms, 4th Edition』公式サイト「3.3 Balanced Search Trees」（https://algs4.cs.princeton.edu/33balanced/）。出典：赤黒木の高さが2 lg N以下であること、最悪の場合でも操作が対数時間で済むという命題を参照（2026年10月確認）
3. *3　参考：Leo J. Guibas, Robert Sedgewick「A Dichromatic Framework for Balanced Trees」（第19回 IEEE Symposium on Foundations of Computer Science、1978年）（https://sedgewick.io/wp-content/themes/sedgewick/papers/1978Dichromatic.pdf）。出典：各ノードに1ビットの色を持たせる枠組み、赤黒の条件、AVL木の平衡条件（左右の部分木の高さの差が1以内）と参考文献に挙げられたAdelson-Velskii・Landisの論文（1962年）を参照（2026年10月確認）
4. *4　参考：Oracle「TreeMap (Java SE 21 & JDK 21)」API仕様（https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/TreeMap.html）。出典：赤黒木をもとにした実装であること、containsKey・get・put・removeのlog(n)の保証、equalsとの整合、同期化されていないことの記述を参照（2026年10月確認）
5. *5　参考：C++ 規格作業草案（eel.is/c++draft）[associative.reqmts.general]（https://eel.is/c++draft/associative.reqmts.general）。出典：連想コンテナのfind・insert・lower_bound・upper_boundの計算量（対数）と、反復子がキーの順（non-descending）にたどるという性質を参照（2026年10月確認）
6. *6　参考：The Linux Kernel documentation「Red-black Trees (rbtree) in Linux」（https://docs.kernel.org/core-api/rbtree.html）。出典：赤黒木とAVL木・ハッシュ表との違い（挿入で2回・削除で3回までの回転）、カーネル内の使用例の記述を参照（2026年10月確認）
7. *7　参考：Oracle「HashMap (Java SE 21 & JDK 21)」API仕様（https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/HashMap.html）。出典：getとputが定数時間となる条件と、順序を保証しないことの記述を参照（2026年10月確認）

Tweet