红黑树
红黑树是一中重要的二叉平衡树 这里主要以JAVA TreeSet中的源码了解其插入节点和删除节点的实现，红黑树主要以维护其一下五个原则为目标进行变色和旋转：
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
1，增加一个节点:
private void fixAfterInsertion(Entry x) {
x.color = RED;//要保持第五个原则，则新插入的节点必须为红色
//x的父节点为红色才需要以下动作
while (x != null && x != root && x.parent.color == RED){//一直循环
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //如果x的父节点是祖父节点是左节点（在左子树）
Entry y =rightOf(parentOf(parentOf(x)));//获取右叔父节点
if (colorOf(y) == RED) {//如果叔父节点同样为红色
setColor(parentOf(x),BLACK);//x的父节点改为黑色
setColor(y, BLACK);//叔父节点置为黑色
setColor(parentOf(parentOf(x)), RED);//祖父节点置为红色
x =parentOf(parentOf(x));//祖父节点赋值给x
} else {//如果叔父节点为黑色
if (x ==rightOf(parentOf(x))) {//自己是父节点的右节点
x = parentOf(x);//x的父节点赋值给x
rotateLeft(x);//左旋x
}
setColor(parentOf(x),BLACK);//x的父节点置为黑色
setColor(parentOf(parentOf(x)), RED);//x的祖父节点置为红色
rotateRight(parentOf(parentOf(x)));// 这时右旋祖父节点
}
} else {//如果x的父节点是祖父节点是右节点（在右子树）
Entry 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));把祖父节点赋值给x
} else {//如果左叔父节点为黑色
if (x ==leftOf(parentOf(x))) {//自己是父节点的左节点
x = parentOf(x);//x父节点赋值给x
rotateRight(x);//x右旋
}
setColor(parentOf(x),BLACK);//x的父节点设置为黑
setColor(parentOf(parentOf(x)), RED);//x的祖父节点设置为红
rotateLeft(parentOf(parentOf(x)));//右旋祖父节点
}
}
}
root.color = BLACK;//根节点设置为黑色
}
2，删除一个节点
private void fixAfterDeletion(Entry x) {
while (x != root && colorOf(x) == BLACK) {//删除黑节点才处理
if (x == leftOf(parentOf(x))) {//是父节点的左节点
Entry sib =rightOf(parentOf(x));//找到父节点的右节点也就是兄弟节点
if (colorOf(sib) == RED) {//兄弟节点是红色
setColor(sib, BLACK);//兄弟节点设置为黑色
setColor(parentOf(x),RED);//x的父节点设置为红色
rotateLeft(parentOf(x));//x的父节点左旋
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) ==BLACK) {//如果sib的左右子节点都是黑色
setColor(sib, RED);//设置sib为hongse
x = parentOf(x);//x的父节点赋值为x
} else {
if (colorOf(rightOf(sib))== BLACK) {//sib的右节点是黑色，左节点为红
setColor(leftOf(sib),BLACK);//设置sib的左节点为黑色这时sib这棵树的左子树比右子树黑节点多需要右旋，把多出来的这个节点变为sib树的根节点
setColor(sib, RED);//设置sib节点为红色
rotateRight(sib);//右旋sib节点
sib =rightOf(parentOf(x));//x的右兄弟节点赋值给sib
}
setColor(sib,colorOf(parentOf(x)));//sib的颜色设置为x父节点的颜色
setColor(parentOf(x),BLACK);//x的父节点设置为黑
setColor(rightOf(sib),BLACK);//sib的右子节点设置为黑
rotateLeft(parentOf(x));//左旋x的父节点
x = root;
}
} else { // symmetric 和上面的一样
Entry 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);
}
网友评论