二叉树与红黑树

BST

二叉查找树就是一颗二叉树，他的左节点比父节点要小，右节点比父节点要大。他的高度决定的查找效率。

理想状态下，二叉树的增删改查的时间复杂度为O(LogN)，最坏的情况为O(N)。当他的高度为LogN+1时，我们说二叉查找树是平衡的。下面盗图几张。

T key = a search key;   //查找的值
Node root = point to the root of a bst; //二叉树的根节点
while(true){
    if(root==null){
        return null;
    }
    if(root.value==key){
        return root;
    }else if(key.compareTo(root.value)<0){
        root = root.left;
    }else{
        root = root.righr;
    }
}
return null;

当查找BST时，先进行当前节点比较：

• 如果相等的话就返回当前节点；
• 如果比当前节点小，则继续查找当前节点的左节点；
• 否则就继续查找当前节点的右节点。

直到当前节点指针为空或找到节点，查找结束。

BST的插入操作

Node node = create a new node;
Node root = point to the root of a bst; //二叉树的根节点
Node parent = null;

while(true){
    if(root==null) break;
    parent = root;
    if(node.value.compareTo(root.value)<0){
        root = parent.left;
    }else{
        root = parent.right;
    }
}
if(parent!=null){
    if(node.value.compareTo(root.value)<0){
        parent.left = node;
    }else{
        parent.right = node;
    }
}

插入BST时，先查找要插入的父节点。找到父节点后，通过比较与父节点的大小，决定要插入节点的位置。

BST的删除操作

1. 查找到要删除的节点。

2. 如果待删除的节点是叶子节点，则直接删除。

3. 如果待删除的节点不是叶子节点，则先找到待删除节点的中序遍历的后继节点，用该后继节点的值替换待删除的节点的值，然后删除后继节点。

   中序遍历：先遍历左节点，然后遍历根节点，最后遍历右节点（根节点放中间）

BST存在的问题

BST存在的问题是，数在插入的时候会导致倾斜，不同的插入顺序会导致数的高度不一样，而树的高度直接影响了树的查找效率。理想的高度是LogN，最坏的情况所有的节点都在一条斜线上，这样树的高度为N。

红黑树Red-Black Tree（RBTree）

基于BST存在的问题，平衡查找二叉树（Balanced BST）产生了。平衡树的插入和删除的时候，会通过旋转操作将高度保持在LogN。其中两款具有代表性的平衡术分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。

红黑树的实际应用非常广泛，如Java中的HashMap和TreeSet，Java 8中HashMap的实现因为用RBTree代替链表（链表长度>8时），性能有所提升。

RBTree的规则定义

1.任何一个节点都有颜色，红色或黑色
2.根节点是黑色的
3.父子节点之间不能出现两个连续的红节点
4.任何一个根节点，遍历到他的子孙节点，所经过的黑色节点数必须相同
5.空节点被认为是黑色的

  class Node<T>{
    public T value;
    public Node<T> parent;
    public boolean isRed;
    public Node<T> left;
    public Node<T> right;
}

因为以上规则的限制，保证了红黑树的自平衡。红黑树从根到叶子节点的最长路径不会超过最短路径的2倍。

RBTree的自平衡策略

当插入或删除节点时，红黑树的规则可能被打破，这时候就需要做出一些调整，来维持RBT的规则定义。调整包括变色，左旋转和右旋转。

变色

为了符合红黑树规则，尝试将节点颜色红色节点变为黑色，或将黑色节点变为红色。

旋转

旋转操作(Rotate)的目的是使节点颜色符合定义，让RBTree的高度达到平衡。
左旋转：被旋转的节点从左侧上升到父节点
右旋转：被旋转的节点从右侧上升到父节点

什么时候用变色，什么时候用旋转呢？

查了一些资料，插入和删除包含了很多情况，比较复杂。这里有个传送们：
30张图带你彻底理解红黑树。

RBTree的插入操作

RBTree与BST的插入方式是一样的，只不过在插入之后，可能会导致树的不平衡，这时需要对树进行旋转操作和颜色修复（这里简称插入修复），使得他符合RBTree的定义。

新插入的节点颜色是红色，插入修复操作如果遇到父节点为黑色则修复操作结束。也就是说，只有在父节点为红色时是需要修复操作的。

当父节点为红色时，插入修复操作分以下三种情况：

1. 叔叔节点也为红色。
2. 叔叔节点为空，且祖父节点、父节点和新节点处于同一条斜线上。
3. 叔叔节点为空，且祖父节点，父节点和新节点不处于同一条斜线上。

插入 - case1

如果叔叔节点也为红色，则将父节点，叔叔节点，祖父节点颜色互换，这样就符合了RBTree的定义。既维持了高度的平衡。下图中插入N节点，经过修复A、B、C节点颜色互换，如果A节点的父节点也为红色，则继续进行修复操作。

1566953856393.png

插入 - case 2

将B节点右旋，并且和父节点A互换颜色。如果B、C节点都是右节点，则将B节点左旋，然后与父节点A互换颜色就可以了。通过该修复操作的RBTree，高度和颜色都符合红黑树的定义。 1566966499559.png

插入 - case 3

1566967585800.png

现将C节点左旋，旋转后就将修复操作转换为 case 2。

插入操作总结

插入操作是一个向根节点回溯的操作，一旦牵涉的所有节点都符合红黑树的规则，则修复操作结束。之所以回回溯，是因为在进行case 1时，会将父节点颜色改变，有可能导致祖父节点不平衡，这时候就需要从祖父节点为起点，根据以上三种case做出调整。调整会一直到节点符合红黑树规则维泽，否则会一直到root节点结束，root节点永远是黑色的。

RBTree的删除操作

删除操作首先要做的是BST的删除操作，如果被删除的节点是叶子节点，则直接删除，如果是非叶子节点，会将该节点的中序遍历后继节点顶替要删除的节点。删除后就需要做删除修复操作，使RBTree符合定义，高度平衡。

删除修复操作在遇到删除节点是红色或到达root节点时结束修复。

删除操作是针对删除节点是黑色才有的（4. 任何一个根节点，遍历到他的子孙节点，经过的黑色节点必须相同），需要做的操作是从他的兄弟节点上借调黑色节点过来，如果没有黑色节点可以调用，则向上追溯，将每一级的黑色节点减1（？？），使红黑树符合定义。

删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部平衡，如果局部平衡达成了，就看整体树是否平衡，如果不平衡就向上追溯调整。

删除修复节点分为有多种情况，下面举两种例子：

1. 待删除的节点的兄弟节点是红色的
2. 待删除的节点的兄弟节点是黑色的，且兄弟节点所有子节点都是黑色的

...

删除 - case 1

由于兄弟节点是红色的，无法从兄弟节点借调，所以将兄弟节点通过左旋提升到父节点。这样case 1就可以转换成 case 2 ，case 3，case 4进行处理了。

1567039739689.png

删除 - case 2

由于兄弟节点及其所有的子节点都是黑色，所以可以将兄弟节点变红，这样就可以保证树的局部颜色定义了。继续向上调整，知道整棵树的颜色符合RBTree的定义为止。 1567040701594.png

删除总结

红黑树的删除是最复杂的操作，复杂在于删除黑色节点的时候，如何从兄弟节点调用，以保证树符合定义。

总结

作为二叉查找树中面众多的实现之一，红黑树通过引入颜色的概念，通过颜色约束的使用，包括变色和旋转，来保持树的高度平衡。即使在最坏的情况下，操作的时间复杂度也为O(LogN)，原因是整个红黑树的高度保持是LogN(因为旋转修复)。

参考文章：

• 红黑树深入剖析及Java实现
• 漫画：什么是红黑树？