因为看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;
// 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;
cmp = k.compareto(t.key);
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);
}
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的父节点已为黑色，循环可以直接退出。
entry<k,v> y = leftof(parentof(parentof(x)));
if (x == leftof(parentof(x))) {
rotateright(x);
rotateleft(parentof(parentof(x)));
treemap中红黑树节点删除
红黑树的删除类似二叉查找树删除逻辑类似，在对同时有左子树和右子树存在时，treemap选择先将要删除的节点替换成其直接后继节点，然后删除其直接后继节点（其直接后继节点不可能同时存在左子节点和右子字节点）。对红黑树，由于红色节点不影响路径计算（性质6），因而对红色节点可以直接删除。然而在删除黑色节点时，如果删除的节点不是树的唯一节点，那么在某些路径上的黑色节点数会发生改变，破坏性质6；如果被删除的唯一子节点为红色，而父节点也为红色，那么性质5被破坏，因为存在红色节点的子节点为红色；如果删除的是根节点，而它的唯一子节点是红色，则性质3被破坏。因而需要做一些调整。
private void deleteentry(entry<k,v> p) {
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.
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);
if (colorof(rightof(sib)) == black) {
setcolor(leftof(sib), black);
setcolor(sib, red);
rotateright(sib);
sib = rightof(parentof(x));
setcolor(sib, colorof(parentof(x)));
setcolor(rightof(sib), black);
x = root;
} else { // symmetric
entry<k,v> sib = leftof(parentof(x));
rotateright(parentof(x));
sib = leftof(parentof(x));
if (colorof(rightof(sib)) == black &&
colorof(leftof(sib)) == black) {
if (colorof(leftof(sib)) == black) {
setcolor(rightof(sib), black);
rotateleft(sib);
sib = leftof(parentof(x));
setcolor(leftof(sib), black);
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/