8、红黑树

平衡树：AVL（平衡二叉搜索树），红黑树（AVL整体效率低于红黑树，现在一般都用红黑树）
二叉平衡树：平衡二叉搜索树，也可叫做AVL树，是一种自平衡的树。
除了规定左节点小于根节点，右节点大于根节点以外，还规定了左子树和右子树的高度差不得超过1。
因为查找效率和树的高度成正比，所以我们需要建立一棵尽可能矮的树。
平衡因子：左子树的高度减去其右子树的高度。
所以，平衡二叉树中，各个结点的平衡因子的绝对值小于等于1，【-1，0，1】，可以满足我们的二叉平衡树的需求，平衡二叉树是一棵二叉搜索树，只不过平衡树比较矮而已。
控制平衡因子：如果平衡因子的绝对值超过了1，那么我们就称之为：失衡
控制平衡因子，要把平衡因子控制在绝对值不大于1的范围内（平衡值调整），在平衡二叉树中，使用旋转操作来达到平衡。

左侧子节点高于右侧子节点时

右侧子节点高于左侧子节点时

AVL树相对于红黑树，它的插入/删除操作效率都不高
红黑树（R-B tree）
红黑树是一种自平衡的二叉搜索树，以前叫作平衡二叉B树
红黑树增加的一些特性：
1、结点是红色或者黑色（结点上有一个color属性）
class Node{
    constructor(){
      this.color = 'black';
  }
}
2、根节点是黑色
3、叶子节点都是黑色且为null（NIL节点）
4、连接红色节点的两个子节点都是黑色，红色结点的父节点都是黑色，红色结点的子节点都是黑色
5、从任意结点出发，到其每个叶子结点的路径中包含相同数量的黑色结点
这5条性质就是红黑树给出的自动维持平衡所具备的规则
是为了保证：从根节点到叶子节点的最长路径不大于最短路径的2倍
红黑树插入数据的时候，会先去遍历数据应该插入到哪个位置，插入的数据一定是红色的

总结：
1、树
2、二叉树
3、二叉搜索树
4、红黑树：自平衡的二叉搜索树