JavaScriptのAVL木でバランス係数を計算する方法

AVL木（AVLツリー）は、左部分木と右部分木の高さを比較し、その差が1を超えないことを保証する自己平衡型二分探索木です。この高さの差のことをバランス係数（Balance Factor）と呼びます。

バランス係数とは

例として、次のような木を考えてみましょう。1つ目の木はバランスが取れていますが、2つ目と3つ目の木はバランスが崩れています。

2つ目の木では、ノードCの左部分木の高さが2、右部分木の高さが0であるため、差は2になります。また、3つ目の木では、ノードAの右部分木の高さが2である一方、左部分木が存在しないため高さは0となり、ここでも差は2です。AVL木では、この差（バランス係数）は1以下でなければならないと定められています。

バランス係数は次の式で求められます。

BalanceFactor = height(左部分木) − height(右部分木)

左右の部分木の高さの差が1を超えた場合、木は回転（ローテーション）と呼ばれる操作によって再びバランスを取るように調整されます。

JavaScriptでの実装例

それでは、バランス係数を計算するメソッドを定義し、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) {
         height = -1;
      } else {
         height = Math.max(this.getHeight(root.left), this.getHeight(root.right)) + 1;
      }
      return height;
   }
}
AVLTree.prototype.Node = class {
   constructor(data, left = null, right = null) {
      this.data = data;
      this.left = left;
      this.right = right;
   }
};

コードの解説

getHeightメソッドは、指定されたノードを根とする部分木の高さを再帰的に計算します。ノードがnull（空の木）の場合は-1を返し、そうでなければ左右の子の高さの最大値に1を加えた値を返します。

getBalanceFactorメソッドは、左部分木の高さから右部分木の高さを引いた値を返します。この結果が-1、0、1の範囲に収まっていれば、その木はバランスが取れていると判断できます。もし範囲外の値になった場合は、回転操作を用いて木を再平衡化する必要があります。