我们可以学习如何在AVL树中插入节点。AVL树中的插入与BST相同,只要我们在树上向下移动,我们只需在插入过程中执行一个额外的步骤,称为平衡树。
这需要计算我们之前已经看到的平衡因子。并且根据配置,我们需要调用适当的旋转方法。在以上说明的帮助下,这些都是非常直观的。
我们再次为递归调用创建一个类方法和一个辅助函数-
insert(data) { let node = new this.Node(data); //检查树是否为空 if (this.root === null) { //插入为第一个元素 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) { //向左走! root.left = insertHelper(self, root.left, node); //检查平衡系数并执行适当的旋转 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) { //向右走!根。 right = insertHelper(self, root.right, node); //检查平衡系数并执行适当的旋转 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