アン AVLツリー 自己平衡化として定義される 任意のノードの左側のサブツリーと右側のサブツリーの高さの差は、 バランス係数 ノードの。
AVL ツリーは、1962 年の論文「情報整理のためのアルゴリズム」でこの AVL ツリーを発表した発明者、ジョージー・アデルソン・ベルスキーとエフゲニー・ランディスにちなんで名付けられました。
AVL ツリーの例:
AVLツリー
すべてのノードの左右のサブツリーの高さの差が 1 以下であるため、上のツリーは AVL です。
AVL ツリーでの操作:
AVL ツリー内のサブツリーを回転する:
AVL ツリーは、次の 4 つの方法のいずれかで回転して、バランスを保つことができます。
左回転 :
右側のサブツリーの右側のサブツリーにノードが追加されるときに、ツリーのバランスが崩れると、左に 1 回回転します。
AVL ツリーの左回転
xdxdの意味右回転 :
左側のサブツリーの左側のサブツリーにノードが追加されると、AVL ツリーのバランスが崩れる可能性があるため、右回転を 1 回実行します。
AVL ツリーの右回転
左右回転 :
左右の回転は、右回転が実行された後に最初の左回転が行われる組み合わせです。
AVL ツリーの左右回転
左右回転 :
右から左への回転は、左回転が実行された後に最初の右回転が行われる組み合わせです。
AVL ツリーの右から左への回転
AVL ツリーのアプリケーション:
- データベース内の巨大なレコードにインデックスを付けたり、データベース内で効率的に検索したりするために使用されます。
- セットや辞書を含むあらゆる種類のメモリ内コレクションには、AVL ツリーが使用されます。
- データベース アプリケーション。挿入や削除はあまり一般的ではありませんが、頻繁なデータ検索が必要です。
- 最適化された検索が必要なソフトウェア。
- 企業分野やストーリー性のあるゲームに適用されます。
AVL ツリーの利点:
- AVL ツリーは自己バランスをとることができます。
- 確かに歪んではいないですね。
- 赤黒ツリーよりも高速なルックアップを実現します。
- バイナリ ツリーなどの他のツリーと比較して、検索時間の複雑さが向上します。
- 高さは log(N) を超えることはできません。N はツリー内のノードの総数です。
AVL ツリーの欠点:
- 実装するのは難しいです。
- 一部の操作には高い定数係数があります。
- 赤黒木に比べてあまり使用されません。
- AVL ツリーは、かなり厳密なバランスのため、回転が実行されるにつれて複雑な挿入および削除操作を実行します。
- バランスをとるためにさらに処理がかかります。
関連記事：
- 二分探索ツリーの概要 – データ構造とアルゴリズムのチュートリアル
- AVL ツリーへの挿入
- AVL ツリーの削除
