資料結構
網路
RDBMS
作業系統
Java
MS 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 次瀏覽
廣告