TreeMap是基于红黑树实现的二叉树.
红黑树是一种平衡二叉树(个人理解是它总是能够将数据均匀地排布,使得树的形状能够呈三角形展示,而不至于单边倒或者干脆成为线性链表
- 以下来自于百度
- 红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
- 原则1. 节点是红色或黑色。
- 原则2. 根节点是黑色。
- 原则3 每个叶节点（NIL节点，空节点）是黑色的。
- 原则4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 原则5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
- 这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
- 要知道为什么这些特性确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长.
TreeMap的插入部分.##
网上百度了很多有关于红黑树的知识,很多都介绍了红黑树插入违反原则的各种情况,然后针对这些情况进行解答,篇幅巨长,反正我是看懵了.但是借着TreeMap的源码,我初步知道了违反原则后该怎么样处理,红黑树的插入还是有迹可循的.
下面我画了一张图,用于展示红黑树的构建过程.依次插入50,3,4,51,52.
可能对于左旋和右旋有点懵,我从网上找了两张gif图.
图片来自http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html
我会和TreeMap的fixAfterInsertion方法结合在一起解释上面的每一个步骤
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {//最外层递归判断
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//a.判断当前节点的父节点是否为祖父节点的左节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) { //b.判断当前节点的叔节点是否为红色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else { //c.叔节点为空或者为黑色
if (x == rightOf(parentOf(x))) { //d.判断当前节点是否为父节点的右节点
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else { //e.当前节点的父节点为祖父节点的右节点
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) { //f.判断当前节点的叔节点是否为红色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else { //g.叔节点为空或者为黑色
if (x == leftOf(parentOf(x))) {//h.判断当前节点是否为父节点的左节点
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
- fixAfterInsertion方法执行时.每次都会将新加的节点设为红色,将根节点设为黑色.
- 步骤1,插入节点50作为根节点,执行fixAfterInsertion方法后直接将其染黑.
- 步骤2,插入节点3,因为比50小,作为50的左节点.执行fixAfterInsertion方法时,首先将3染红,因为3的父节点是黑色的,直接跳过while循环中的判断.
- 步骤3,插入节点4,因为比50小,选择放入50的左边部分.比3大,作为3的右节点.执行fixAfterInsertion方法将4染红,while条件判断发现4的父节点(3)为红色且满足其他条件,于是进行一系列复杂的判断.首先进行代码注释的a判断,它的父节点是祖父节点的左节点,条件成立.进入b判断,发现他的叔叔节点(即祖父节点(50)的右节点)不为红色,进入c判断进入步骤4
- 步骤4,进入d判断,判断当前节点(4)是否为父节点(3)的右节点,如图成立.以父节点(3)为中心进行左旋,结果是父节点(3)和子节点(4)的关系相互转换.当前节点x变成了3,这还没完,因为两个节点还是红色的,违反原则4.进入步骤5
- 步骤5,执行c判断成立后剩下的三段代码,将父节点(3)染黑,将祖父节点(50)染红,然后进入步骤6
- 步骤6,以祖父节点(50)为中心进行右旋,最后判断当前节点3是否还要进行处理,这里3的父节点4是黑色的,直接结束.最后产生一个稳定的结构,(左旋和右旋多看看gif图,马上会有感觉)
- 步骤7,插入51,在结构重新变换的基础上作为50的右节点,又违反了原则4.进入步骤8
- 步骤8,判断e成立,当前节点(51)的父节点(50)为祖父节点(4)的右节点,判断f也成立,叔节点(3)为红色.执行判断f成功后的代码,将父节点(50)和叔节点(3)都设为黑色,将祖父节点(4)设为红色,最后设祖父节点为当前节点x继续进行while循环(若该祖父节点不为根节点,那么它的父节点可能为红色,会违反原则4,需要重复执行步骤8,直至不违反原则4),当然在这里4为根节点,跳出循环,在最后 root.color = BLACK被重新染成黑色.
- 步骤9,插入52,又违反了原则4,进入步骤10
- 步骤10,父节点(51)为为祖父节点(50)的右节点.判断e成立,52没有叔节点,所以判断g成立(叔节点为空或者为黑色).判断h不成立,当前节点为父节点的右节点.于是直接执行余下三行代码.将父节点(51)染黑,祖父节点(50)染红.以祖父节点(50)为中心进行左旋.最后达到如上图所示结构.
每一个步骤说的可能有点多,不好理解,我也是木木地坐在电脑前写写画画弄了好一阵子才搞懂,希望能为阅读者带来一点启发.
上面十个步骤是我不看代码直接一步步画出来的,最后根据debug代码来验证正确性.我也得到了规律.- 当两个红色节点相遇时,就要调整结构.这时候就要看作为子节点的叔节点是红是黑还是不存在.
- 若为红色,那么很简单,将叔节点和父节点都染黑,将祖父节点染红.再判断祖父节点是否和它的父节点有冲突,递归循环直到没有冲突.
- 若为黑或者无,那么就看子节点,父节点,祖父节点是否在一条线上(父节点为祖父节点的左节点,子节点为父节点的左节点).若不成立,还有以父节点为中心进行相应的旋转(祖父二者在左叉树,进行右旋,祖父二者在右叉树进行左旋),最后的结果是使祖孙三代在一条线上.最后将祖父节点染红,父节点染黑,以祖父节点为中心进行旋转置换两者的位置(旋转方位的判断同上,爸爸当爷爷,爷爷成为爸爸的儿子,儿子成为爷爷的兄弟).
TreeMap的删除部分部分.##
当程序从排序二叉树中删除一个节点之后，为了让它依然保持为排序二叉树，程序必须对该排序二叉树进行维护。维护可分为如下几种情况：
- 被删除的节点是叶子节点，则只需将它从其父节点中删除即可。
- 被删除节点 p 只有左子树，将 p 的左子树 pL 添加成 p 的父节点的左子树即可(顶替p的位置,为左子树)；被删除节点 p 只有右子树，将 p 的右子树 pR 添加成 p 的父节点的右子树即可((顶替p的位置,为右子树))。
- 若被删除节点 p 的左、右子树均非空，有两种做法：
- 将 pL 设为 p 的父节点 q 的左或右子节点（取决于 p 是其父节点 q 的左、右子节点），将 pR 设为 p 节点的中序前趋节点 s 的右子节点（s 是 pL 最右下的节点，也就是 pL 子树中最大的节点）。
- 以 p 节点的中序前趋或后继替代 p 所指节点，然后再从原排序二叉树中删去中序前趋或后继节点即可。（也就是用大于 p 的最小节点或小于 p 的最大节点代替 p 节点即可)。
TreeMap中主要使用第二种方法,它用p节点的后继替代p所指节点.在被删除节点双子树俱在前提下分析.
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {//双子树俱全,那么只能执行里面的方法
Entry<K,V> p = t.right;
while (p.left != null)//while循环寻找后继节点,并返回.如果没有就返回右子节点.如果是后继节点,那么肯定是叶子节点.如果是右子节点,那么不一定,说不定右子节点后还有节点.
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
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原来的内容已经被删除
p.value = s.value;
p = s;//p的引用指向s,s将被删除.
} // p has 2 children
// Start fixup at replacement node, if it exists.
Entry<K,V> replacement = (p.left != null ? p.left : p.right);//这里的replacement适合种情况
//1.只有左子树或者右子树的节点,replacement得到右子树或左子树.这样可以通过子树替代被删除的节点
//2.双子树俱在,上面已经处理过了,将会得到后继节点,或者右子节点.一般replacement 为空,但是不排除,后继节点有右子树,右子节点还有右子节点.
//3.双子树俱无,直接删了就好了,但是要考虑节点是黑的情况.
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;
}
}
}
我先着重梳理第二种情况,且设p为后继节点.
这里要着重注意的是要被删除的这个后继节点的颜色,如果节点是黑色的,那么删除它必然会破坏红黑树的结构.
你可以想象这个黑色的后继节点x一旦被删除的话,含有x的路径黑色高度会比其他小1.为了平衡,肯定要把别的路径都去掉一个黑色节点: 主要思路:"攘外必先安内",先把兄弟的黑节点去掉一个先,这样我们一家子都一样了.但是旁边叔叔一家比我们多,那就把叔叔一家削个黑色节点(黑高度一致),削谁方便?当然是叔叔啦.好了,我们爷爷这一脉都平衡了,但是隔壁叔公家多了个黑节点,把叔公的削一个掉.以此类推,直到上面一代没有兄弟(根节点),如下图所示,删除一个A节点,H失去一层黑色变红,A的叔叔节点O也失去一层黑色变红.
当然,可能兄弟是红的,削不出黑的.这里就遇到一种情况:x的兄弟节点w为红色的.那么w的子节点都是黑色的(null也算黑的).那放低身段和侄子比较(通过旋转).此处必有图(第一种方法).曾经的侄子变成现在的兄弟.
与上图不同,这里我要删除G节点,所以把G节点的兄弟节点转换为黑色节点,进入下面几种情况.
这样又能愉快地和兄弟作对了,这里也有几种情况:
1.兄弟的子树都是黑的,这样很简单,把兄弟直接改成红的就行了.然后就和主要思路一致.把不平衡的问题抛给父节点,一步一步往上走,如果父节点是红色的,那正好,直接把红变成黑的,不用大费周章再去搞别的兄弟节点了.
这种情况不适用于p为后继节点.
2.兄弟的左子树红,右子树黑的,这就要用旋转了,经过处理后会变为为下一种情况,因为.如果p为后继节点并不会出现这种情况,所以忽略.
3.兄弟是黑色的,右孩子是红色的,或者为空.
回过头来看一下deleteEntry剩下部分,即replacement不为空的情况
Entry<K,V> replacement = (p.left != null ? p.left : p.right);//这里的replacement适合种情况
//1.只有左子树或者右子树的节点,replacement得到右子树或左子树.这样可以通过子树替代被删除的节点
//2.双子树俱在,上面已经处理过了,将会得到后继节点,或者右子节点.一般replacement 为空,但是不排除,后继节点有右子树,右子节点还有右子节点.
//3.双子树俱无,直接删了就好了,但是要考虑节点是黑的情况.
if (replacement != null) {//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;//上面几步以如下图的方式用replacement节点取代非叶子节点的successor(p)
// 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.源码已经注释:p没有子节点的情况,具体情形上面已经描述过
//如果这个节点是叶子节点,那么先处理节点为黑的情况,最后才把这个节点删除.
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;
}
}
之前兄弟节点为黑的两种情况没有用图来解释,现在放到这里来展示.
1.兄弟的子树都是黑的,这样很简单,把兄弟直接改成红的就行了.然后就和主要思路一致.把不平衡的问题抛给父节点,一步一步往上走,如果父节点是红色的,那正好,直接把红变成黑的,不用大费周章再去搞别的兄弟节点了.
2.兄弟(为右子树)的左子树红,右子树黑的或者兄弟(为左子树)的左子树黑,右子树红,这就要用旋转了,经过处理后会变为为第三种情况:兄弟(为右子树)是黑色的,右孩子是红色的,或者为空,或兄弟(为左子树)是黑色的,左孩子是红色的,或者为空
//fixAfterDeletion的部分方法,调整颜色那步开始修复红黑树,这之前8已经被移除.
while (x != root && colorOf(x) == BLACK) {
if (x == rightOf(parentOf(x))) {//9为右子节点
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) {//兄弟sib的左子节点为黑
setColor(rightOf(sib), BLACK);//红色的3染黑
setColor(sib, RED);//2染红
rotateLeft(sib);//以2为中心左旋转
sib = leftOf(parentOf(x));//设3为兄弟sib节点
}
setColor(sib, colorOf(parentOf(x)));//将3染红
setColor(parentOf(x), BLACK);//4染黑
setColor(leftOf(sib), BLACK);//2染黑
rotateRight(parentOf(x));//以4为中心右旋转
x = root;//最后将根节点染黑
}
}
}
setColor(x, BLACK);
这里再总结一下删除部分.
1.如果被删除的节点能够找到后继节点,那么以后继节点的内容替换被删除节点.因为后继节点是叶子节点,所以replacement=null.若该后继节点为黑色,那么向上递归地平衡兄弟节点的黑高度,直到 1.根节点, 2.某一层的兄弟节点为红色,则把兄弟为红色的情况转换为兄弟为黑色(没猜错的话只会遇到第三种情况),最后根据兄弟的子节点来平衡红黑树.最后删除后继节点
2.如果被删除的节点能够找不到后继节点,那么直接用它的右子节点(左子节点)的内容替换自身,先删除右子节点(左子节点).因为右子节点(左子节点)可能还有子节点,所以
replacement!=null,同样的,replacement的兄弟为红色就进行转换(1,2,3三种情形都会遇到).
- 如果被删除的节点能够找到后继节点,那么fixAfterDeletion方法执行完才会删除后继节点.
- 如果被删除的节点能够找不到后继节点,那么会先删除被删除的节点的子节点a,根据a是否为黑执行fixAfterDeletion方法.
学习过程中参考博文:
java提高篇（二七）-----TreeMap
java中treemap和treeset实现（红黑树）