Javascript AVL 트리에서 균형 계수 계산

AVL 트리는 왼쪽 및 오른쪽 하위 트리의 높이를 확인하고 차이가 1 이하인지 확인합니다. 이 차이를 균형 요소라고 합니다.>

예를 들어, 다음 트리에서 첫 번째 트리는 균형을 이루고 다음 두 트리는 균형이 맞지 않습니다 -

두 번째 트리에서 C의 왼쪽 서브트리는 높이가 2이고 오른쪽 서브트리는 높이가 0이므로 차이는 2입니다. 세 번째 트리에서 A의 오른쪽 서브트리는 높이가 2이고 왼쪽이 누락되어 있으므로 0입니다. , 그리고 그 차이는 다시 2입니다. AVL 트리는 차이(균형 계수)가 1일 수 있도록 허용합니다.

BalanceFactor = height(left-sutree) − height(right-sutree)

왼쪽 및 오른쪽 하위 트리의 높이 차이가 1보다 크면 일부 회전 기술을 사용하여 트리가 균형을 이룹니다.

이 메소드를 정의하고 클래스도 초기화합시다 -

예시

class AVLTree {
   constructor() {
      // Initialize a root element to 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;
   }
};