困惑了很久的红黑树========来个了断吧
本文主要是为了描述旋转的原则,所以,至于红黑树的数据结构,红黑树的基本准则,不在强调,,红黑树困惑的就是这旋转的过程.!!!
画红黑树很简单的画图工具: https://sourceforge.net/projects/dia-installer/?source=typ_redirect11
参靠博客: http://www.cnblogs.com/skywang12345/p/3245399.html
https://www.cnblogs.com/xrq730/p/6867924.html
三大原则:前提是红黑树的五个性质(根是黑的,空节点是黑的,红色节点不连续)
1.当前节点的父节点是红色,且叔叔节点也是红色
将父节点设为黑色
将叔叔设置成 黑色,
祖父节点变红,
将祖父节点设为"新的当前节点 ”（红色节点），进行操作
2.父节点是红,叔叔是黑,且当前节点是父节点的右孩子
将父节点作为"新的当前节点 ”,
以"新的当前节点 ”为支点进行左旋
3.父节点是红,叔叔是黑,且当前节点是父节点的左孩子
将父节点设为"黑色",
将祖父节点设为红色,
以"祖父节点进行"右旋
比如
这是第三点,右旋
左旋加右旋
左旋,后右旋
对应的java 代码
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//1.当前节点的父节点 是 祖父节的左节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));//叔叔(右)节点
if (colorOf(y) == RED) {//叔叔(右)节点是红色?
// 1.1父节点是红色,叔叔节点也是红色,设置父节点和叔叔节点都为黑色
setColor(parentOf(x), BLACK);//设置父节点为黑色
setColor(y, BLACK);//
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {//叔叔(右)节点是黑色
// 1.2父节点是红色,叔叔节点是黑色
if (x == rightOf(parentOf(x))) {
//2.1 当前节点是右节点,则当前节点父节点左转
x = parentOf(x);//
rotateLeft(x);//左旋
}
setColor(parentOf(x), BLACK);//父节点变黑
setColor(parentOf(parentOf(x)), RED);//祖父节点变红
rotateRight(parentOf(parentOf(x)));
}
}
增加告一段落,,
删除真是过于复杂,遍历的时候采用的是中序遍历,找到最小的,然后左->父->右