女性向けエンジニアスクール
3秒でわかる
各ノードが子を最大2つまで持つ木構造。探索・整列・優先度つき取り出しを、データ量の対数に比例した手数で行うための土台になります。
もう少し詳しく
どういうものか
二分木は、ひとつのノードが子を最大2つまでしか持たない木構造です。2つの子はふつう左の子と右の子として区別され、順番を入れ替えると別の木になります。ノードは値と、左右の子への参照を持つだけの小さな部品で、その部品を入れ子にしていくことで階層が生まれます。
根から葉までの段数を高さと呼びます。ノード数が n のとき、きれいに枝分かれしていれば高さはおよそ log2(n) に収まります。ノードが100万個あっても20段ほどで葉に届く、という感覚が二分木の値打ちです。
なぜ必要か
配列は添字でのアクセスは速い一方、途中への挿入や削除で後ろ全体をずらす必要があります。連結リストは挿入が軽い代わりに、目的の値を探すのに先頭から順に辿るしかありません。二分木は、左には小さい値、右には大きい値、という規則を持たせることで、探索と挿入の両方を高さぶんの比較で済ませます。
具体例
class Node:
def __init__(self, value):
self.value = value
self.left = <a href="/glossary/none" class="text-primary font-medium underline underline-offset-2 hover:text-primary-dark">None</a>
self.right = None
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
def contains(node, value):
while node is not None:
if value == node.value:
return True
node = node.left if value < node.value else node.right
return False
root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
root = insert(root, v)
print(contains(root, 40)) # True
print(contains(root, 45)) # Falseつまずきやすいところ
最大の落とし穴は木の偏りです。上のコードにソート済みの [10, 20, 30, 40, 50] を順番に入れると、右の子だけが伸びて連結リストと同じ形になり、探索は log2(n) ではなく n に比例します。実運用のデータは日付順や ID 順で並んでいることが多いので、この形はうっかり作りがちです。回避策としては、挿入のたびに高さを揃える平衡二分探索木（AVL 木や赤黒木）を使います。
もうひとつは再帰の終了条件の書き忘れです。node is None を先頭で返さないと、葉の先で属性アクセスが失敗します。
似た用語との違い
| 語 | 中身 |
|---|---|
| 二分木 | 子が最大2つ、という形だけの決まり |
| 二分探索木 | さらに「左は小、右は大」の並び順の制約がついたもの |
| ヒープ | 親が子より大きい（小さい）だけの制約。最大値の取り出しに使う |
| 完全二分木 | 葉の手前まで隙間なく埋まった形。配列で表現できる |
覚え方
分かれ道が毎回2つある迷路だと考えます。1回進むごとに残りの候補が半分になるので、段数が増えるほど効率が効いてきます。
