【えーぶいえるき】
AVL木 とは？
最終更新:
💡 左右の高さの差を、各ノードで1以内に保つ
各ノードの左右の部分木の高さの差を1以内に保つ、自己平衡二分探索木。値の大小の並び、回転による調整、計算量と使い分けを解説します。
📌 このページのポイント
- 値の大小で左右に分ける二分探索木の一種
- 各ノードで、左右の部分木の高さの差を1以内に保つ
- 挿入・削除で崩れた場合、回転などで条件を回復する
- 探索・挿入・削除は、要素数nに対し最悪O(log n)
ひよこ 二分探索木は、なぜ偏る？
ペンギン先生 値の大小で左右へ分ける木でも、並べ方によって片側に長く伸びることがあるよ。たとえば30、20、10の順に入れると、左へ続く形になる。探索で多くのノードをたどる原因になるんだ。
ひよこ AVL木では、どう防ぐ？
ペンギン先生 各ノードで、左と右の部分木の高さの差を1以内に保つよ。一番上だけでなく、木の中のすべてのノードが対象なんだ。挿入や削除で条件が崩れたら、回転などで並びを調整する。
ひよこ 回転で、値の順番が変わらない？
ペンギン先生 二分探索木の大小関係を保って、つながりを組み替えるよ。さっきの30→20→10なら、20を上に、左に10、右に30とする右回転で整えられる。値を小さい順にたどると、前も後も10、20、30なんだ。
ひよこ どのくらい速くなる？
ペンギン先生 木の高さを要素数nに対してO(log n)に抑えられるので、探索・挿入・削除も最悪O(log n)だよ。これは要素数が増えるときの計算量の話で、何ミリ秒かを示す値ではない。比較の処理や実装も実行時間に関係するんだ。
ひよこ 赤黒木より、必ず速い？
ペンギン先生 平衡の条件や調整方法が違うので、一律には言えないよ。探索と更新の割合、データ、メモリ、実装によって変わる。AVL木は高さを厳密に制御する方法の一つで、どんな用途でも最速だったり、常に最小の高さになったりするという意味ではないんだ。
もっと詳しく知りたい人へ
高さの差が1以内なら、全ノードが同じ深さ？
同じ深さである必要はありません。各ノードの左右の部分木の高さの差が0または1なら条件を満たします。完全な二分木や、すべての葉の深さが同じ木と同義ではありません。
同じ値を複数入れる場合も、必ず左が小さく右が大きい？
図と基本の説明は、重複しない値の例です。同じ値を許すコレクションでは、個数を持つなどの扱いを実装で決めます。大小関係と重複の方針を確認し、どの実装でも同じ規則だと決め付けないようにします。
まとめ：ざっくりこれだけ覚えればOK！
「AVL木」って出てきたら「左右の高さの差を小さく保ち、偏りを抑える二分探索木」と思えばだいたいOK！
📖 おまけ：英語の意味
「AVL Tree」 ＝ 発明者の名前に由来する平衡二分探索木
💬 Adelson-VelskiiとLandisの名前に由来します。NISTの辞典は、1962年の論文を原典として挙げています。