二分探索木

実装: data-structures/bst/ / 実行: go test ./data-structures/bst/

「左の子は自分より小さく、右の子は大きい」というルールだけの木を作る。比較のたびに片側を丸ごと捨てられるので速い。ただし形を整える処理がどこにも無いので、形は入れた順だけで決まる。1万件を昇順に入れると高さは9999、1回引くのに平均5000.5回比べることになる。連番のIDも時刻順のログも、素直に流し込むといちばん悪い形になる。

この章で作るもの

B-Tree の前提になる、二分探索木(binary search tree, BST)を実装する。

順に見ていく。

1回の比較で片側を丸ごと捨てる: ルールが保たれている限り、降りる先は片方だけになる
速さの正体は高さ: 比較の回数は高さで決まる。件数ではない
形は入れた順だけで決まる: 整える処理がどこにも無いので、昇順で1本の鎖に落ちる

前提: 木の用語

この教科書で「木」と言ったら、上下逆さまに描く家系図のような構造のこと。

ノード: 木の1つの要素。この章では整数のキーを1つ持つ
根(root): 一番上のノード。すべての操作はここから始まる
子 / 親: ノードから下にぶら下がるのが子。二分木では子は最大2つ(左と右)
葉(leaf): 子を持たないノード
高さ: 根から一番遠い葉までの段数。根だけなら高さ0

二分探索木の例。どのノードでも「左の子孫 < 自分 < 右の子孫」が成り立っている

① 1回の比較で片側を丸ごと捨てる

上の木から 60 を探すことを考える。根の 50 と比べて「60 は大きい」と分かった瞬間、 左半分の木(20 以下の世界)は見なくてよいと確定する。次に 80 と比べて小さければ、 80 の右側も捨てられる。

60 の探索経路。比較のたびに薄い部分がまるごと候補から消える

「半分ずつ捨てる」を繰り返すと、候補は全件 → 1/2 → 1/4 → … と減っていく。 n 件から1件に絞るまでの回数が log2(n) で、これが「対数時間」の正体:

件数	比較回数(バランス時)
1,000	約10回
100万	約20回
10億	約30回

件数が1000倍になっても比較は10回しか増えない。この鈍さが log の価値。

② 速さの正体は高さ

ノードとルールをそのままコードにする。

// node は1つのキーと左右の子を持つ。
type node struct {
	key         int
	left, right *node
}

// Tree は二分探索木。平衡化はしない(それがこの章の主題)。
type Tree struct {
	root *node

	// compares は Contains で鍵を見比べた回数の累計。
	// 「1回の比較で候補が半分になる」が本当かは、ここを数えれば分かる。
	compares int
}

// New は空の木を返す。
func New() *Tree {
	return &Tree{}
}

検索は「比較して左右どちらかへ降りる」だけ:

// Contains は key の有無を返す。大小比較して左右どちらかへ降りるだけ。
// ループ回数は最大で木の高さ+1。
func (tr *Tree) Contains(key int) bool {
	for n := tr.root; n != nil; {
		tr.compares++
		switch {
		case key == n.key:
			return true
		case key < n.key:
			n = n.left
		default:
			n = n.right
		}
	}
	return false
}

挿入は検索と同じ道を降りて、行き止まりに新ノードを置く:

// Insert は key を挿入する(既存なら何もしない)。
// 検索と同じ道を降りて、行き止まり(nil)の場所に新しいノードを置く。
// どこに置かれるかは「今までに入った順序」だけで決まる。ここに崩れる種がある。
func (tr *Tree) Insert(key int) {
	pos := &tr.root
	for *pos != nil {
		n := *pos
		switch {
		case key == n.key:
			return // 重複は無視
		case key < n.key:
			pos = &n.left
		default:
			pos = &n.right
		}
	}
	*pos = &node{key: key}
}

コードの読みどころ: ポインタへのポインタ

pos := &tr.root の pos は「ノードへのポインタ」ではなく「ノードへのポインタが入っている場所を指すポインタ」(**node 相当)。これで「根に入れる」「左の子に入れる」「右の子に入れる」の3パターンが、最後の *pos = &node{key: key} の1行に統一される。

tr.root ──▶ [50]
             ├ left  ──▶ [20]
             └ right ──▶ nil   ← pos はこの「nil が入っている場所」を指している
                               *pos = 新ノード で、ここに直接書き込む

pos を使わずに書くと「親を覚えておいて、左右どちらの子だったかで分岐して代入」という重複コードになる。行き先の場所そのものを持ち歩くのがこのイディオム。

③ 形は入れた順だけで決まる

ここからがこの章の本題。Insert は来たキーを規則通りの場所に置くだけで、 木の形を整える処理はどこにもない。つまり形は挿入順まかせ。

昇順(1, 2, 3, …)で挿入するとどうなるか。新しいキーは常に既存のどのキーよりも大きいので、毎回いちばん右の行き止まりに置かれる:

1〜5 を昇順で挿入した結果。右にしか伸びない一本鎖 = 実質ただの連結リスト

高さは n-1 になり、検索も挿入も毎回全ノードをたどる O(n) に落ちる。「半分ずつ捨てる」が「1個ずつ捨てる」になってしまうから。

試してみる: 「昇順で1件挿入」を連打すると右一直線に伸びて、高さが件数とともに 1ずつ増えていく。リセットして「ランダムに1件挿入」なら、高さは理想値の近くに留まる。

デモ二分探索木の挿入

件数 0 / 高さ -1

まだ空です。挿入してみてください。

崩れ方は数字で言える。比較した回数を数えられるようにしておく:


// Compares は Contains で鍵を見比べた回数の累計を返す。
func (tr *Tree) Compares() int { return tr.compares }

// ResetStats は数え直す。
func (tr *Tree) ResetStats() { tr.compares = 0 }

同じ件数を昇順に入れた場合とばらばらに入れた場合で、高さと「1回引くのに比べる回数」を測るとこうなった:

件数	昇順:高さ	昇順:比較	ばらばら:高さ	ばらばら:比較
100	99	50.5	13	7.2
1,000	999	500.5	19	14.1
10,000	9999	5000.5	30	18.0

昇順の列は、高さが 件数 - 1、比較回数が 件数 ÷ 2 にぴたりと乗っている。半分ずつ捨てるが、1個ずつ捨てるに落ちている。ばらばらに入れた側は、件数を100倍にしても比較が 7.2 → 18.0 にしか増えない。

テストで、昇順の高さがちょうど 件数 - 1 になること、ばらばらなら件数の対数の3倍以内に収まることを、両方固定した。

そして厄介なのは、昇順に入るのは珍しい状況ではないことになる。連番の ID、時刻順のログ、ソート済みファイルからの読み込み。素直に流し込むと、いちばん悪い形になる。

崩れたときの出口

「入れた順に関係なく高さを対数に保ちたい」、つまり平衡を保ちたい。やり方は大きく3系統ある。

系統	発想	代表
回転	偏りを見つけたらノードを繋ぎ替えて回す	AVL木、赤黒木(各言語の Map の中身)
太らせて割る	ノードにキーを複数詰め、溢れたら割る	B-Tree(次章)
確率	高さをコイン投げで決めて、偏りを持ち込まない	スキップリスト

3つめが面白いところで、スキップリストは崩れを直さない。高さをコイン投げで決めるので、キーの並びが形に影響しない。同じ4000件の昇順を両方に入れると、二分探索木の高さが 3999 なのに対してスキップリストは 13 になる。直すか、持ち込まないかの違いになる。

設計の観点

不変条件を1つに絞る: 「左は小さい、右は大きい」だけで、探索も挿入も同じ道になる
速さの根拠を言えるようにする: 「対数」は形が整っている前提つきの主張になる
前提が崩れた姿を測る: 悪い順で入れたときの数字を知らないと、使ってよいか判断できない
悪い入力は普通に来る: 連番も時刻順もソート済みも、どれもありふれている
直すか、持ち込まないか: 偏りを検知して直す道と、偏りようのない決め方にする道がある
整えるのは無料ではない: 回転も分割も手間なので、何もしない選択が正しい場面もある

対照と実例

	平衡	昇順で入れると	実装	特徴
二分探索木	保たない	高さ = 件数 - 1	最も易しい	この章。崩れることが主題
AVL木	回転(厳しめ)	対数	難しい	探索が速い
赤黒木	回転(ゆるめ)	対数	難しい	挿入削除が速い。各言語の Map
B-Tree	太らせて割る	対数	中くらい	ディスク向き
スキップリスト	コイン投げ	対数(実質)	易しい	回転が要らない

裏どり:

各言語の順序つき Map: C++ の std::map、Java の TreeMap はどれも赤黒木。素の二分探索木が標準ライブラリに入らないのは、この章で測った崩れ方があるから
ばらばらに入れたときの高さ: 期待値は 2 log₂(件数) 前後になることが知られている。実測の 13 / 19 / 30 も、この線に乗っている
Treap / ランダム化 BST: 挿入時に乱数で優先度を振り、それに従って回す。スキップリストと同じ「持ち込まない」側の発想を、木でやる形になる
ディスクの事情: B-Tree がノードを太らせるのは、平衡のためだけでなくページ単位の読み書きに合わせるためだ
削除の難しさ: 子が2つあるノードを消すには、右の部分木の最小値と入れ替える一手間が要る。平衡木ではさらに回転が続く

簡略化したこと

削除なし: 子が2つあるノードを消す手順は入れていない
平衡化なし: 崩れること自体がこの章の主題になる。回転は扱わない
キーは整数のみ: 値を持たないので、集合としてしか使えない
並行安全でない: 読み書きを同時にする話は扱わない
数えるのは Contains だけ: Insert がたどる手数は数えていない

参考資料

CLRS『アルゴリズムイントロダクション』12章(BST)・13章(赤黒木)
VisuAlgo: BST — 挿入・削除・回転をアニメーションで試せる
実装: data-structures/bst

二分探索木 ​

この章で作るもの ​

前提: 木の用語 ​

① 1回の比較で片側を丸ごと捨てる ​

② 速さの正体は高さ ​

コードの読みどころ: ポインタへのポインタ ​

③ 形は入れた順だけで決まる ​

崩れたときの出口 ​

設計の観点 ​

対照と実例 ​

簡略化したこと ​

参考資料 ​