红黑树、TreeSet 和 TreeMap

先看看这篇文章，了解一下红黑树。
http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91

特别注意这一段：

因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次。

==================================

看一下帮助文件：

java_zh/java/util/TreeSet.html

public class TreeSet<E>
extends AbstractSet<E>
implements SortedSet<E>, Cloneable, Serializable

此类实现 Set 接口，该接口由 TreeMap 实例支持。此类保证排序后的 set 按照升序排列元素，根据使用的构造方法不同，可能会按照元素的自然顺序 进行排序（参见 Comparable），或按照在创建 set 时所提供的比较器进行排序。

此实现为基本操作（add、remove 和 contains）提供了可保证的 log(n) 时间开销。

==================================
java_zh/java/util/TreeMap.html

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements SortedMap<K,V>, Cloneable, Serializable

SortedMap 接口的基于红黑树的实现。此类保证了映射按照升序顺序排列关键字，根据使用的构造方法不同，可能会按照键的类的自然顺序 进行排序（参见 Comparable），或者按照创建时所提供的比较器进行排序。

此实现为 containsKey、get、put 和 remove 操作提供了保证的 log(n) 时间开销。这些算法是 Cormen、Leiserson 和 Rivest 的《Introduction to Algorithms》中的算法的改编。


==================================

嗯，然后看一段 TreeMap 的源程序。

    /** From CLR **/
    private void fixAfterInsertion(Entry<K,V> x) {
        x.color = RED;

        while (x != null && x != root && x.parent.color == RED) {
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    if (parentOf(parentOf(x)) != null)
                        rotateRight(parentOf(parentOf(x)));
                }
            } else {
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x),  BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    if (parentOf(parentOf(x)) != null)
                        rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;
    }

可以看到，在进行红黑属性恢复。

还有其它的一些函数也涉及到红黑属性恢复，可以自行查看。

评论

3 楼 zwhc 2010-11-19  

maomaolingyu 写道

想问下lz,红黑树在插入和删除之后就不符合红黑树了，那红黑树的实现 TreeMap 在插入和删除做了修复 保证还是红黑树了吗。还没看源码。。tks

你看我的原文：

>>可以看到，在进行红黑属性恢复。

>>还有其它的一些函数也涉及到红黑属性恢复，可以自行查看。

2 楼 maomaolingyu 2010-11-05  

想问下lz,红黑树在插入和删除之后就不符合红黑树了，那红黑树的实现 TreeMap 在插入和删除做了修复 保证还是红黑树了吗。还没看源码。。tks

1 楼 zwhc 2010-04-01  

堆排序与直接选择排序的区别

　　直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在 R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
　　堆排序可通过树形结构保存部分比较结果，可减少比较次数。

http://baike.baidu.com/view/157305.htm