1 歩ずつ動かす
命令の列 (左から順に実行する)
- insert 7
- search 6
- search 13
- insert 4
- いま着いているノード
- なし
- この命令で比べたノード
- なし
- 木の大きさ
- 6 個、高さ 3
- いま着いているノード
- 比べて通ったノード
- この命令では通らないノード
- たどった線
1 歩目 / 全 28 歩実行した命令 0 個比べた回数 0 回ノード 6 個
根が 8 の木です。ノードは 6 個、高さは 3 です。
いま動いている疑似コードの行
- 1insert(x) と search(x) は、根から始める
- 2着いたノード n と x を比べる
- 3x が n.value と同じなら、search は見つかって終わる (insert は入れない)
- 4x が小さければ左の子へ、大きければ右の子へ進む
- 5進む先が空なら、insert はそこへ x を置き、search は無いと分かって終わる
見本を変える
予想してみる
いまの歩は、比べた直後でも進んだ直後でもありません。「1 歩進む」で、ノードに着く歩まで進めましょう。
今回わかること
- 左は小さい値、右は大きい値という木の決まり
- 比べるたびに、探す範囲が左か右の一方に絞られる様子
- 値を入れる順番で木の形が変わり、比べる回数が変わること
前提
- 二分探索 (真ん中と比べて範囲を絞る)
- ノードが子を指す形 (連結リストの next と同じ)
どんな入れ物か
二分探索木は、ノードが左と右に 1 つずつ子を持つ木で、どのノードも「左にぶら下がる値は自分より小さく、右にぶら下がる値は自分より大きい」という決まりを守ります。
探すときは根から始め、比べるたびに左か右の一方だけを見ます。二分探索が真ん中で範囲を絞るのと同じ考え方を木の形で持ち続けるので、値を足しても並べ直す必要がありません。
手順と具体例
- 1根のノードと、探す値を比べる
- 2同じなら、見つかって終わる (insert は入れない)
- 3小さければ左の子へ、大きければ右の子へ進む
- 4進む先が空なら、search は「無い」で終わり、insert はそこへ新しいノードを置く
| 命令 | 比べたノード (根から) | 結果 |
|---|---|---|
| insert 7 | 8 → 3 → 6 | 新しいノードを置いた |
| search 6 | 8 → 3 → 6 | 見つかった |
| search 13 | 8 → 10 → 14 | 無い |
| insert 4 | 8 → 3 → 6 | 新しいノードを置いた |
比べる回数と計算量
| 木の形 | 比べる回数 | 計算量 |
|---|---|---|
| ほどよく広がっている | 木の高さまで (7 個なら 3 回) | O(log n) |
| ばらばらの順に入れた平均 | およそ log n 回 | O(log n) |
| 一列に偏っている | n 回 (全部と比べる) | O(n) |
n はノードの数です。比べる回数は根からそのノードまでの深さで、木の高さが上限になります。7 個がほどよく並べば高さは 3、1000 個でも 10 ほどです。小さい順に入れると木が一列になり、線形探索と同じ手間になります。偏りを直す工夫が AVL 木や赤黒木です。
使いどころ
向いているとき
- 値を足しながら、探すことも小さい順に取り出すことも両方したいとき
- 並んだ配列を保つのが、挿入のたびに後ろをずらす手間で重いとき
- 最小値や最大値、範囲の取り出しが多いとき
向いていないとき
- 同じ向きに偏った値が入るとき (偏りを直す木を使う)
- キーで直接引くだけでよいとき (ハッシュテーブルのほうが速い)
コード
疑似コード
- 1insert(x) と search(x) は、根から始める
- 2着いたノード n と x を比べる
- 3x が n.value と同じなら、search は見つかって終わる (insert は入れない)
- 4x が小さければ左の子へ、大きければ右の子へ進む
- 5進む先が空なら、insert はそこへ x を置き、search は無いと分かって終わる
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- 同じ値を入れようとすると、どうなりますか？
- このページの木では、同じ値は入れずに終わります。同じ値も持ちたいときは、ノードに個数を持たせる、右の子に入れる決まりにする、のように実装ごとに決めます。
- 木の形は、なぜ偏るのですか？
- 根になるのは、最初に入れた値です。小さい順に入れると、毎回いちばん右に付くので木が一列になります。見本の「偏った木」で確かめられます。
- 二分探索とは何が違いますか？
- 二分探索は並んだ配列の真ん中を見るので、値を足すたびに並べ直しが要ります。二分探索木は、木のまま値を足せます。そのかわり、木の形が偏ると速さが落ちます。
