JavaScriptのAVLツリークラス完全実装ガイド ― 回転操作の仕組みまで徹底解説

AVL木（Adelson-Velsky・Landis木）は、1962年にG.M. Adelson-VelskyとE.M. Landisが発表した、世界初のセルフバランシング二分探索木です。通常の二分探索木はデータの挿入順序によって木が偏り、最悪の場合、検索や挿入の計算量がO(n)まで悪化してしまいます。

AVL木では、すべてのノードにおいて左右の部分木の高さの差（バランスファクター）が−1、0、1のいずれかに保たれます。挿入などでこの条件が崩れた場合には、回転（ローテーション）と呼ばれる操作によって自動的に再バランスが行われるため、常にO(log n)の計算量を維持できるのが大きな特徴です。

JavaScriptによるAVLツリークラスの完全な実装

以下が、ノードの挿入・高さの取得・バランスファクターの計算・4種類の回転操作をすべて含んだ、AVL木クラスの完全な実装です。

class AVLTree {
  constructor() {
    // ルート要素を null で初期化する
    this.root = null;
  }

  getBalanceFactor(root) {
    return this.getHeight(root.left) - this.getHeight(root.right);
  }

  getHeight(root) {
    let height = 0;
    if (root === null || typeof root === "undefined") {
      height = -1;
    } else {
      height = Math.max(this.getHeight(root.left), this.getHeight(root.right)) + 1;
    }
    return height;
  }

  insert(data) {
    const node = new this.Node(data);
    // 木が空であるかどうかをチェックする
    if (this.root === null) {
      // 最初の要素として挿入する
      this.root = node;
    } else {
      this.root = insertHelper(this, this.root, node);
    }
  }

  inOrder() {
    inOrderHelper(this.root);
  }
}

AVLTree.prototype.Node = class {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
};

function insertHelper(self, root, node) {
  if (root === null) {
    return node;
  } else if (node.data < root.data) {
    // 左へ進む！
    root.left = insertHelper(self, root.left, node);
    // バランスファクターを確認し、適切な回転を行う
    if (root.left !== null && self.getBalanceFactor(root) > 1) {
      if (node.data < root.left.data) {
        root = rotationLL(root);
      } else {
        root = rotationLR(root);
      }
    }
  } else if (node.data > root.data) {
    // 右へ進む！
    root.right = insertHelper(self, root.right, node);
    // バランスファクターを確認し、適切な回転を行う
    if (root.right !== null && self.getBalanceFactor(root) < -1) {
      if (node.data > root.right.data) {
        root = rotationRR(root);
      } else {
        root = rotationRL(root);
      }
    }
  }
  return root;
}

function inOrderHelper(root) {
  if (root !== null) {
    inOrderHelper(root.left);
    console.log(root.data);
    inOrderHelper(root.right);
  }
}

function rotationLL(node) {
  const tmp = node.left;
  node.left = tmp.right;
  tmp.right = node;
  return tmp;
}

function rotationRR(node) {
  const tmp = node.right;
  node.right = tmp.left;
  tmp.left = node;
  return tmp;
}

function rotationLR(node) {
  node.left = rotationRR(node.left);
  return rotationLL(node);
}

function rotationRL(node) {
  node.right = rotationLL(node.right);
  return rotationRR(node);
}

コードのポイント解説

1. Nodeクラス

各ノードは、値を格納する data、左の子を指す left、右の子を指す right の3つのプロパティを持ちます。Nodeクラスは AVLTree.prototype.Node として定義されており、クラス内部からは new this.Node(data) の形式で生成できます。

2. 高さとバランスファクターの計算

getHeight() メソッドは再帰的に木の高さを求めます。空のノード（null または undefined）の高さは −1 と定義され、それ以外の場合は左右の部分木の高さの最大値に1を加えた値となります。

getBalanceFactor() は「左部分木の高さ − 右部分木の高さ」を返します。この値が1より大きければ木が左に偏っており、−1より小さければ右に偏っており、回転による修正が必要です。

3. 挿入処理と4種類の回転

insertHelper() 関数は再帰的に適切な位置へノードを挿入し、その部分木の新しい根を戻り値として返します。挿入後、バランスの崩れの方向と挿入された位置に応じて、次の4種類の回転のいずれかが実行されます。

• LL回転（右回転）：左の子のさらに左側への挿入で左に偏った場合
• RR回転（左回転）：右の子のさらに右側への挿入で右に偏った場合
• LR回転：左の子の右側への挿入。まず左部分木をRR回転してから、全体をLL回転します
• RL回転：右の子の左側への挿入。まず右部分木をLL回転してから、全体をRR回転します

4. 中間順走査（In-order Traversal）

inOrder() メソッドは「左 → 根 → 右」の順で木を走査し、ソート済みの昇順データを出力します。AVL木が正しく構成されているかを確認する際に便利です。

使用例

const tree = new AVLTree();

tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(10);
tree.insert(50);

tree.inOrder();
// 出力: 10 20 30 40 50

このように、挿入のたびに木が自動的に再バランスされるため、どのような順序でデータを挿入しても木の深さはおおむね log n に保たれます。なお、本実装は挿入時の再バランスのみを扱っていますが、削除操作も同じ回転の考え方を応用することで同様に実装できます。