BST / AVL木ビジュアライザー

値を挿入して木が成長する様子を見てみましょう。AVLモードに切り替えると自動的な再平衡が見られます。

計算例 — BST / AVL木ビジュアライザー

木の高さ	7
ノード数	7
種類	BST
理想の平衡高さ	3
AVL回転	オフ

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

ソート済みの入力が最悪の入力 🖖

二分探索木の速さは形から来ており、その形は挿入順だけで決まります。このツールに 10, 20, 30, 40, 50, 60, 70 をこの順で与えると、どのキーも直前より大きいので、すべてが前のノードの右にぶら下がります。木は高さ 7 の一直線の鎖になります。木のポインタという余分なコストを背負った連結リストであり、70 を見つけるのに 3 回ではなく 7 回の比較がかかります。データに病的なところは何もありません。ただ最初から並んでいただけで、しかもデータは普通そうやって届きます。同じ 7 個の値を AVL モードに切り替えると、回転が高さを 3 に押し戻します。自己平衡木を使う理由は、これで全部です。

各ステップで半分を捨てる 🖖

二分探索木は辞書で単語を引く作業に似ています。各ノードで値を比較し、あなたの値を含みえない側の半分をまるごと捨てるのです。だからよく整った木なら、100万件の中から目的の値をおよそ20回の比較で見つけられます。ただし木の形は挿入順で決まります。すでにソート済みの値(10, 20, 30, …)を入れてみると、木が一本の傾いた線に崩れ、リストを一つずつ調べるのと同じ速さになってしまいます。

AVL木に潜む黄金比 🖖

AVLモードに切り替えて、こう問うてみましょう。ノード数を決めたとき、バランスの取れた木はどこまで高くなれるのか。その答えには黄金比が隠れています。各高さで最も節点の少ない正当なAVL木はフィボナッチ木で、二つの小さなフィボナッチ木から作られるため、その節点数はフィボナッチ数列に従います。だからこそ高さの上界には定数 1.44 が現れます。これはまさに 1 / log₂(φ) であり、φ ≈ 1.618、すなわち黄金比です。

BST と AVL 木 — 同じ値から、四つの違う木

あなたの挿入順はどの木を作るか

二分探索木の形を決めるのは、中に入っている値ではなく、値が届いた順番です。そしてその形が、使うときの費用そのものになります。探索も挿入も削除も根から葉まで下りていくので、高さがそのまま代価です。どの型にいるかは二つの問いで決まります。値はすでに並んだ状態で届いたか、そして何かがそれを回して釣り合いに戻しているか。

釣り合った BST — 到着順がうまく噛み合った h = 3 = ⌈log₂(n + 1)⌉

縮退した BST — 並んだ入力、釣り合いを直すものがない h = n = 7 ⇒ O(n)

AVL の釣り合い直し — 回転は局所的で安い |hL − hR| > 1 → ↻, h = 3

並んだ入力を AVL へ — 回転が存在する理由そのもの ↻ × 4 ⇒ h = 3 < 7

釣り合った BST — 到着順がうまく噛み合った

わかっていること: 純粋な BST モード、回転なし。値は中央から順に届くので、新しい鍵はまだ浅い部分木に落ち、どちらの側も相手より先に伸びません。

かかる費用: h = 3 = ⌈log₂(n + 1)⌉

計算例: 50, 30, 70, 20, 40, 60, 80 → 根は 50、節点 7 個、高さ 3 — ちょうど理想の ⌈log₂(7+1)⌉ = 3 なので、最も深い探索でも比較は 3 回です

この型を開く: 平衡

釣り合った BST — 到着順がうまく噛み合った. 三段に七つの節点、どの葉も根から同じ距離 — これ以上は望めません。純粋な BST モード、回転なし。値は中央から順に届くので、新しい鍵はまだ浅い部分木に落ち、どちらの側も相手より先に伸びません。 — 三段に七つの節点、どの葉も根から同じ距離 — これ以上は望めません。

縮退した BST — 並んだ入力、釣り合いを直すものがない

わかっていること: また純粋な BST モードですが、値は昇順で届きます。どれもすでに入っている値より大きいので、毎回そのまま右へ進みます。

かかる費用: h = n = 7 ⇒ O(n)

計算例: 10, 20, 30, 40, 50, 60, 70 → 根は 10、節点 7 個、高さは 3 ではなく 7。70 を見つけるのに比較 7 回かかり、この道具は結果を連結リストと呼びます

この型を開く: 退化

縮退した BST — 並んだ入力、釣り合いを直すものがない. どの節点も子は一つ：探索は七段すべてを歩き、配列を順に見るのと変わりません。また純粋な BST モードですが、値は昇順で届きます。どれもすでに入っている値より大きいので、毎回そのまま右へ進みます。 — どの節点も子は一つ：探索は七段すべてを歩き、配列を順に見るのと変わりません。

AVL の釣り合い直し — 回転は局所的で安い

わかっていること: AVL モード。挿入ごとに根へ向かって戻り、二つの部分木の高さの差が 1 を超えた最初の節点を回します。節点の横の印は、左の高さから右の高さを引いた値です。

かかる費用: |hL − hR| > 1 → ↻, h = 3

計算例: AVL モードで 30, 20, 10, 25, 35, 40 → 10 を入れると節点 30 が +2 に傾き、右回転が 20 をその位置へ持ち上げます。後から入る 40 はある節点を −2 に傾け、左回転が直します。回転 2 回、節点 6 個、高さ 3。

回転は画面では大がかりに見えますが、中身はほとんど何もしていません。矢印を三本つなぎ替え、高さを二つ計算し直すだけ。かかる時間は一定で、部分木の外には一切触れません。順序を壊すこともありません。回転が動かすのは部分木まるごとで、値どうしが追い越すことはないので、通りがけ順の並びは前後で完全に同じです。だからこそ AVL は挿入ごとに検査する余裕があります。しかも直しは挿入一回につき一度で必ず足ります。回転一回、傾きがつづら折りのときはその二つ組を一度 — それで上にあるすべての先祖の高さは元に戻ります。

この型を開く: AVL再平衡

AVL の釣り合い直し — 回転は局所的で安い. 輪で囲んだ節点は回転で持ち上げられたもの。どの印も ±1 の中に戻っています。 AVL モード。挿入ごとに根へ向かって戻り、二つの部分木の高さの差が 1 を超えた最初の節点を回します。節点の横の印は、左の高さから右の高さを引いた値です。 — 輪で囲んだ節点は回転で持ち上げられたもの。どの印も ±1 の中に戻っています。

並んだ入力を AVL へ — 回転が存在する理由そのもの

わかっていること: AVL モードに、二つ前の型で鎖を作ったのとまったく同じ値を流し込みます。挿入はいつも右端に落ち、どこかの先祖の釣り合いを −2 に押すので、ほぼ毎回直しが起きます。

かかる費用: ↻ × 4 ⇒ h = 3 < 7

計算例: AVL モードで 10, 20, 30, 40, 50, 60, 70 → 左回転 4 回、根は 10 ではなく 40 になります。高さは 7 ではなく 3 — 同じ入力、同じ七つの節点で、深さは半分未満です。

二番目の型と見比べてください。値も順番も同じで、違いは釣り合いを見張るものがいたかどうかだけです。挿入七回に対する回転四回が、保証の代金でした。矢印の書き換えという一定の割増しを払う代わりに、入力がどれほど意地悪でも高さはおよそ 1.44 log₂ n を超えません。AVL が一度もしなかったことにも注目してください。データが並んでいると気づくことです。全体の傾向を見抜く仕組みはどこにもありません。各節点が自分の二つの部分木の高さを比べるだけで、その純粋に局所的な信号があれば、最悪の形はそもそも生まれずに済むのです。

この型を開く: 並んだ入力をAVLへ

並んだ入力を AVL へ — 回転が存在する理由そのもの. 型 2 と同じ並んだ値を、届くたびに回して三段へ戻したもの。 AVL モードに、二つ前の型で鎖を作ったのとまったく同じ値を流し込みます。挿入はいつも右端に落ち、どこかの先祖の釣り合いを −2 に押すので、ほぼ毎回直しが起きます。 — 型 2 と同じ並んだ値を、届くたびに回して三段へ戻したもの。

参考文献 (1)

Insight block 3 — the Fibonacci tree that sets the AVL height bound: D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, §6.2.3. Addison-Wesley, 1998. ISBN 978-0-201-89685-5 — the sparsest legal AVL tree of each height, and the logφ bound that follows.

全プロセスの詳細解説

高さ七の木（七つのノードを持つ） 5 ステップ
7つのノードと高さ7の木。平衡木であれば高さは3になるはずである。入力が何を引き起こしたのか、そして大規模化した際にそれがどれほどのコストになるかを解き明かせ。
1. デフォルトのキーは 10, 20, 30, … とすでにソートされている。挿入ルールに従うと、新しいキーは常に木の中のどの要素よりも大きいため、毎回右の子へと挿入される。
  
  $insert 10, 20, 30, 40, 50, 60, 70 in order$
2. その結果、分岐はまったく生じない。各ノードは子を1つしか持たないため、この構造はたまたま木として描画された連結リストにすぎず、高さはノード数と等しくなる。
  
  $each new key > every key present ⟹ always the right child$
3. 7つのノードに対する可能な限り最善の高さは3である。高さ h の木が保持できるノード数は最大で 2ʰ − 1 個であり、2³ − 1 = 7 と一致するからである。平衡な状態が可能であったにもかかわらず、この入力は最悪のケースを実現している。
  
  $h = n = 7 (a linked list wearing a tree’s name)$
4. 探索は根から辿るため、そのコストは高さそのものとなる。ここでは理想的な3回に対して7回の比較を要する。
  
  $h_{m i n} = ⌈ lo g_{2} (n + 1)⌉ = ⌈ lo g_{2} 8 ⌉ = 3$
5. 本質はこの比率にあり、規模が大きくなるほど影響は拡大する。ノード数が100万の場合、平衡木の高さは20であるのに対し、ソート済み入力での高さは100万となる。
  
  $n = 1 0^{6} : h_{m i n} = 20 but sorted input gives h = 1 0^{6}$
解答

ツールは、高さ 7（ノード数 7、理想値 3）と出力する。教訓は、O(log n) は決して二分探索木自体の性質ではない ということである。それは挿入順序の性質であり、プログラマーが与える最も自然な順序であるソート済みデータこそが、まさにそれを破壊する。これこそが AVL 木や赤黒木が存在する全体の理由である。これらは挿入ごとに1、2回の回転コストを支払うことで、その保証を無条件のものにする。モードを AVL に切り替えれば、同じ7つのキーが高さ 3 に収まる様子を確認できる。

$O (lo g n) is a claim about the INPUT ORDER, not about the structure$

42Math チーム · 更新 2026-07-28

公表された資料と照合しています。訂正のご指摘を歓迎します。編集方針 · 訂正

コンピューティングのレッスン一覧 →

例題

平衡 - バランスの取れたBST：ノード7個、高さ3
退化 - 並んだ入力：BSTは高さ7まで伸びる
AVL再平衡 - AVLは回転2回で自動的に釣り合う
並んだ入力をAVLへ - 同じ並んだ値をAVLへ：回転4回で高さ3