因为看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字段：

TreeMap中红黑树节点插入
红黑数的插入分以下步骤：
1. 如果当前为空树，插入节点直接作为根节点，并将该节点颜色比较
2. 以二叉排序树的查找算法查找当前树，如果在当前树中找到已存在的节点，更新节点的值，并返回。
3. 否则，创建一个新节点，将其插入到最后一个查找到的叶子节点上，其初始颜色为红色。
4. 如果新插入节点的父节点是黑节点，则没有破坏当前红黑树的性质，直接返回。
5. 如果新插入节点的父节点是红节点，则需要做一些调整。
在TreeMap中，key值的比较可以通过构造TreeMap传入的Comparator实例，如果没有Comparator，则key必须实现Comparable接口作为比较逻辑，key不可以为null。以二叉排序树的算法插入新节点的代码比较简单：

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的父节点已变为黑色，循环可以直接退出。
如下图所示：

代码：
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的父节点已为黑色，循环可以直接退出。
如下图所示：

代码：

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

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的右子节点时，其逻辑和以上对称，不再赘述。

TreeMap中红黑树节点查找
红黑树的节点查找同二叉查找树逻辑，不再赘述。这里有一点不太明白：getEntryUsingComparator()方法注释中说它从getEntry()方法提取出来是为了性能上的考虑，这是为什么？

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

参考链接：