資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究插入結點到 Javascript AVL 樹
我們可以學習如何插入一個結點到 AVL 樹中。在 AVL 樹中的插入和在 BST 中的插入是一樣的，我們只需要在插入的時候執行一個額外的步驟，即在遍歷樹的時候平衡樹。
這需要計算平衡因子，我們之前已經看到過。並且根據配置，我們需要呼叫適當的旋轉方法。在上述解釋的幫助下，這些方法非常直觀。
我們再次對遞迴呼叫建立類方法和輔助函式 -
示例
insert(data) {
let node = new this.Node(data);
// Check if the tree is empty
if (this.root === null) {
// Insert as the first element
this.root = node;
} else {
insertHelper(this, this.root, node);
}
}輔助方法
function insertHelper(self, root, node) {
if (root === null) {
root = node;
} else if (node.data < root.data) {
// Go left!
root.left = insertHelper(self, root.left, node);
// Check for balance factor and perform appropriate rotation
if (root.left !== null && self.getBalanceFactor(root) > 1) {
if (node.data > root.left.data) {
root = rotationLL(root);
} else {
root = rotationLR(root);
}
}
} else if (node.data > root.data) {
// Go Right! root.
right = insertHelper(self, root.right, node);
// Check for balance factor and perform appropriate rotation
if (root.right !== null && self.getBalanceFactor(root) < -1) {
if (node.data > root.right.data) {
root = rotationRR(root);
} else {
root = rotationRL(root);
}
}
}
return root;
}你可以使用以下程式碼進行測試 -
示例
let AVL = new AVLTree(); AVL.insert(10); AVL.insert(15); AVL.insert(5); AVL.insert(50); AVL.insert(3); AVL.insert(7); AVL.insert(12); AVL.inOrder();
輸出
將會輸出以下結果 -
3 5 7 10 12 15 50
更新於: 15-Jun-2020
189 次瀏覽
廣告