JDK源码研究TreeMap（红黑树）下篇

十三月的

浏览: 165153 次
性别:
来自: 长沙

最近访客更多访客>>

robotmen

malongkong

天堂路

leozam

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

数据结构理解

JDK TreeMap 红黑树

TreeMap

目的：

通过对JDK源码的分析，进一步了解红黑树。

1:TreeMap介绍

2:红黑树介绍

3:红黑树插入及TreeMap插入实现

4:红黑树删除及TreeMap删除实现

1：TreeMap介绍

TreeMap和HashMap同样继承于Map接口，前者是在基于红黑树，后者是基于散列。

红黑树，是一种平衡的二叉搜索树。但是它并非是严格的平衡树，而是追求局部的平衡，从而保证树的高度在lgn和2lgn之间。

所谓平衡，实际是为了解决二叉搜索树的两种极端情况即所有结点的值本来是有序，则在建立二叉搜索树的时候，该树实际变成了一个链表，它的时间复杂度是o(n)。当通过旋转操作使之称为平衡二叉树后，树的高度是lgn，则其搜索的时间复杂度是o(lgn)。

2：红黑树介绍

红黑树：红黑树首先是一个二叉搜索树.树中每个节点的值，都大于或等于在它的左子树中的所有节点的值，并且小于或等于在它的右子树中的所有节点的值。

除此之外，红黑树还有如下性质：

1：每个结点都有颜色，不是红色就是黑色

2：根节点必须是黑色

3：所有的叶子结点都是空结点（null），颜色是黑色

4：红色结点的父结点必须是黑色

5：从任意一个结点到其子树中的叶子结点的路径中包含相同数目的黑色节点。

3：红黑树插入及TreeMap插入实现

http://wlh0706-163-com.iteye.com/blog/1851697

4：红黑树删除及TreeMap删除实现

删除结点和修复结点有如下4种情况，我们分为3类

第一类：情况1

情况：如果被删除的结点D有两个非空孩子。

策略：选择按照中序遍历时该结点下一个结点H，只把D的值改为H的值，但是并不改变D的颜色。然后将D指向H位置。（H结点是第二类中的一种情况）

第二类：情况2，3

情况：当删除的结点是第一类的时候，经过上述分析实际上是转化为了第二类中某一种情况。

策略：我们直接用D的儿子代替D，我们称之为N。但是这并没有完，直接替代有可能会违反红黑树的一些性质，需要详细讨论。

针对第二类详细讨论：

1：如果D是红色，结束。

2：如果D是黑色，此时需要根据N的父亲P、兄弟S、S的左孩子S_L和右孩子S_R的颜色进行判断。

下面对D是黑色，分情况讨论：

情况1：如果D没有父节点，即为root，则结束。

情况2：如果D有父节点，S的颜色为红色。

结果：

此时,原本经过P和S的路线的黑色结点个数并没有变化；原本经过P和N的路线改成经过S、P和N，虽然结点增多，但是仍旧没有改变本条线路由于删除D后减少一个黑色结点的事实，但是N的情况已经改变，可以转换为下面的情况来分析。

情况3：如果D有父节点P，P的颜色是黑色，S结点是黑色，同时它的两个儿子S_L和S_R也是黑色。

结果：

此时，原本经过P和S的路线的黑色结点个数由于S变成了红色减少1；原本经过P和N的路线仍旧因删除了D减少1个黑色结点并没有改变；但是这个时候经过P的两条线路的黑色结点个数相同了（当然仍旧改变不了都减少1个黑节点的事实），这个时候相当于N指向了P,需要从情况1开始进行分析。

情况4：如果D有父节点P，P的颜色是红色，S结点是黑色，S的儿子S_L为黑色和S_R为黑色

结果：

此时，原本经过P和S的路线的黑色结点个数并没有发生改变；当时原本经过P和N的线路由于P的颜色的改变，弥补了删除D后黑色结点个数的损失，结束！

所以说，第4种情况是继第1种情况后，又一个简单的情况。

情况5：如果D有父节点P，P的颜色不确定，S结点是黑色，S的儿子S_R为黑色和S_L为红色。

结果：

N和SL成为了兄弟结点，原本经过P和S的线路，虽然调换了S和SL的颜色并进行旋转，此时黑色结点并没有改变；原本经过P和N的线路并没有做出任何改变，因此此线路仍旧由于删除了D结点后黑色结点还是少1.此时我们已经将情况5做出了一点改变即：如果D有父节点P，P的颜色不确定，S结点是黑色，（到这还没有改变），S的儿子S_R为红色（情况改变）。实际这就是情况6.情况6就是另外一个结束的大门.

情况6：如果D有父节点P，P的颜色不确定，S结点是黑色， S的儿子S_R为红色。

结果：

原本经过P和S的线路虽然由于P和S交换，并且P叛变为另外一条线路，但是此时SR及时改变颜色，使得经过该线路的黑色结点个数没变；原本经过P和N的线路，此时多了一个结点P弥补了删除D使得黑色结点少1的情况，结束！（当然当前经过P的线路仍旧满足黑色结点个数相同如经过P到3和经过P、N到1和2处）

上述6种共有3个出口，即情况1、4和6.

上述6种情况都是假设N是P的左节点，当然如果N是右节点情况是一样的。

第三类：情况4

实际上第三类和第二类处理方法是相同的，但是处理的顺序是不同的。

由于D没有子孩子，修复的办法是：用D充当第二类中的N，带修复完毕之后，再设置父子节点的关系。

代码实现：

private void deleteEntry(Entry<K,V> p) 
 { 
    modCount++; 
    size--; 
   // 第一类：被删除节点的左子树、右子树都不为空
    if (p.left != null && p.right != null) 
    { 
        // 用 p 节点的中序后继节点代替 p 节点
        Entry<K,V> s = successor (p); 
        p.key = s.key; 
        p.value = s.value; 
        p = s; 
    } 
   //第二类：如果左节点不为空则选取左节点，否则选取右节点
    Entry<K,V> replacement = (p.left != null ? p.left : p.right); 
    if (replacement != null) 
    { 
        replacement.parent = p.parent; 
        // 如果 p 没有父节点即root
        if (p.parent == null) 
            root = replacement; 
        // 如果 p 节点是其父节点的左子节点
        else if (p == p.parent.left) 
            p.parent.left  = replacement; 
        // 如果 p 节点是其父节点的右子节点
        else 
            p.parent.right = replacement; 
        p.left = p.right = p.parent = null; 
        // 修复
        if (p.color == BLACK) 
            fixAfterDeletion(replacement);    
    } 
    // 如果 p 节点没有父节点
    else if (p.parent == null) 
    { 
        root = null; 
    } 
    else 
    { 
    //第三类：先根据p修复，再设置父子关系
        if (p.color == BLACK) 
            // 修复红黑树
            fixAfterDeletion(p);      
        if (p.parent != null) 
        { //设置父子关系
            if (p == p.parent.left) 
                p.parent.left = null; 
            else if (p == p.parent.right) 
                p.parent.right = null; 
            p.parent = null; 
        } 
    } 
 }

修复函数

// 修复红黑树
 private void fixAfterDeletion(Entry<K,V> x) 
 { 
    //情况2-5： 直到 x 不是根节点，且 x 的颜色是黑色
    while (x != root && colorOf(x) == BLACK) 
    { 
        //  左子节点
        if (x == leftOf(parentOf(x))) 
        { 
            // 获取 x 节点的兄弟节点
            Entry<K,V> sib = rightOf(parentOf(x)); 
            //情况2：如果 sib 节点是红色
            if (colorOf(sib) == RED) 
            { 
                setColor(sib, BLACK); 
                setColor(parentOf(x), RED); 
                rotateLeft(parentOf(x)); //左旋
                // 再次将 sib 设为 x 的父节点的右子节点
                sib = rightOf(parentOf(x)); 
            } 
           //情况3和4：如果 sib 的两个子节点都是黑色
            //这里有个不同的地方：针对情况4，我们分析的时候它是一个出口
            //这里和情况3一样只是设置x为它的父节点，而情况4中父节点是红色
            //直接跳出循环，执行最后一句<span style="font-size: 1em; line-height: 1.5;">setColor(x, BLACK);效果一样</span>
            if (colorOf(leftOf(sib)) == BLACK 
                && colorOf(rightOf(sib)) == BLACK) 
            { 
                setColor(sib, RED);  
                x = parentOf(x); 
            } 
            else 
            { 
               //情况5：如果 sib 的孩子只有右子节点是黑色
                if (colorOf(rightOf(sib)) == BLACK) 
                { 
                    setColor(leftOf(sib), BLACK); 
                    setColor(sib, RED); 
                    rotateRight(sib); 
                    sib = rightOf(parentOf(x)); 
                } 
               //情况6：如果sib的孩子的右节点是红色
                setColor(sib, colorOf(parentOf(x))); 
                setColor(parentOf(x), BLACK); 
                setColor(rightOf(sib), BLACK); 
                rotateLeft(parentOf(x)); 
                x = root; 
            } 
        } 
        //另外一种： 如果 x 是其父节点的右子节点
        else 
        { 
            Entry<K,V> sib = leftOf(parentOf(x)); 
            if (colorOf(sib) == RED) 
            { 
                setColor(sib, BLACK); 
                setColor(parentOf(x), RED); 
                rotateRight(parentOf(x)); 
                sib = leftOf(parentOf(x)); 
            } 
            if (colorOf(rightOf(sib)) == BLACK 
                && colorOf(leftOf(sib)) == BLACK) 
            { 
                setColor(sib, RED); 
                x = parentOf(x); 
            } 
            else 
            { 
                if (colorOf(leftOf(sib)) == BLACK) 
                { 
                    setColor(rightOf(sib), BLACK); 
                    setColor(sib, RED); 
                    rotateLeft(sib); 
                    sib = leftOf(parentOf(x)); 
                } 
                setColor(sib, colorOf(parentOf(x))); 
                setColor(parentOf(x), BLACK);       
                setColor(leftOf(sib), BLACK); 
                rotateRight(parentOf(x)); 
                x = root; 
            } 
        } 
    } 
    setColor(x, BLACK); 
 }

可以看的出来，删除结点的复杂性要远远比插入复杂，需要考虑的情况也多。

想要看明白红黑树确实需要自己动手画些图，即便是看不懂，可以按照插入的例子运行一次，就能对其过程有很大的了解，画的多了很多就自然明白，至于作者当时是如何想到此种数据结构以及进行修复，就难以用自己的思维逻辑去推到了。

TreeMap主要的步骤就在插入和删除（当然还有其他的，此处没有分析），红黑树分析到此为止。