首页 > 代码库 > jdk源码分析红黑树——插入篇
jdk源码分析红黑树——插入篇
红黑树是自平衡的排序树，自平衡的优点是减少遍历的节点，所以效率会高。如果是非平衡的二叉树，当顺序或逆序插入的时候，查找动作很可能会遍历n个节点
红黑树的规则很容易理解，但是维护这个规则难。
一、规则
1.每个节点要么是红色、要么是黑色
2.根节点一定是黑色
3.红色节点不可以连续出现（父节点、子节点不可同时为红）
4.从任意节点出发，到树底的所有路线，途径的黑节点数量必须相同
在修改红黑树的时候，切记要维护这个规则。一般默认插入红色节点（除非是root节点），插入后再进行旋转和颜色变换
二、旋转、变换技巧
关于旋转和颜色变换有几种情况：
1.插入root
不会违反规则
2.父黑
插入节点的父节点是黑色，不会违反规则
3.父红
插入节点的父节点是红色，一定违反规则（违反规则3）（因为默认插入红色节点），此时就需要修复红黑树了。这种情况下又细分为几种情况
4.父红，叔红
父节点和叔节点均为红色（违反规则3）
这种情况下就把父节点和叔节点都改成黑色，然后曾节点改为红色
可是此时，如果曾节点是根节点的话，那么必须将曾节点转为黑色。
所以一般在修补红黑树的方法的最后，会强制将根节点转为黑色
这种情况可能又会导致5.1的情况
5.1父红，叔黑，外侧子孙
父节点是红色，叔节点是黑色或者null，且新增节点是曾节点的外侧子孙（违反规则3）
外侧子孙：A点是B点的左-左-....-左或者右-右-..-右，那么A是B的外侧子孙，否则A是B的内侧子孙
符号解释：
N:新插入的节点，P：父节点，G：曾节点，U：叔节点
此时就需要将G点旋转，这里是右旋
不过此时颜色还有冲突，还要调整一下颜色
将P与G的颜色对调，既P变为黑色，G变为红色
总结一下，5.1的步骤：
step1:P->黑
step2:G->红
step3:将G旋转
5.1.1关于旋转的方向
旋转有左旋右旋，具体是看父节点是曾节点的左节点还是右节点
P是G的左节点，那么就将Ｇ右旋（因为要把Ｐ移动到Ｇ的位置）
P....G....右节点.....................Ｇ左旋
5.2父红，叔黑，内侧子孙
父节点是红色，叔节点是黑色或者null，且新增节点是曾节点的内侧子孙（违反规则3）
外侧子孙：A点是B点的左-左-....-左或者右-右-..-右，那么A是B的外侧子孙，否则A是B的内侧子孙
5.2跟5.1只有一个内侧外侧的区别。
内侧子孙比外侧要多做一次旋转。目的是把内侧子孙旋转成外侧子孙来做
这里的N就是G的内侧子孙，现在要把N变成G的外侧子孙。
将P旋转（这里是左旋），让N旋转到P的位置
之后的步骤就是和5.1处理外侧子孙的一样了。
5.2.1内侧转外侧的旋转方向
根据P点和N的相对位置，当N是P的右节点，则将P左旋，否则将P右旋
目的是让N旋转到P的位置
总结情况：
1.插入的是根节点，不违反规则
2.插入点的父节点是黑色，不违反规则
3.插入点的父、叔节点是红色，将父、叔转成黑色，然后将曾节点转成红色
4.插入点的父是红色、叔节点是黑色或者null，通过旋转和转变颜色，注意内侧外侧子孙！
三、分析TreeMap源码
jdk中的红黑树实现是TreeMap。
每次put之后，都会调用这个方法去维护红黑树的规则
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)))) {//父节点是曾节点的左节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {//父、叔节点都是红色，情况4
//将父节点和叔节点变为黑色，曾节点变为红色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {//父节点是红色，叔节点是黑色或者null
if (x == rightOf(parentOf(x))) {//内侧子孙
x = parentOf(x);
rotateLeft(x);//旋转成外侧子孙
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(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)));
}
}
}
root.color = BLACK;//强制将根节点转成黑色
}
查看原文：http://blog.zswlib.com/2016/11/01/jdk%e6%ba%90%e7%a0%81%e5%88%86%e6%9e%90%e7%ba%a2%e9%bb%91%e6%a0%91-%e6%8f%92%e5%85%a5%e7%af%87/
jdk源码分析红黑树——插入篇
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。