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