木と二分探索木

二分探索木はどこで崩れるのか

二分探索木は、入れる順で形が決まり、小さい順に入れると 1 本の線に片寄って、探す手間が件数と同じ O(n) まで落ちます。整った形のまま保つ仕組みは、普通の二分探索木には入っていません。

入れる順で、高さが 10 にも 1,000 にもなる

同じ 0 から 999 までの 1,000 個の値を、3 通りの順で入れて比べます。

1. 真ん中から入れる。全体の真ん中の値を先に入れ、左右の半分でも同じことをくり返す
2. 混ぜて入れる。乱数の代わりに決まった式で混ぜた順に入れる (誰が動かしても同じになる)
3. 小さい順に入れる。0、1、2 … 999 の順

出力は左から、件数、入れる順、木の高さ、平均です。平均は、木にある値を 1 つずつ全部探したときの、見た節の数の平均です (各節が何段目にあるかの平均と同じです)。

100 真ん中から 7 5.8
100 混ぜて 16 8.91
100 小さい順 100 50.5
1000 真ん中から 10 8.987
1000 混ぜて 22 12.336
1000 小さい順 1000 500.5

真ん中から入れた 1,000 件の木は高さ 10 で、2-1 の二分探索の最悪 10 回と同じです。100 件の高さ 7、平均 5.8 も、2-1 の数当ての最悪 7 回、平均 5.8 回と重なります。真ん中から入れた木は、二分探索と同じく、どの段でも候補を真ん中で半分に分ける形になるからです。

混ぜて入れた木は、高さ 22、平均 12.336 でした。真ん中からより高いものの、まだ速く探せます。

小さい順に入れた木は、高さが件数と同じ 1,000 になりました。新しい値がいつも前の値の右の子になり、枝分かれのない 1 本の線になったからです。999 を探すと 1,000 個の節を見ます。平均の 500.5 も、端から比べる線形探索と変わりません。

図で入れる順を切り替えると、小さい順のときだけ右へ一直線に伸びます。通りがけ順の並びは変わらないので、出てくる値だけでは片寄りに気づけません。

小さい順に入れる場面は、思ったより多い

会員番号や注文番号、日時のように増えていく値を鍵 (探すときの目印の値) にして順に入れると、小さい順に入れたのと同じになります。外から来る値の順に入れる作りなら、相手が並べた順で送るだけで、こちらの木は片寄ります。

並べた配列と、入れる手間を比べる

1,000 個の値を入れる手間を比べます。木では入れる場所を探して見た節の数、並べた配列では bisect で位置を探したあと後ろへずらした値の数を、それぞれ合計します。

混ぜて
 木で見た節 11336
 配列でずらす 246632
小さい順
 木で見た節 499500
 配列でずらす 0

混ぜた順で入れると、木で見た節は合計 11336、配列でずらした値は合計 246632 でした。木のほうが、20 分の 1 より少ない手間で済んでいます。

小さい順で入れると逆転します。木は 1 本の線になり、入れるたびに端まで降りるので、見た節は合計 499500 (0 から 999 までを足した数) に膨らみました。配列は新しい値がいつも最後に入るので、ずらす値は 0 です。

普通の二分探索木が得なのは、入れる順がばらけているときだけです。

片寄りを直す木がある

片寄りを防ぐには、入れ消しのたびに木の形を少し組み替えて高さを抑えます。この組み替えを回転と呼び、こうした木を平衡二分探索木と呼びます。代表は AVL 木と赤黒木 (あかくろぎ) です。

Linux カーネルの公式文書は、赤黒木を「自分で釣り合いを取る二分探索木」と説明し、入れるときは最大 2 回、消すときは最大 3 回の回転で釣り合いが取れると書いています。回転の中身はこの回では扱いません。入れる順に関係なく高さを抑える仕組みがある、と知っておけば十分です。