資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告