JavaScriptで学ぶAVL木：自己平衡二分探索木の基礎と実装

AVL木とは

AVL木（発明者であるAdelson-VelskyとLandisの名前にちなんで命名されました）は、自己平衡二分探索木の一種です。自己平衡木とは、部分木の内部で「回転（ローテーション）」と呼ばれる操作を行うことで、木の左右のバランスを自動的に保つデータ構造のことです。

なぜ木のバランスが重要なのか

二分探索木にデータを挿入し続けると、値の並び方によっては木が片側に偏ってしまうことがあります。このようなケースでAVL木は特に有効です。

バランスの取れた木では、探索・挿入・削除の時間計算量がO(log n)に保たれます。一方、完全に偏った木（実質的に連結リストと同じ状態）では、計算量がO(n)にまで悪化してしまいます。AVL木は常にバランスを維持するため、最悪の場合でもO(log n)の性能を保証できる点が大きな強みです。

平衡係数（バランスファクター）

AVL木では、各ノードについて「左の部分木の高さ − 右の部分木の高さ」で表される平衡係数を計算し、その値が常に -1、0、1 のいずれかに収まるように管理します。挿入や削除によってこの範囲を超えた場合には、回転操作によってバランスを復元します。

回転操作の種類

AVL木のバランス復元には、主に次の4種類の回転が使われます。

• 右回転（Right Rotation）：木が左側に偏った場合に適用
• 左回転（Left Rotation）：木が右側に偏った場合に適用
• 左-右回転（Left-Right Rotation）：左の子の右側に偏った場合に、左回転と右回転を組み合わせて適用
• 右-左回転（Right-Left Rotation）：右の子の左側に偏った場合に、右回転と左回転を組み合わせて適用

JavaScriptでの実装のポイント

JavaScriptでAVL木を実装する際は、各ノードに高さ情報を持たせ、挿入・削除のたびに再帰的に平衡係数を更新するのが一般的です。以下はノードの基本構造の例です。

class AVLNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1; // 新しいノードの高さは1から始まる
  }
}

まとめ

AVL木は、挿入や削除が頻繁に行われる状況でも、常にバランスの取れた状態を維持できる強力なデータ構造です。探索性能をO(log n)に保ちたい場合や、偏ったデータが挿入される可能性がある場合に、ぜひ活用を検討してみてください。