概念

BST 存在一个问题：
取决于你添加的节点数，树的一条边可能会非常深；
也就是说，树的一条分支会有很多层，而其他的分支却只有几层，
这会造成很大的性能问题
所以需要平衡二叉搜索树来解决这个问题
平衡二叉树 - 图1
平衡二叉树的概念

  • 在AVL 树中，需要对每个节点计算右子树高度（hr）和左子树高度（hl）之间的差值，该值（hr－hl）应为0、1 或 -1。
  • 如果结果不是这三个值之一，则需要平衡该AVL 树。
    这就是平衡因子的概念。
    平衡二叉树 - 图2

AVL的实现

  • 我们可以扩展我们写的BST 类，只需要覆盖用来维持AVL 树平衡的方法，也就是insert、insertNode 和removeNode 方法。
  • 所有其他的BST 方法将会被AVLTree 类继承。

1 平衡因子的计算

  1. const BalanceFactor = {
  2.     UNBALANCED_RIGHT: 1,
  3.     SLIGHTLY_UNBALANCED_RIGHT: 2,
  4.     BALANCED: 3,
  5.     SLIGHTLY_UNBALANCED_LEFT: 4,
  6.     UNBALANCED_LEFT: 5
  7. };
  1. // 树的高度
  2. getNodeHeight(node) {
  3.     if (!node) {
  4.         return -1;
  5.     }
  6.     return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
  7. }
  9. // 两个树的高度差
  10. getBalanceFactory(node) {
  11.     let heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
  12.     switch (heightDifference) {
  13.         case -2:    // 右边不平衡
  14.             return BalanceFactory.UNBALANCE_RIGHT;
  15.         case -1:    // 右边有点点不平衡
  16.             return BalanceFactory.SLIGHTLY_UNBALANCE_RIGHT;
  17.         case 0:    // 平衡
  18.             return BalanceFactory.BALANCE;
  19.         case 1:    // 左边有点点不平衡
  20.             return BalanceFactory.SLIGHTLY_UNBALANCE_LEFT;
  21.         case 2:    // 左边不平衡
  22.             return BalanceFactory.UNBALANCE_LEFT;
  23.     }
  24. }

2 平衡操作

  • 左-左（LL）：向右的单旋转
  • 右-右（RR）：向左的单旋转
  • 左-右（LR）：向右的双旋转（先LL 旋转，再RR 旋转）
  • 右-左（RL）：向左的双旋转（先RR 旋转，再LL 旋转）

向右的单旋转LL

这种情况出现于节点的左侧子节点的高度大于右侧子节点的高度时，并且左侧子节点也是平衡或左侧较重的，这个时候需要左子树放在上面。者就是所谓的右单旋转
平衡二叉树 - 图3
假设向AVL 树插入节点5，这会造成树失衡（节点50-Y 高度为+2），需要恢复树的平衡。

  1. 保存不平衡树node的左子树temp
  2. node左子树替换为temp的右子树
  3. temp的右子树替换为改变后的node树

平衡二叉树 - 图4
平衡二叉树 - 图5
平衡二叉树 - 图6

  1.     rotationLL(node) {
  2.         let temp = node.left;
  3.         node.left = temp.right;
  4.         temp.right = node;
  5.         return temp;
  6.     }

平衡二叉树 - 图7

RR:向左的单旋转

与LL情况相反。它出现于右侧子节点的高度大于左侧子节点的高度，并且右侧子节点也是平衡或右侧较重的

  1.     rotationRR(node) {
  2.         let temp = node.right;
  3.         node.right = temp.left;
  4.         temp.left = node;
  5.         return temp;
  6.     }

向右的双旋转LR：Left-Right

  • 这种情况出现于左侧子节点的高度大于右侧子节点的高度，并且左侧子节点右侧较重.
  • 简而言之，左子树重了，左子树中的右子树也重了
  • 在这种情况下，可以先对左侧子节点进行RR左旋转来修复，这样会形成LL的情况，然后再对不平衡的节点进行一个LL右旋转来修复

平衡二叉树 - 图8

  1.     rotationLR(node) {
  2.         node.left = this.rotationRR(node.left);
  3.         return this.rotationLL(node);
  4.     }

向左的双旋转RL: Right-Left

  1. 先对右子树进行LL右旋，整个树形成RR条件
  2. 再对整个树RR左旋
    平衡二叉树 - 图9
  1.     rotationRL(node) {
  2.         node.right = this.rotationLL(node.right);
  3.         return this.rotationRR(node);
  4.     }

3 插入结点

插入方法和bst是一样的，不过还需要讨论不平衡的情况

  1. 如果在向左侧子树插入节点后树不平衡了，我们需要比较是否插入的键小于左侧子节点的键。如果是，我们要进行LL 旋转。否则，要进行LR 旋转。
  2. 如果在向右侧子树插入节点后树不平衡了，我们需要比较是否插入的键小于右侧子节点的键。如果是，我们要进行RR 旋转。否则，要进行RL 旋转。
  1. insert(key) {
  2.     this.root = this.insertNode(this.root, key);
  3. }
  4. insertNode(node, key) {
  5.     // 像在BST 树中一样插入节点
  6.     if (node == null) {
  7.         return new Node(key);
  8.     } else if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
  9.         node.left = this.insertNode(node.left, key);
  10.     } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
  11.         node.right = this.insertNode(node.right, key);
  12.     } else {
  13.         return node; // 重复的键
  14.     }
  15.     // 如果需要，将树进行平衡操作
  16.     const balanceFactor = this.getBalanceFactor(node);
  17.        // 左不平衡
  18.     if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
  19.         // 判断是否存在LR情况
  20.         if (this.compareFn(key, node.left.key) === Compare.LESS_THAN) {
  21.             node = this.rotationLL(node);
  22.         } else {
  23.             return this.rotationLR(node);
  24.         }
  25.     }
  26.     // 右不平衡
  27.     if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
  28.         if (this.compareFn(key, node.right.key) === Compare.BIGGER_THAN) {
  29.             node = this.rotationRR(node);
  30.         } else {
  31.             return this.rotationRL(node);
  32.         }
  33.     }
  34.     return node;
  35. }

4 删除结点

  1. removeNode(node, key) {
  2.     node = super.removeNode(node, key);
  3.     if (node == null) {
  4.         return node; // null，不需要进行平衡
  5.     }
  6.     // 检测树是否平衡
  7.     const balanceFactor = this.getBalanceFactor(node);
  8.     // 左不平衡 
  9.     if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
  10.         // 左子树状态
  11.         const balanceFactorLeft = this.getBalanceFactor(node.left);
  12.         // 如果是平衡（h = 0）或者有点不平衡(h = 1),LL
  13.         if (balanceFactorLeft === BalanceFactor.BALANCED ||
  14.             balanceFactorLeft === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
  15.             return this.rotationLL(node);
  16.         }
  17.         // 如果不平衡（h = 2）LR
  18.         if (balanceFactorLeft === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
  19.             return this.rotationLR(node.left);
  20.         }
  21.     }
  22.     // 右不平衡
  23.     if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
  24.         // 右子树
  25.         const balanceFactorRight = this.getBalanceFactor(node.right);
  26.         if (balanceFactorRight === BalanceFactor.BALANCED ||
  27.             balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
  28.             return this.rotationRR(node);
  29.         }
  30.         if (balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
  31.             return this.rotationRL(node.right);
  32.         }
  33.     }
  34.     return node;
  35. }

完整代码

  1. class Node {
  2.     constructor(key) {
  3.         this.key = key; //  节点值
  4.         this.left = null; // 左侧子节点引用
  5.         this.right = null; // 右侧子节点引用
  6.     }
  7. }
  9. const Compare = {
  10.     LESS_THAN: -1,
  11.     BIGGER_THAN: 1
  12. };
  14. class BinarySearchTree {
  15.     constructor() {
  16.         this.root = null; //  Node 类型的根节点 默认就是null
  17.     }
  19.     compareFn(a, b) {
  20.         if (a === b) { //
  21.             return 0;
  22.         }
  23.         return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN; // 比较函数, a<b返回-1. 大于则返回正1
  24.     }
  26.     insert(key) {
  27.         if (this.root == null) {
  28.             this.root = new Node(key);
  29.         } else {
  30.             this.insertNode(this.root, key);
  31.         }
  32.     }
  34.     insertNode(node, key) {
  35.         if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
  36.             if (node.left == null) {
  37.                 node.left = new Node(key);
  38.             } else {
  39.                 this.insertNode(node.left, key);
  40.             }
  41.         } else {
  42.             if (node.right == null) {
  43.                 node.right = new Node(key);
  44.             } else {
  45.                 this.insertNode(node.right, key);
  46.             }
  47.         }
  48.     }
  50.     inOrderTraverse(callback) {
  51.         this.inOrderTraverseNode(this.root, callback);
  52.     }
  54.     inOrderTraverseNode(node, callback) {
  55.         if (node != null) {
  56.             this.inOrderTraverseNode(node.left, callback);
  57.             callback(node.key);
  58.             this.inOrderTraverseNode(node.right, callback);
  59.         }
  60.     }
  62.     preOrderTraverse(callback) {
  63.         this.preOrderTraverseNode(this.root, callback);
  64.     }
  66.     preOrderTraverseNode(node, callback) {
  67.         if (node != null) {
  68.             callback(node.key);
  69.             this.preOrderTraverseNode(node.left, callback);
  70.             this.preOrderTraverseNode(node.right, callback);
  71.         }
  72.     }
  74.     postOrderTraverse(callback) {
  75.         this.postOrderTraverseNode(this.root, callback);
  76.     }
  78.     postOrderTraverseNode(node, callback) {
  79.         if (node != null) {
  80.             this.postOrderTraverseNode(node.left, callback);
  81.             this.postOrderTraverseNode(node.right, callback);
  82.             callback(node.key);
  83.         }
  84.     }
  86.     min() {
  87.         return this.minNode(this.root);
  88.     }
  90.     minNode(node) {
  91.         let current = node;
  92.         while (current != null && current.left != null) {
  93.             current = current.left;
  94.         }
  95.         return current;
  96.     }
  98.     max() {
  99.         return this.maxNode(this.root);
  100.     }
  102.     maxNode(node) {
  103.         let current = node;
  104.         while (current != null && current.right != null) {
  105.             current = current.right;
  106.         }
  107.         return current;
  108.     }
  110.     search(key) {
  111.         return this.searchNode(this.root, key);
  112.     }
  114.     searchNode(node, key) {
  115.         if (node == null) {
  116.             return false;
  117.         }
  118.         if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
  119.             return this.searchNode(node.left, key);
  120.         } else if (
  121.             this.compareFn(key, node.key) === Compare.BIGGER_THAN
  122.         ) {
  123.             return this.searchNode(node.right, key);
  124.         } else {
  125.             return true;
  126.         }
  127.     }
  129.     remove(key) {
  130.         this.root = this.removeNode(this.root, key);
  131.     }
  133.     removeNode(node, key) {
  134.         if (node == null) {
  135.             return null;
  136.         }
  137.         if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
  138.             node.left = this.removeNode(node.left, key);
  139.             return node;
  140.         } else if (
  141.             this.compareFn(key, node.key) === Compare.BIGGER_THAN
  142.         ) {
  143.             node.right = this.removeNode(node.right, key);
  144.             return node;
  145.         } else {
  146.             // 键等于node.key
  147.             // 第一种情况
  148.             if (node.left == null && node.right == null) {
  149.                 node = null;
  150.                 return node;
  151.             }
  152.             // 第二种情况
  153.             if (node.left == null) {
  154.                 node = node.right;
  155.                 return node;
  156.             } else if (node.right == null) {
  157.                 node = node.left;
  158.                 return node;
  159.             }
  160.             // 第三种情况
  161.             const aux = this.minNode(node.right);
  162.             node.key = aux.key;
  163.             node.right = this.removeNode(node.right, aux.key);
  164.             return node;
  165.         }
  166.     }
  167. }
  169. const BalanceFactor = {
  170.     UNBALANCED_RIGHT: 1,
  171.     SLIGHTLY_UNBALANCED_RIGHT: 2,
  172.     BALANCED: 3,
  173.     SLIGHTLY_UNBALANCED_LEFT: 4,
  174.     UNBALANCED_LEFT: 5
  175. };
  179. class AVLTree extends BinarySearchTree {
  180.     constructor() {
  181.         super();
  182.         this.root = null;
  183.     }
  184.     getNodeHeight(node) {
  185.         if (node == null) {
  186.             return -1;
  187.         }
  188.         return Math.max(
  189.             this.getNodeHeight(node.left), this.getNodeHeight(node.right)
  190.         ) + 1;
  191.     }
  192.     getBalanceFactor(node) {
  193.         const heightDifference = this.getNodeHeight(node.left) -
  194.             this.getNodeHeight(node.right);
  195.         switch (heightDifference) {
  196.             case -2:
  197.                 return BalanceFactor.UNBALANCED_RIGHT;
  198.             case -1:
  199.                 return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
  200.             case 1:
  201.                 return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
  202.             case 2:
  203.                 return BalanceFactor.UNBALANCED_LEFT;
  204.             default:
  205.                 return BalanceFactor.BALANCED;
  206.         }
  207.     }
  208.     rotationLL(node) {
  209.         const tmp = node.left;
  210.         node.left = tmp.right;
  211.         tmp.right = node;
  212.         return tmp;
  213.     }
  214.     rotationRR(node) {
  215.         const tmp = node.right;
  216.         node.right = tmp.left;
  217.         tmp.left = node;
  218.         return tmp;
  219.     }
  220.     rotationLR(node) {
  221.         node.left = this.rotationRR(node.left);
  222.         return this.rotationLL(node);
  223.     }
  224.     rotationRL(node) {
  225.         node.right = this.rotationLL(node.right);
  226.         return this.rotationRR(node);
  227.     }
  228.     insert(key) {
  229.         this.root = this.insertNode(this.root, key);
  230.     }
  231.     insertNode(node, key) {
  232.         // 像在BST 树中一样插入节点
  233.         if (node == null) {
  234.             return new Node(key);
  235.         } else if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
  236.             node.left = this.insertNode(node.left, key);
  237.         } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
  238.             node.right = this.insertNode(node.right, key);
  239.         } else {
  240.             return node; // 重复的键
  241.         }
  242.         // 如果需要，将树进行平衡操作
  243.         const balanceFactor = this.getBalanceFactor(node);
  244.         if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
  245.             if (this.compareFn(key, node.left.key) === Compare.LESS_THAN) {
  246.                 node = this.rotationLL(node);
  247.             } else {
  248.                 return this.rotationLR(node);
  249.             }
  250.         }
  251.         if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
  252.             if (
  253.                 this.compareFn(key, node.right.key) === Compare.BIGGER_THAN
  254.             ) {
  255.                 node = this.rotationRR(node);
  256.             } else {
  257.                 return this.rotationRL(node);
  258.             }
  259.         }
  260.         return node;
  261.     }
  262.     removeNode(node, key) {
  263.         node = super.removeNode(node, key);
  264.         if (node == null) {
  265.             return node; // null，不需要进行平衡
  266.         }
  267.         // 检测树是否平衡
  268.         const balanceFactor = this.getBalanceFactor(node);
  269.         // 左不平衡 
  270.         if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
  271.             // 左子树状态
  272.             const balanceFactorLeft = this.getBalanceFactor(node.left);
  273.             // 如果是平衡（h = 0）或者有点不平衡(h = 1),LL
  274.             if (balanceFactorLeft === BalanceFactor.BALANCED ||
  275.                 balanceFactorLeft === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
  276.                 return this.rotationLL(node);
  277.             }
  278.             // 如果不平衡（h = 2）LR
  279.             if (balanceFactorLeft === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
  280.                 return this.rotationLR(node.left);
  281.             }
  282.         }
  283.         // 右不平衡
  284.         if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
  285.             // 右子树
  286.             const balanceFactorRight = this.getBalanceFactor(node.right);
  287.             if (balanceFactorRight === BalanceFactor.BALANCED ||
  288.                 balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
  289.                 return this.rotationRR(node);
  290.             }
  291.             if (balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
  292.                 return this.rotationRL(node.right);
  293.             }
  294.         }
  295.         return node;
  296.     }
  297. }
  299. let avl = new AVLTree();
  300. avl.insert(70);
  301. avl.insert(50);
  302. avl.insert(80);
  303. avl.insert(72);
  304. avl.insert(90);
  305. avl.insert(75);
  306. avl.remove(70);
  307. avl.remove(50);
  308. console.log(avl);