这是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); }