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/