在Javascript AVL树中插入节点

我们可以学习如何在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