Java Core系列之TreeMap实现详解-阿里云开发者社区

因为看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/

Java Core系列之TreeMap实现详解

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件