红黑树也是一种自平衡的二叉搜索树
红黑树必须满足一下5条性质
节点是RED或者BLACK
根节点是BLACK
叶子节点(外部节点,空节点)都是BLACK
RED节点的子节点都是BLACK
RED节点的parent都是BLACK
从根节点到叶子节点的所有路径上不能有2个连续的RED节点
从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点
以下即为一颗红黑树:
如上图所示:
? 上面的是红黑树,下面是与之等价的2-3-4树
// 染色
private Node<E> color(Node<E> node, boolean color) {
if (node == null) return node;
((RBNode<E>)node).color = color;
return node;
}
// 将该节点染为红色
private Node<E> red(Node<E> node) {
return color(node, RED);
}
// 将该节点染为黑色
private Node<E> black(Node<E> node) {
return color(node, BLACK);
}
// 返回该节点的颜色
private boolean colorOf(Node<E> node) {
return node == null ? BLACK : ((RBNode<E>)node).color;
}
// 该节点是否为黑色
private boolean isBlack(Node<E> node) {
return colorOf(node) == BLACK;
}
// 该节点是否为红色
private boolean isRed(Node<E> node) {
return colorOf(node) == RED;
}
public Node<E> sibling(){
if(isLeftChild()){
return parent.right;
}
if(isRightChild()){
return parent.left;
}
return null;
}
已知
建议新添加的节点默认为RED,这样能让红黑树的性质尽快满足
如果添加的是根节点,染成BLACK即可
有4中情况满足红黑树的性质4:parent为BLACK
同样也满足4阶B树的性质
因此不用做任何处理
如下图所示,如果我们要添加的是红色节点的话,又因为任何添加其实都是在叶子节点处添加,所以我们不需要对这种情况进行任何的处理,如图中的40,78,82,90都是这种情况
有 8 种情况不满足红黑树的性质 4 :parent 为 RED( Double Red )
接下来我们对其进行一一解析
? 我们先来看这种情况,我们要在节点50的左边添加一个新的节点,或者我们要在72的右边添加一个新的节点。那么我们要做的事情很简单。我们知道新添加的这俩个节点,他们的父节点都是红色,这样的话,就会有连续的俩个节点都为红色了,那么就违背了红黑树的性质,所以我们要进行一定的调整。
判定条件:uncle(叔父节点)不是RED
? 其实调整的过程非常的简单:
? 也就是:
parent染成BLACK,grand染成RED
grand进行单选操作
LL:右旋转
RR:左旋转
旋转后如图所示:
? 我们再看这种情况,这种情况下,新添加的节点处于grand.right.left或者是grand.left.right,也就是我们下图所要添加的节点48或者节点74。对于这种情况,其实处理的方法也很简单,那就是我们要将新添加的节点染黑,然后将它的祖父节点染成红色,并且我们要进行旋转操作。对于下图添加节点48的情况,我们要将它的父节点进行右旋,然后将祖父节点进行左旋;对于下图中添加节点74的情况,我们只需要将它的父节点左旋,然后将它的祖父节点进行右旋就可以了。
判定条件:uncle不是RED
旋转之后的样子:
? 对于这种情况,我们添加元素的时候,肯定会发出上溢的情况,这个时候我们就要将节点进行向上合并的操作。如下图我们要添加新的节点10的时候,我们就需要进行一系列的操作。
? 首先,我们要将取出中间位置的节点向上合并,我们这里取节点25向上合并,做完这个操作之后,我们将25这个节点染成红色,作为是新添加的节点一样进行处理。然后因为25已经向上合并了,所以原先25节点的左子树和右子树分裂,所以我们要将新添加的节点的父节点,也就是下图的17节点染成黑色,然后我们将下图的33节点也染成黑色,因为现在的33节点也是一个叶子节点,我们知道红黑树里的叶子节点都是黑色的。
判定条件:uncle是RED
parent、uncle染成BLACK
grand向上合并
grand向上合并时,可能继续发生上溢
若上溢持续到根节点,只需将根节点染成BLACK
添加节点处理后如图所示:
? 对于这种情况,其实是和我们上面说的是相似的。对于我们要添加的新节点36来说,如果我们要添加新节点,那么必然会发生上溢的现象。所以我们同样的要选取中间位置的节点进行向上合并,这里我们取节点25进行向上合并,同样的,我们将节点25染成红色,当成新添加的节点进行处理。然后原来25节点的左右子树进行分裂。这个时候,我们应该将parent、uncle染成黑色。
判定条件:uncle是RED
? 在这里我就不一一进行赘述了,下面的情况大家可以自己进行理解
判定条件:uncle是RED
判定条件:uncle是RED
有3种情况
我们来说一说,为什么拥有2个RED子节点的BLACK节点的这种情况。如下图,假如我们要删除的是节点55,我们要处理的情况就是找到节点55的前驱结点或者后继节点进行替换节点55,然后将它的前驱结点或者后继节点删除。也就是说,如果我们要删除的节点是55的话,其实我们删除的就是它的前驱结点或者后继节点。
我们来简单的叙述一下这种操作,如下图,我们要删除节点46和节点76,因为要替代他们俩位置的都是红色的子节点50和72,所以进行删除的时候我们只需要将俩个节点删除,然后将节点50和72染成黑色就好了
操作之后的样子为:
原文:https://www.cnblogs.com/coderD/p/14612349.html