データ構造の可視化
二分探索木・AVL 木・赤黒木・B 木・二分ヒープへの挿入・削除・探索を、回転や分割を含めて 1 コマずつ見せます。同じキーを入れたときの木の高さや比較の回数も比べられます。
どのノードでも左右の部分木の高さの差を 1 以内に保ちます。崩れたら回転で直します。
- 細い輪: たどったところ
- 太い輪: 見つけた・入れたところ
- 破線の輪: 回転・分割・併合・入れ替えなどで動くところ
- 赤い破線: 取り除くところ
- 右上の数: 偏り（左の高さ − 右の高さ）
- キーの数
- 10
- 高さ
- 4
入れた順: 85, 98, 99, 47, 42, 60, 64, 29, 79, 3
同じキーで比べる
今のキーを、上の「入れた順」で空の状態から挿入したときの比較です。探索は、入っているキーを 1 つずつ探したときの比較の回数です。
| 構造 | 高さ | 挿入の比較 | 構造を直した回数 | 探索の比較（平均） | 探索の比較（最大） |
|---|---|---|---|---|---|
| 二分探索木 | 5 | 22 | — | 3.2 | 5 |
| AVL 木 | 4 | 25 | 回転 6 | 3.0 | 4 |
| 赤黒木 | 4 | 26 | 回転 7・塗り替え 21 | 2.9 | 4 |
| B 木（t = 2） | 3 | 23 | 分割 4 | 3.0 | 5 |
| B 木（t = 3） | 2 | 20 | 分割 2 | 3.1 | 5 |
| 二分ヒープ | 4 | 16 | 入れ替え 11 | 5.5 | 10 |
B 木はノードの中のキーを左から順に比べて数えています。ヒープは大小の並びが部分的なので、探索では配列を先頭から順に調べます。
使い方
- 上のボタンでデータ構造を選びます。今入っているキーは、選んだ構造に入れた順で入れ直します。
- キー（0〜999）を入力して「挿入」「削除」「探索」を押すと、その手順が 1 コマずつ再生されます。入力欄で Enter を押しても挿入できます。ヒープでは「最小値を取り出す」も使えます。
- 「◀」「▶」で 1 コマずつ戻る / 進むことができます。キーボードでは ← → で 1 コマ、Home / End で最初 / 最後に移ります（入力欄にカーソルがないとき）。
- 「まとめて入れ直す」で 15 個のキーを入れた状態から始められます。「昇順」を二分探索木と AVL 木で比べると、バランスを取る意味がよくわかります。
- 下の表では、同じキーを同じ順に入れたときの高さと比較の回数を、すべての構造で比べられます。
バランスを取る木
二分探索木は、左の部分木のキーはすべて小さく、右の部分木のキーはすべて大きい、という規則でキーを並べます。根から比べながら下りるだけで探せるので、高さが h なら探索は h 回の比較で済みます。ただし入れる順によって形が決まり、昇順に入れると一直線になって、探索は配列を端から調べるのと変わらなくなります。
AVL 木は、どのノードでも左右の部分木の高さの差（偏り）が 1 以内という規則を保ちます。挿入や削除で偏りが 2 になったら、回転で部分木の形を組み替えます。回転は大小の順を変えずに、片方の子を親の位置へ上げる操作です。赤黒木は、ノードを赤と黒に塗り分け、赤いノードが続かないことと、根からどの葉までも黒いノードの数が同じことを保ちます。AVL 木より規則がゆるいので回転が少なく、多くの言語の標準ライブラリの連想配列（C++ の std::map、Java の TreeMap など）に使われています。どちらも高さはキーの数 n に対して log n に比例する大きさに収まります。
B 木とヒープ
B 木は 1 つのノードに複数のキーを持たせ、ノードが満杯になったら真ん中のキーを親へ上げて 2 つに分けます。木は根の側にしか伸びないので、すべての葉が同じ深さにそろいます。ディスクのように 1 回の読み込みが遅い記憶装置では、1 ノードを 1 ブロックにすると読み込む回数が木の高さで済むため、データベースやファイルシステムの索引に使われています。このアプリでは、下りながら満杯のノードを先に分けておく（削除では、少ないノードに兄弟から借りるかまとめておく）教科書の方法で動かしています。
二分ヒープは、親が子より小さい（最小ヒープ）という規則だけを保つ完全二分木です。左から詰めて並べるので、i 番目の子を 2i + 1 番目と 2i + 2 番目とする配列で表せます。最小値はいつも根にあり、取り出しと挿入は高さの分だけ入れ替えれば済むので、優先度付きキューやヒープソートに使われます。その代わり、任意のキーを探すには全体を調べる必要があります。