在Javascript AVL树中计算平衡因子

AVL树检查左子树和右子树的高度,并确保差异不超过1。该差异称为“平衡因子”。

例如,在以下树中,第一棵树是平衡的,接下来的两棵树是不平衡的-

在第二棵树中,C的左子树的高度为2,而右边子树的高度为0,所以差为2。在第三棵树中,A的右子树的高度为2,而左子树的高度为2,所以它为0。 ,并且相差再次为2。AVL树允许差异(平衡因子)仅为1。

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

如果左右子树的高度差大于1,则使用某些旋转技术来平衡树。

让我们定义此方法并初始化类- 

示例

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;
   }
};