上善若水
In general the OO style is to use a lot of little objects with a lot of little methods that give us a lot of plug points for overriding and variation. To do is to be -Nietzsche, To bei is to do -Kant, Do be do be do -Sinatra
posts - 146,comments - 147,trackbacks - 0
因为看EHCache中溢出文件的管理代码,它用到了AA-Tree作为文件中的磁盘管理,因而决定先复习以下红黑树(RBT, Red Black Tree),顺便看看TreeMap的代码。关于红黑树,网上已经有各种相关的文章了,因而属于多一篇不多,少一篇不少的状态,因而我纯粹当作是我自己理解的纪录,加深印象,如果能对部分思路和我类似的人有一些帮助,那就最好了。基于这样的目的,我并不打算深入,如果想看更深入的或者更好的,可以读读我最后的参考链接。

红黑树引入的目的
首先要从对有序序列的查找问题开始,对一个静态的有序序列数组,只需要二分查找即可得到O(log(n))的查找效率;然而实现并不会显得那么“静态”,需要实现动态的插入、删除同时保持序列的有序性,并且尽量提高插入、删除、查找的效率。

为实现动态插入、删除,最简单的实现是二叉排序树(BST, Binary Sort Tree),它具有以下性质:
1. 它可以是一个空树。
2. 若它的左子树不为空,则它的左子树所有节点的值均小于根节点的值。
3. 若它的右子树不为空,则它的右子树所有节点的值均大于根节点的值。
4. 它的左子树和右子树都是一个二叉排序树。
根据以上性质,
对查找,比较查找数和当前节点,如果查找数和当前节点相等,则找到返回;如果查找数小于当前节点,查找其左子树,如果查找数大于当前节点,查找其右子树,直到找到或直到叶子节点为null,返回null。
对插入,先查找这棵树,如果找到已存在的节点,更新节点值,否则把新值插入到最后一个为null的节点中。
对删除,首先找到要删除的节点,a)如果找到的节点P没有子节点,直接删除即可;b)如果找到的节点P只有左子树或右子树,删除该节点,并将其父节点原来的指针指向它唯一的左子树、或右子树即可;c)如果找到的节点P既有左子树又有右子树,可以有两种做法:I)删除节点P,把节点P的父节点原来指向P的指针指向节点P的左字节点,而将节点P的右节点插入到节点P右节点的最右叶子节点上(如果节点P是其父节点的右节点,则将节点P的父节点原来指向P节点的指针指向P节点的右子树,而将节点P的左子树插入到节点P最左叶子节点上),II)将节点P替换成节点P的直接前驱(或直接后继),然后删除节点P的直接前驱(或直接后继)(注:直接前驱查找:节点P左子树的最右节点,直接后继查找:节点P右子树的最左节点)。
二叉排序树实现比较简单,但是它查找效率却不理想,最好的效率是O(log(n)),最会效率为O(n)。

为了提高查找效率,后来有人提出了平衡二叉树(AVL树),它具有二叉排序树的所有特点,并添加了以下性质:
1. 左子树和右子树的深度之差绝对值不超过1。
2. 左子树和右子树都是平衡二叉树。
为了实现平衡二叉树,需要在没个节点上添加平衡因子字段,在插入后,如果发现平衡因子不符合性质1,则需要经过旋转以调整。平衡二叉树可以保证其查找的最好、最坏查找时间复杂度都为O(log(n))。

红黑树是平衡二叉树的变种,它是一种自平衡的二叉排序树,也需要通过一些旋转调整以保持它的性质,它的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。不同于平衡二叉树的高度平衡,红黑树只能保证从根到叶子节点的最长路径不超过最短路径的2倍,因而它的最坏查找时间复杂度为O(2log(n + 1)),然而有研究表明它的统计性能要好于平衡二叉树,因而它具有更广泛的应用。

红黑树的性质
一棵树需要满足以下性质才能保证它是一颗红黑树:
1. 它是一颗二叉查找树(BST)。
2. 它的所有节点是红色或黑色。
3. 它的根节点是黑色。
4. 它的叶子节点是黑色(空节点视为叶子节点)。
5. 它的红节点的子节点必须是黑色的;而黑节点的字节点可以是黑色或红色。
6. 它任一节点到其后代的叶子节点路径上有相同的黑色节点数。
一般的文章都是把性质列出来,然后根据这些性质来写代码实现(我也一样:)),但是如何得出这些性质呢?多问几个为什么总是好事,这个问题需要去读上面提到的论文,我没读过也不打算读,这貌似不是我能涉及的,那就提出问题不回答了。。。

TreeMap中红黑树的节点
对一颗树的节点,最基础是该节点的值、左节点指针、右节点指针。对TreeMap,因为它存储的是键值对,因而它包含了key、value,为了纪录节点的颜色,它还需要有color字段:
    private static final boolean RED   = false;
    private static final boolean BLACK = true;

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left = null;
        Entry<K,V> right = null;
        Entry<K,V> parent;
        boolean color = BLACK;
        ....
    }

TreeMap中红黑树节点插入
红黑数的插入分以下步骤:
1. 如果当前为空树,插入节点直接作为根节点,并将该节点颜色比较
2. 以二叉排序树的查找算法查找当前树,如果在当前树中找到已存在的节点,更新节点的值,并返回。
3. 否则,创建一个新节点,将其插入到最后一个查找到的叶子节点上,其初始颜色为红色。
4. 如果新插入节点的父节点是黑节点,则没有破坏当前红黑树的性质,直接返回。
5. 如果新插入节点的父节点是红节点,则需要做一些调整。
在TreeMap中,key值的比较可以通过构造TreeMap传入的Comparator实例,如果没有Comparator,则key必须实现Comparable接口作为比较逻辑,key不可以为null。以二叉排序树的算法插入新节点的代码比较简单:
    public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
    private void fixAfterInsertion(Entry<K,V> x) {
        x.color = RED;
        ..
        root.color = BLACK;
    }

TreeMap中红黑树新节点插入后调整

红黑树的调整比较复杂,首先它会从当前节点向上查找,直到当前节点为null,或是root节点,或者当前节点的父节点颜色不是红色,然后根据以下不同情况做处理(设当前节点为C(红色),其父节点为P(红色),其祖先节点为A(黑色),其叔叔节点为U(待定)):
1. P是A的左子树,U节点颜色为红色,此时不管C是节点是P的左子树还是右子树,只需要将P和U设为黑色,A设为红色,则可保证当前局部树符合红黑树定义,把A作为新插入节点重新调整,如果当前树已经是整棵树,则因为根节点为红色,不符合红黑树定义,此时只需要将根节点颜色设置为黑色即可,即fixAfterInsertion()最后一句代码的作用。
2. P是A的左子树,U节点颜色为黑色,C是P的左子树,将P设置为黑色,A设置为红色,并对A做右旋操作。此时C的父节点已变为黑色,循环可以直接退出。
3. P是A的左子树,U节点颜色为黑色,C是P的右子树,此时只需要先对P左旋,然后设置C为黑色,A为红色,并对A右旋,此时P的父节点已变为黑色,循环可以直接退出。
如下图所示:

代码:
        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);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                ....
            }
        }
4. P是A的右子树,U节点颜色为红色,此时不管C是节点是P的左子树还是右子树,只需要将P和U设为黑色,A设为红色,则可保证当前局部树符合红黑树定义,把A作为新插入节点重新调整,如果当前树已经是整棵树,则因为根节点为红色,不符合红黑树定义,此时只需要将根节点颜色设置为黑色即可,即fixAfterInsertion()最后一句代码的作用。
5. P是A的右子树,U节点颜色为黑色,C是P的右子树,将P设置为黑色,A设置为红色,并对A做左旋操作。此时C的父节点以变为黑色,循环可以直接退出。
6. P是A的右子树,U节点颜色为黑色,C是P的左子树,此时只需要先对P左旋,然后设置C为黑色,A为红色,并对A右旋,此时P的父节点已为黑色,循环可以直接退出。
如下图所示:

代码:
        while (x != null && x != root && x.parent.color == RED) {
            if (parentOf(x) == leftOf(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);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }

TreeMap中红黑树节点删除
红黑树的删除类似二叉查找树删除逻辑类似,在对同时有左子树和右子树存在时,TreeMap选择先将要删除的节点替换成其直接后继节点,然后删除其直接后继节点(其直接后继节点不可能同时存在左子节点和右子字节点)。对红黑树,由于红色节点不影响路径计算(性质6),因而对红色节点可以直接删除。然而在删除黑色节点时,如果删除的节点不是树的唯一节点,那么在某些路径上的黑色节点数会发生改变,破坏性质6;如果被删除的唯一子节点为红色,而父节点也为红色,那么性质5被破坏,因为存在红色节点的子节点为红色;如果删除的是根节点,而它的唯一子节点是红色,则性质3被破坏。因而需要做一些调整。
    private void deleteEntry(Entry<K,V> p) {
        modCount++;
        size--;

        // If strictly internal, copy successor's element to p and then make p
        
// point to successor.
        if (p.left != null && p.right != null) {
            Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        
// Start fixup at replacement node, if it exists.
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);

        if (replacement != null) {
            // Link replacement to parent
            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;

            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
        } else { //  No children. Use self as phantom replacement and unlink.
            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;
            }
        }
    }

TreeMap中红黑树删除黑色节点后调整
调整的逻辑分以下步骤来考虑(假设新替换的节点为C,即代码中的x参数,C的父节点为P,C是P的左子节点,C的兄弟节点为S,S的左子树为SL,S的右子树为SR):
1. 如果C为红色,直接将C标记为黑色即可,因为删除的黑节点数被该节点补上,该树已经恢复成一颗红黑树。
2. 如果C为黑色,且C为根节点,直接返回。
3. 如果C为黑色,且S为红色,那么节点P、SL、SR都为黑色,此时设置P为红色,S为黑色,对P左旋,并重新计算S,即S变为SL,即把问题转换为兄弟节点为黑色的情况。图片来自http://blog.csdn.net/v_JULY_v/article/details/6105630,自己画太麻烦了,虽然图片的命名规则和我的不一样,凑合的看把,囧。
 
4. 如果C为黑色,S为黑色,且SL、SR都为黑色,将S设置为红色,P赋值给C,重新计算。

5. 如果C为黑色,S为黑色,且SL为红色,SR为黑色,那么设置SL为黑色,S为红色,对S右旋,重新设置S为SL。

6. 如果C为黑色,S为黑色,且SR为红色,SL为任一颜色,则把S节点的颜色设置为P节点的颜色,设置P节点的颜色为黑色,SR节点的颜色为黑色,对P节点右旋,算法结束。
 
当C为P的右子节点时,其逻辑和以上对称,不再赘述。
    private void fixAfterDeletion(Entry<K,V> x) {
        while (x != root && colorOf(x) == BLACK) {
            if (x == leftOf(parentOf(x))) {
                Entry<K,V> sib = rightOf(parentOf(x));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateLeft(parentOf(x));
                    sib = rightOf(parentOf(x));
                }

                if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(rightOf(sib)) == BLACK) {
                        setColor(leftOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(parentOf(x));
                    x = root;
                }
            } else { // symmetric
                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中红黑树节点查找
红黑树的节点查找同二叉查找树逻辑,不再赘述。这里有一点不太明白:getEntryUsingComparator()方法注释中说它从getEntry()方法提取出来是为了性能上的考虑,这是为什么?
    /**
     * Version of getEntry using comparator. Split off from getEntry
     * for performance. (This is not worth doing for most methods,
     * that are less dependent on comparator performance, but is
     * worthwhile here.)
     
*/
    final Entry<K,V> getEntryUsingComparator(Object key)

TreeMap中其他方法
TreeMap中其他方法实现比较直观,只要理解了红黑树,基本上很容易理解,不再赘述。

参考链接:
http://blog.csdn.net/v_JULY_v/article/details/6105630
http://blog.csdn.net/zhaojinjia/article/details/8120403
http://blog.csdn.net/eric491179912/article/details/6179908
http://dongxicheng.org/structure/red-black-tree/
posted on 2013-10-26 18:41 DLevin 阅读(2796) 评论(0)  编辑  收藏 所属分类: Core Java

只有注册用户登录后才能发表评论。


网站导航: