Javascript中的AVL树类

这是AVL树类的完整实现-

示例

class AVLTree {
   constructor() {
      //将根元素初始化为null。
      this.root = null;
   }

   getBalanceFactor(root) {
      return this.getHeight(root.left) - this.getHeight(root.right);
   }

   getHeight(root) {
      let height = 0;
      if (root === null || typeof root == "undefined") {
         height = -1;
      } else {
         height = Math.max(this.getHeight(root.left), this.getHeight(root.right)) + 1;
      }
      return height;
   }

   insert(data) {
      let node = new this.Node(data);
      //检查树是否为空
      if (this.root === null) {
         //作为第一个元素插入this.root = node; 
      } else {
         insertHelper(this, this.root, node);
      }
   }
   inOrder() {
      inOrderHelper(this.root);
   }
}

AVLTree.prototype.Node = class {
   constructor(data, left = null, right = null) {
      this.data = data;
      this.left = left;
      this.right = right;
   }
};

function insertHelper(self, root, node) {
   (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;
}

function inOrderHelper(root) {
   if (root !== null) {
      inOrderHelper(root.left);
      console.log(root.data);
      inOrderHelper(root.right);
   }
}

function rotationLL(node) {
   let tmp = node.left;
   node.left = tmp.right;
   tmp.right = node;
   return tmp;
}

function rotationRR(node) {
   let tmp = node.right;
   node.right = tmp.left;
   tmp.left = node;
   return tmp;
}

function rotationLR(node) {
   node.left = rotationRR(node.left);
   return rotationLL(node);
}

function rotationRL(node) {
   node.right = rotationLL(node.right);
   return rotationRR(node);
}