数据结构
网络
关系型数据库管理系统
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会科学
时尚研究
法律研究计算 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;
}
};
更新于: 15-Jun-2020
711 次浏览
广告