数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 编程
C++
C #
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚设计
法律研究在 Javascript AVL 树中插入一个节点
我们可以学习如何在 AVL 树中插入一个节点。AVL 树中的插入与二叉查找树相同，我们只需要在向下移动树时执行一个额外的步骤，称为平衡树。
这需要计算我们之前看到的平衡因子。根据配置，我们需要调用适当的旋转方法。借助以上解释，这些方法非常直观。
我们再次为递归调用创建一个类方法和一个帮助器函数 −
示例
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 查看
广告