深入理解红黑树(一)

大家好，我是阿呆，一个不务正业的程序员。

上一篇文章我们介绍了一下JDK1.8中HashMap的实现原理，其中涉及到了红黑树，没有深入的展开讲解，今天来补充一下。

但是在介绍红黑树之前，我们先来了解一下二叉查找树，因为红黑树本质上就是一棵二叉查找树。

本文只讲原理，不谈具体实现，最多只是伪代码。文章同样有点长，也有点干，建议看完。（本文部分原理图来自：

）

0、二叉查找树

二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree），排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

• 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 任意结点的左、右子树也分别为二叉查找树。
• 没有键值相等的结点（no duplicate nodes）。

下图是一棵典型的二叉查找树：

对于一棵二叉树来说，最重要的就是它的结点插入、删除和查找，下面我们分别来看一下，对于二叉查找树，是如何完成这些动作的。

0.1、插入结点

插入结点就是从根结点开始查找比较，如果要插入的结点值大于比较的结点，就取比较结点的右子节点比较，否则就取左子节点比较，直到比较结点为叶子结点，然后根据值的大小，插入到叶子结点的左侧或者右侧。来看一张动图理解一下。

依次插入结点[100,50,200,80,300,10]

看图是不是很好理解，我们再来看下对应的伪代码：

void put(V value) {
	 // 如果是第一个结点，直接创建结点作为根结点，返回
     if (root == null) {
        root = new Node<>(value, null); 
        return;
    }       
    Node<V> t = root; 
    int cmp; // 比较结果    
    Node<V> parent;  
    Comparable<? super V> v = (Compavable<? super V>) value;
    // 从根节点开始向下找
    do {
        parent = t;
        // 比较结点的值
        cmp = k.compareTo(t.key);
        // 如果值比该结点的值小，就取左子节点，否则取右子节点
        // 如果相等，表示值已经存在，直接返回
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else
            return;
    } while (t != null);
    
    // 直到取到的结点是null，退出循环，此时parent为叶子结点
    // 再次根据值的大小，确定是放左边还是放右边
    Node<V> e = new Node<>(value, parent);
    if (cmp < 0){
         parent.left = e;
    }else{
       parent.right = e;  
    }  
}

0.2、查找结点

查找结点其实在刚才的插入结点中就有所体现了，其实就是那一段while循环，这里就不再放伪代码了，直接看个动图。

0.3、删除结点

二叉查找树的删除结点，就是先找到要删除的结点，然后从树中移除。

但是删除的时候会出现一些复杂的情况，我们来总结一下：

1、要删除的结点没有子结点，代表要删除一个叶子结点，这是最简单的情况，直接移除就好

2、要删除的结点有一个子结点，

3、要删除的结点有两个子结点，

我们先来看最简单的情况，也就是要删除的结点是叶子结点的时候，还是来看一张动图。这张图里我们要删除的结点是70。

我们再来看另外一种情况，要删除的结点有一个子结点的情况。这种情况下，只需要把要删除的结点的子结点，交给它的祖父节点，也就是要删除结点的父节点，然后再删除就好了。

下面这张图我们要删除的结点是200。

最后来看一下最复杂的情况，删除有两个子结点的结点，这种情况要涉及到结点的位置变换，需要用该结点的右子树中最小结点替换当前节点。我们通过动图来理解一下。比如我们要删除的是50结点。

最后我们来看下上边这三种情况的伪代码。

Node remove(V value) {
    // 查找节点(参考上面查找结点)
    Node<V> p = getNode(value); 

    // 节点变换。 p 有两个子节点，将其转换为删除后继节点
    if (p.left != null && p.right != null) {
        Entry<K,V> s = t.right;
        while (s.left != null){
            s = s.left;
        }
        p.key = s.key;
        p.value = s.value;
        p = s;
    } 
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    // p 有一个子节点
    if (replacement != null) {
        replacement.parent = p.parent;
        if (p.parent == null){
            root = replacement;
        }  else if (p == p.parent.left){
            p.parent.left  = replacement;
        } else{
            p.parent.right = replacement;
        }
        p.left = p.right = p.parent = null;

    } else if (p.parent == null) { // 根节点
       
         root = null;
    } else { //  p 没有子节点
       
         if (p == p.parent.left){
            p.parent.left = null;
        } else if (p == p.parent.right){
            p.parent.right = null;
        }
        p.parent = null;   
    } 
    return p;
}

0.3、二叉查找树的缺点

由于二叉查找树是一种非平衡树，由于插入数据的顺序，可能会导致所有的结点都倾向于一侧，这种极限情况下，树就变成了一个线性结构，相当于链表。

这种不平衡会导致树的层级增多，也就是高度增加，从而导致查找和插入的效率变低。时间复杂度从O(log n)变为O(n)。

那么如何避免这个问题呢，只需要在每次插入或者删除结点的时候，去动态的维持树的平衡，就不会出现数据向某一侧倾倒的情况了。

而红黑树正是通过这样的方式，来动态保证树的平衡。接下来我们正式介绍红黑树。

1、红黑树

前面我们已经说过，红黑树，本质上来说就是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质，使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

但它是如何保证一棵n个结点的红黑树的高度始终保持在h = logn的呢？这就引出了红黑树的5条性质：

1）每个结点要么是红的，要么是黑的。

2）根结点一定是是黑的。

3）所有叶子结点（叶子结点即指树尾端NIL指针或NULL结点）一定是黑的。

4）如果一个结点是红的，那么它的俩个子结点一定都是黑的。

5）从任一结点出发，到叶子结点的每一条路径，都包含相同数目的黑结点。

正是红黑树的这5条性质，使得一棵n个结点是红黑树始终保持了logn的高度，从而也就解释了上面我们所说的 “红黑树的查找、插入、删除的时间复杂度最坏为O(log n)” 这一结论。

我们先来看一下一棵标准的红黑树是什么样子：

上面我们所说的 “叶子结点” 或”NIL结点”，它不包含数据而只充当路径在此结束的一个指示，这些结点在绘图中经常会被省略。

可以从这张图上来自行验证一下刚才说的5条性质。

1.1、树的旋转知识

当我们在对红黑树进行插入和删除等操作时，也就是树的结点个数发生变化，那么就可能会导致红黑树不再满足性质。

为了继续保持红黑树的性质，我们可以通过对结点进行重新着色，以及对树进行相关的旋转操作，也就是通过修改树中某些结点的颜色及指针结构，来保证对红黑树进行插入或删除结点等操作后，能继续保持它的性质或保持平衡。

树的旋转，分为左旋和右旋，这两种旋转是对称的，我们以右旋为例看一下旋转的过程，下面这张图在p结点上做右旋操作：

我们来简单总结一下这个过程：

当在一个结点上做右旋操作时，需要移动的两个单元分别为：该结点和该结点的右子结点，以及该结点的左子节点和左子结点的左子结点。这两个单元做顺时针旋转。

左旋和右旋对称，是逆时针旋转：

我们来看一下旋转的伪代码：

/**
 * 右旋
 */
private void rotateRight(Node<V> p) {
    if (p != null) {
        Node<V> l = p.left;
        p.left = l.right;
        if (l.right != null) 
            l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

/**
 * 左旋
 */
private void rotateLeft(Node<V> p) {
    if (p != null) {
        Node<V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。