计算 Javascript AVL 树中的平衡因子
javascriptweb developmentfront end technology
AVL 树检查左子树和右子树的高度并确保差异不超过 1。此差异称为 平衡因子
例如，在以下树中，第一棵树是平衡的，而接下来的两棵树不平衡 −
在第二棵树中，C 的左子树高度为 2，右子树高度为 0，因此差值为 2。在第三棵树中，A 的右子树高度为 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;
}
};
相关文章
有用资源
javascript 参考教程 - 该教程包含有关 javascript 的更多信息:https://www.cainiaomax.com/javascript/
