二分探索木

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

「左の子は自分より小さく、右の子は大きい」というルールだけの木を作る。この約束のおかげで、比較するたびに候補が半分に減って、log(件数)回で目当てを見つけられる。ただし木の形は入れた順番で決まってしまい、昇順に入れると一本の鎖に崩れる。この弱点が、次の B-Tree が必要な理由になる。

この章で作るもの

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

この章の肝は3つ。

ルールは1つだけ:「左の子孫は自分より小さく、右の子孫は大きい」
速さの正体は高さ。1回の比較で候補が半分になるから、高さ ≈ log2(件数) で済む
木の形は挿入された順序だけで決まる。昇順に入れると一本鎖に崩壊する—— これが平衡木(B-Tree を含む)が存在する理由

前提: 木の用語

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

ノード: 木の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
}

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

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

// Contains は key の有無を返す。大小比較して左右どちらかへ降りるだけ。
// ループ回数は最大で木の高さ+1。
func (tr *Tree) Contains(key int) bool {
	for n := tr.root; n != nil; {
		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

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

テストでもこの崩壊を固定してある: ランダム1023件なら高さ30以下、 昇順100件なら高さちょうど99。

出口: 崩壊にどう対処するか

「挿入順に関係なく高さを log に保ちたい」= 平衡を保ちたい。やり方は大きく3系統ある。

系統	発想	代表
回転	偏りを検知したらノードをつなぎ替えて回す	AVL木、赤黒木(各言語の Map の中身)
太らせて割る	ノードにキーを複数詰め、溢れたら分割する	B-Tree(次章)
確率	ランダムな高さの飛び道具で期待値的に平衡	skip list(Redis の sorted set)

B-Tree は「平衡の実現方法のひとつ」であり、さらにディスクの事情 (ディスクとページで扱う)に合わせてノードを太らせた木、と位置づけられる。この2つを前提に B-Tree の章へ進むのがおすすめ。

簡略化したこと

削除は未実装: 子が2つあるノードの削除は「右部分木の最小値と入れ替える」一手間が要る
平衡化はしない: 崩壊すること自体がこの章の主題。回転(AVL/赤黒木)は扱わない
キーは整数のみ、値も持たない(集合として使う)

参考資料

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

二分探索木 ​

この章で作るもの ​

前提: 木の用語 ​

なぜ速いのか: 1回の比較で候補が半分になる ​

実装 ​

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

崩壊: 木の形は挿入順で決まる ​

出口: 崩壊にどう対処するか ​

簡略化したこと ​

参考資料 ​