关于javascript:前端数据结构算法系列之五平衡二叉树

前端算法系列之一：工夫复杂度、空间复杂度以及数据结构栈、队列的实现
前端算法系列之二：数据结构链表、双向链表、闭环链表、有序链表
前端算法系列之三：数据结构数据汇合
数据结构和算法之四：树
上一篇咱们曾经介绍了树以及树的相干个性，也实现了一个二叉搜寻树 (BST) 也理解 BST 的遍历、搜寻、减少和移除节点的操作。通过后面的学习聪慧的你肯定发现二叉搜寻树在减少元素的时候存在一个问题，当始终增加大于根节点的元素时候，树就会向一侧歪斜。如下图所示：

这样在歪斜的边上增加、移除和搜寻某个节点时引起一些性能问题。为了解决这个问题，有一种树叫作 Adelson-Velskii-Landi 树（AVL 树）。AVL 树是一种自均衡二叉搜寻树，意思是任何一个节点左右两侧子树的高度之差最多为 1。

均衡二叉树(AVL)

均衡二叉树增加和删除元素后，会进行构造的调整，让任意一个节点的左子树和右子树高度之差绝对值小于等于 1；
如何创立一个均衡二叉树的类呢？均衡二叉树也是二叉搜寻树的一种，他继承于二叉搜寻树；

import BinarySearchTree from './BinarySearchTree'
import {defaultCompare, COMPARE, BALANCEFACTOR} from "../util";
import {TreeNode} from "./TreeNode";
export default class AVLTree extends BinarySearchTree{constructor(compareFn = defaultCompare) {super(compareFn);
    this.compareFn = compareFn;
    this.root = null;
    this.count = null;
 }
}

AVL 树继承于 BST 树所以 AVL 具备 BST 中：插入、删除、搜寻、遍历这些办法，对于 AVL 树来说只有在插入和删除的时候会进行树的均衡调整，其余 api 办法是齐全遵循 BST 树的，接下来咱们来实现 AVL 树的 insert、remove 办法，不过在此之前咱们先来理解节点的高度和均衡因子；

节点的高度和均衡因子

所谓节点的高度是指节点到任意子节点边的最大值，也能够说说是节点的深度，如下图所示：

从图中咱们能够看出各个节点的高度 (红色数字)，所谓的高度就是节点左右边数最大的值​；​
怎么计节点的高度呢？实现如下：

getNodeHeight(node) {if (!node) {return -1;}
 return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
}

在 AVL 均衡树中，任何节点右子树的高度（hr）与左子树的高度（hl）之差的绝对值都要小于等于 1，也就是值：-1、0、1 三个值，如果不满足则须要均衡这棵树；咱们把这个差值（-1、0、1）称作均衡因子，能够依据均衡因子来对树进行旋转调整，使树达到均衡状态。
均衡因子的计算形式如下所示：

getBalanceFactor(node) {const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
 switch (heightDifference) {
  case -2:
   return BALANCEFACTOR.UNBALANCED_RIGHT;
 case -1:
   return BALANCEFACTOR.SLIGHTLY_UNBALANCED_RIGHT;
 case 1:
   return BALANCEFACTOR.SLIGHTLY_UNBALANCED_LEFT;
 case 2:
   return BALANCEFACTOR.UNBALANCED_LEFT;
 default:
   return BALANCEFACTOR.BALANCED;
 }
}

均衡 AVL 的旋转

当向均衡二叉树中插入或者删除节点后，就会要对节点进行验证，看是否须要进行再均衡，在均衡中会进行旋转，旋转包含：左 - 左 : 向右的单旋转； 右 - 右 ：向左的单旋转； 左 - 右 ：向右的双旋转（先 LL 旋转，再 RR 旋转）； 右 - 左: 向左的双旋转（先 RR 旋转，再 LL 旋转）；

1、左 - 左（LL）：向左边单旋转
这种状况呈现于节点的左侧子节点的高度大于右侧子节点的高度时，并且左侧子节点也是均衡或左侧较重的，如下图所示。

看下图一个实例：

从图中可知刚开始树是均衡的，前面向树中插入节点 12 后，整体树失去了均衡向左歪斜或者说左侧较重，通过均衡因子的计算，会发现根节点 22 的均衡因子（左子树高度 – 右子树高度）为 2，不属于 -1,、0、1 三个值，所以要进行树的再均衡调整。调整过程如下步骤：
1、和均衡调整相干的三个节点别离是：22、17、15，将节点 17 置于节点 22（均衡因子为 +2）所在的地位；
2、节点 17 的左节点放弃不变，并将节点 22 的左节点置为节点 17 的右节点（20）；
3、将节点 17 的右节点置为节点 22；
通过 LL 调整就失去了右侧的构造了，实现代码如下：

rotationLL(node) {
 const tempNode = node.left; 
 node.left = tempNode.right;
 tempNode.right = node;
 return tempNode;
}

2、右 - 右（RR）：向右边单旋转
这种状况和第一种 LL 刚刚相同，它呈现于右侧子节点的高度大于左侧子节点的高度，并且右侧子节点也是均衡或右侧较重的，如下图所示：

看下图一个实例：

从图中咱们能够晓得在插入节点 11 后，导致整棵树左边歪斜失去平衡；根节点的均衡因子为 -2，绝对值是大于 1 的，所以要进行整体树的调整，而树满足 RR 单向旋转，旋转后从新达到均衡如图右侧；具体的旋转步骤如下：
1、旋转相干节点别离为：3、6、8，将节点 6 置于节点 3(均衡因子是 -2)的地位；
2、将节点 6 的左节点置于 3 的右节点，节点 6 的右节点放弃不变；
3、而后将节点 3 置于节点 6 的左节点；
通过三步就实现了节点旋转；让树从新保持平衡。
代码实现如下：

rotationRR(node) {
 const tempNode = node.right;
 node.right = tempNode.left;
 tempNode.left = node;
 return tempNode;
}

3、左 - 右 (LR)：向右的双旋转
这种状况呈现于左侧子节点的高度大于右侧子节点的高度，并且左侧子节点右侧较重。在解决这种状况，咱们能够对左侧子节点进行左旋转 (RR) 来修复，这样会造成左 - 左的状况，而后再对不均衡的节点进行一个右旋转 (LL) 来修复，如下图所示。

能够看如下图实例：

从上图能够看进去向均衡树中插入节点 23，使整棵树失去平衡，并且合乎 LR 类型；所以依照步骤进行旋转：
1、先对节点 24 的左侧节点进行左单旋转（RR），此刻和旋转相干的元素别离是：15、21、23；
2、将节点 21 置于节点 15，并将节点 21 的左节点置于节点 15 的右节点；
3、将节点 15 置于节点 21 的左节点，而节点 21 的右节点放弃不变，这就实现了对左子节点进行 RR 旋转；
4、下面 3 步失去的树是一颗 LL 树，此时要进行 LL 旋转；
5、进行 LL 旋转和旋转相干的节点：24、21、15，将节点 21 置于节点 24 的地位；
6、将节点 21 的右节点置于节点 24 的左节点，同时将节点 24 置于节点 21 的右节点；
7、节点 21 的左节点和节点 24 的右节点放弃不变，就实现了 LR 旋转，实现树的再均衡；
代码实现如下：

rotationLR(node) {node.left = this.rotationRR(node.left); // 先将失去平衡节点的左子树进行左旋转；return this.rotationLL(node); // 再对整个失去平衡的树进行右单旋转
}

4、右 - 左（R-L）：向左的双旋转
这种状况呈现于右侧子节点的高度大于左侧子节点的高度，并且右侧子节点左侧较重。在解决这种状况，咱们能够对右侧子节点进行右旋转 (LL) 来修复，这样会造成右 - 右的状况，而后再对不均衡的节点进行一个左旋转 (RR) 来修复，如下图所示。

看如下实例：

实现过程和下面的 L - R 绝对的，这外面就不再赘述了，代码实现如下：

rotationRL(node) {node.right = this.rotationLL(node.right); // 先将失去平衡节点的右子树进行右旋转
 return this.rotationRR(node); // 再对整个失去平衡的树进行左旋转
}

理解了这四种旋转形式后咱们来实现均衡树的插入和删除节点

节点的插入：insert(key)

插入一个节点元素会经验如下几个过程：
1、首先会和 BST 规定一样将节点插入树中；
2、而后会计算节点的均衡因子；
3、依据均衡因子进行绝对应的旋转；
4、通过调整后树达到均衡；
代码实现如下：

insert(key) {this.root = this.insertNode(this.root, key);
}
insertNode(node, key) {
 debugger
 if (!node) { // 阐明曾经到了叶节点没有下一个节点了，这个时候能够创立一个新节点作为上一个节点的子节点
 return new TreeNode(key);
 } else if (this.compareFn(key, node.key) === COMPARE.LESS_THAN) { // 如果插入的数比节点的左节点要小
 node.left = this.insertNode(node.left, key);// 递归查找左节点
 } else if (this.compareFn(key, node.key) === COMPARE.BIGGER_THAN) { // 如果插入的数比右节点要大
 node.right = this.insertNode(node.right, key); // 递归查找右节点
 } else {return node; // 相等阐明插入了雷同的数不做操作}
 const balanceFactor = this.getBalanceFactor(node); // 获取该节点的均衡因子
 if (balanceFactor === BALANCEFACTOR.UNBALANCED_LEFT) { // 阐明是左子树失去平衡
 if(this.compareFn(key, node.left.key) === COMPARE.LESS_THAN) { // 如果新插入的数比失去平衡的左子树数要小，则是 LL 型旋转
 node = this.rotationLL(node);
 } else { // 否则阐明新增元素是插入失去平衡节点的左子树的右侧插入，则是 LR 旋转
 return this.rotationLR(node);
 }
 }
 if (balanceFactor === BALANCEFACTOR.UNBALANCED_RIGHT) { // 阐明是右子树失去平衡
 if (this.compareFn(key, node.right.key) === COMPARE.BIGGER_THAN) { // 如果新插入的数比失去平衡的右子树数要大，则是 RR 型旋转
 node = this.rotationRR(node);
 } else { // 否则阐明新增元素是插入失去平衡节点的右子树的左侧插入，则是 RL 旋转
 return this.rotationRL(node);
 }
 }
 return node;
}

测试代码:

avltree.insert(7);
avltree.insert(8);
avltree.insert(9);
avltree.insert(10);
avltree.insert(11);
avltree.insert(12);
avltree.insert(13);
avltree.insert(18);
avltree.insert(25);
let avlarr = [];
avltree.inOrderTraverse((key) => avlarr.push(key));
console.log(avlarr, '中序：inOrderTraverse');//[7, 8, 9, 10, 11, 12, 13, 18, 25]

节点的删除 remove(key)

自均衡二叉树在删除某个节点的时候和 BST（二叉搜寻树）一样先找到这个节点进行删除，删除的状况也会分为删除叶节点、有左子节点或者右子节点、既有左子节点又有右子节点；删除完节点后，会进行均衡因子的计算，再依据均衡因子做相应的均衡调整，使树达到均衡；代码实现如下：

remove(key){this.root = this.removeNode(this.root, key);
}
removeNode(node, key) {node = super.removeNode(node, key);
 if (!node) {return node; // 不须要调整均衡；}
 const balanceFactor = this.getBalanceFactor(node);
 if(balanceFactor === BALANCEFACTOR.UNBALANCED_LEFT) {const balanceFactorLeft = this.getBalanceFactor(node.left);
 if(balanceFactorLeft === BALANCEFACTOR.BALANCED || balanceFactorLeft === BALANCEFACTOR.SLIGHTLY_UNBALANCED_LEFT) {return this.rotationLL(node);
 }
  if (balanceFactorLeft === BALANCEFACTOR.SLIGHTLY_UNBALANCED_RIGHT) {return this.rotationLR(node.left);
 }
 }
 if(balanceFactor === BALANCEFACTOR.UNBALANCED_RIGHT) {const balanceFactorRight = this.getBalanceFactor(node.right);
 if(balanceFactorRight === BALANCEFACTOR.BALANCED || balanceFactorRight === BALANCEFACTOR.SLIGHTLY_UNBALANCED_RIGHT) {return this.rotationRR(node);
 }
  if(balanceFactorRight === BALANCEFACTOR.SLIGHTLY_UNBALANCED_LEFT) {return this.rotationRL(node.right);
 }
 }
 return node;
}

小结

本文次要介绍了一下均衡二叉树的实现原理，关键点要了解几个要害概念：1、树的高度；2、均衡因子计算；3、4 种旋转规定（LL\LR\RR\RL）；4、以及实现均衡二叉树增加和删除元素；其中 4 种旋转规定要重点了解，什么状况进行 LL 旋转什么时候是满足 LR 旋转这些，重复看几遍就能明确其中的情理了；

想理解更多的干活能够关注我的公众号：非驰名 bug 认证师；