锐客网

  1. 首页 > it技术 > >

红黑树

红黑树
红黑树是一中重要的二叉平衡树 这里主要以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);
}

    推荐阅读


    上一篇：一钵米饭的心伤

    下一篇：再见，我不能做个孩子了