红黑树（Red Black Tree）

2021-01-18 本文已影响0人 code希必地

1、概述

红黑树也是一种自平衡的二叉搜索树。

红黑树的5条性质

1、节点只能是RED或BLACK。
2、根节点只能BLACK。
3、叶子节点（外部节点，空节点）都是BLACK。
4、RED节点的子节点必须是BLACK。

RED节点的父节点是BLACK。

从根节点到叶子节点的所有路径都不能有连续的两个RED节点。

5、从任一节点到叶子节点 的所有路径都包含相同个数的BLACK节点。
红黑树.png
上图就是一棵红黑树，它满足红黑树的5条性质。
空节点.png
上图空节点并不是真实存在的，它是假想出来的，它就是我们上面所说的叶子节点。

请问下图中的二叉树是红黑树吗？

image.png

它满足如下几条性质：

节点是红色的或黑色的。

根节点是黑色的。

叶子节点都是黑色的。

红色节点的子节点是黑色的。

然而它并不满足从任一节点到叶子节点所有路径上都有相同数目的黑色节点。

image.png

上图中绿色路径上的黑色节点的数目是2个，其他路径上黑色数目都是3个。

2、红黑树的等价变换

image.png

1、红黑树和 4阶B树（2-3-4树）具有等价性。
2、将红黑树的BLACK节点和它的RED子节点融合在一起，形成一个B树节点。
3、根据2可知，红黑树中黑色节点的个数和其等价B树的所有节点的总个数相等。
注意：3阶B树（2-3树）并不能完美匹配红黑树的所有情况，所以不能用2-3树和红黑树进行类比。
image.png

红黑树 VS 2-3-4树

image.png

和上述4棵红黑树等价的4阶（2-3-4）B树，如下图

image.png

3、添加

3.1、辅助方法

前面我们说了红黑树是一个自平衡的二叉搜索树，所以在设计上红黑树需要继承二叉搜索树的，而且我们需要在Node增加一个新的属性color来记录节点的颜色。

public class RBTree<E> extends BST<E> {
    public static final boolean RED = true;
    public static final boolean BLACK = false;
    
    public static class RBNode<E> extends Node<E> {
        public boolean color;
        public RBNode(E element, Node<E> parent) {
            super(element, parent);
        }
    }
}

为了方便后面的添加、删除，我们增加一些辅助方法。

/**
 * 获取节点的颜色
 */
public boolean colorOf(Node<E> node) {
    return node == null ? BLACK : ((RBNode) node).color;
}

/**
 * 判断节点是否是黑色
 */
public boolean isBlack(Node<E> node) {
    return colorOf(node) == BLACK;
}

/**
 * 判断节点是否是红色
 */
public boolean isRed(Node<E> node) {
    return colorOf(node) == RED;
}

/**
 * 对节点进行染色
 * 
 * @return 返回染色后的节点
 */
public RBNode<E> color(Node<E> node, boolean color) {
    if (node != null)
        ((RBNode) node).color = color;
    return ((RBNode) node);
}

/**
 * 将节点染成黑色
 */
public RBNode<E> black(Node<E> node) {
    return color(node, BLACK);
}

/**
 * 将节点染成红色
 */
public RBNode<E> red(Node<E> node) {
    return color(node, RED);
}

还需要增加一个获取兄弟节点的方法。

public Node<E> sibling() {
    if (isLeftChild()) {
        return parent.right;
    }
    if (isRightChild()) {
        return parent.left;
    }
    return null;
}

3.2、添加节点

1、B树中添加的节点一定是叶子节点。
2、4阶B树的元素的个数1 <= x <= 3。
3、建议新添加的节点默认是红色的，这样就能满足（1、2、3、5）四条性质，性质四不一定满足。
4、如果添加的根节点，那么将其染成BLACK即可。
由于红黑树是等价于4阶B树的，而且B树的节点是将红黑树的黑色节点和其红色子节点融合而成的，而且B树的元素个数不超过3个，则在添加前只会有下面4种情形
image.png

3.2.1、添加的所有情况

而添加元素又可细分为如下12种情况
image.png

1、4种情况不需要任何处理

上面12种情况有4种情况是满足性质4的。即：当添加节点的parent是黑色。

同样也满足4阶B树的性质，因此这4种情况不要做任何处理。

其他8种情况是不满足性质4的，即添加节点的parent为红色（Double Red）

2、4种情况属于B树上溢

添加节点的父节点为RED

当添加节点的uncle节点为红色时，属于B树上溢的情况，如下图前4种就属于B树上溢的情况。
image.png
解决方案如下：

当uncle节点是RED时

1、parent、uncle节点染成黑色

2、祖父节点grand向上合并
然后染成RED，当做新添加的节点进行处理。
image.png

3、祖父节点grand向上合并，可能继续发生上溢
若上溢持续到根节点，只需将根节点染成BLACK

示例
添加元素10
image.png
添加节点的parent是红色，且uncle节点为红色，所以符合上溢情况。将parent节点17和uncle节点33染成黑色，将祖父节点grand25向上合并。
image.png
grand向上合并并染成了红色，将节点25作为新添加的节点，其父节点是红色的，uncle节点红色了，所以依然发生了上溢。
将父节点38、uncle节点80染成黑色，祖父节点55向上合并，并染成红色，由于祖父节点55是根节点，所以要再将其染成黑色。
image.png

3、添加-修复性质4-LL/RR

添加节点的父节点为RED

image.png
解决方案如下：

添加节点的uncle节点为BLACK

parent节点染成BLACK，祖父节点染成RED

2.对grand进行单选操作
a.LL：对grand进行右旋操作
b.RR：对grand进行左旋操作
处理完成后的结果如下
image.png

4、添加-修复性质4-LR/RL

添加节点的父节点为RED

image.png
解决方案

添加节点的uncle节点为Black

1、自己染成BLACK，grand染成RED

2、进行双旋操作
a. LR：parent进行左旋，grand进行右旋
b. RL：parent进行右旋，grand进行左旋
旋转后的结果如下

image.png

3.2.2、具体实现如下

@Override
protected void afterAdd(Node<E> node) {
    Node<E> parent = node.parent;

    if (parent == null) {
        // 添加的是根节点将其染成黑色
        black(node);
        return;
    }
    // 总共有12种情况
    // 1、当添加节点的父节点为黑色，有4种情况，这些情况不需要进行任何处理
    if (isBlack(parent))
        return;
    // 2、当添加节点的父节点为红色，有8种情况：
    // 其中uncle节点为红色,有4种情况
    Node<E> uncle = node.sibling();
    Node<E> grand = parent.parent;
    if (isRed(uncle)) {
        // 将parent和uncle染成黑色
        black(parent);
        black(uncle);
        // 将祖父节点向上合并，将其作为新添加的节点，可能依然会造成上溢
        red(grand);
        afterAdd(grand);
        return;
    }

    // uncle节点为黑色
    // 需要进行判断LL、RR、LR、RL，进行旋转操作
    if (parent.isLeftChild()) { // L
        if (node.isLeftChild()) { // LL
            // parent染成黑色、grand染成红色
            black(parent);
            red(grand);
            // 向右单选
            rotateRight(grand);
        } else {// LR
            // 自己染成黑色，grand染成红色
            black(node);
            red(grand);
            // 双旋
            rotateLeft(parent);
            rotateRight(grand);
        }
    } else { // R
        if (node.isLeftChild()) { // RL
            // 自己染成黑色，grand染成红色
            black(node);
            red(grand);
            // 双旋
            rotateRight(parent);
            rotateLeft(grand);
        } else {// RR
            // parent染成黑色，grand染成红色
            black(parent);
            red(grand);
            // 向左单选
            rotateLeft(grand);
        }
    }

}

// 右旋
private void rotateRight(Node<E> grand) {
    Node<E> parent = grand.left;
    Node<E> child = parent.right;

    grand.left = child;
    parent.right = grand;

    // 让parent称为根节点
    parent.parent = grand.parent;
    if (grand.isLeftChild()) {
        grand.parent.left = parent;
    } else if (grand.isRightChild()) {
        grand.parent.right = parent;
    } else {
        // 根节点
        root = parent;
    }

    // 维护parent属性
    grand.parent = parent;

    if (child != null)
        child.parent = grand;
}

// 左旋
private void rotateLeft(Node<E> grand) {
    Node<E> parent = grand.right;
    Node<E> child = parent.left;

    grand.right = child;
    parent.left = grand;

    // 让parent称为根节点
    parent.parent = grand.parent;
    if (grand.isLeftChild()) {
        grand.parent.left = parent;
    } else if (grand.isRightChild()) {
        grand.parent.right = parent;
    } else {
        root = parent;
    }

    // 维护parent
    grand.parent = parent;
    if (child != null)
        child.parent = grand;
}

4、删除

红黑树等价于4阶B树，B树中真正被删除的必定都在叶子节点中，也就是B树的最后一层。而最后一层的元素只会有如下四种情况

image.png
根据上图可以将删除分为如下两种情况：

1、删除叶子节点中的红色元素。
2、删除叶子节点中的黑色元素。

4.1、删除-RED节点

直接删除，不需做任何处理
比如删除上图中17/33/50/72红色节点，直接删除即可，并不会影响红黑树的5条性质。

4.2、删除-BLACK节点

可以分为3种情况：

1、拥有2个RED子节点的BLACK节点

对应上图中的情况1，删除BLACK节点25时，会先找到前驱或后继节点，覆盖BLACK节点25的值，然后再删除前驱或后继节点，其实情况1就转化成了删除RED节点的情况，不需任何处理。

2、拥有1个RED子节点的BLACK节点
3、BLACK叶子节点
image.png

4.2.1、删除-拥有1个RED子节点的BLACK节点

判定条件：用以替代的子节点为RED子节点。
处理方案：将替代的RED子节点染成BLACK接口修复红黑树的性质。

image.png

4.2.2、删除-BLACK叶子节点-sibling为BLACK

image.png

上图3棵树中，BLACK叶子节点88，它的sibling节点都是黑色。

如果删除BLACK叶子节点88，从B树的角度来看，会使B树下溢。
B树下溢处理方案有两种：
1、如果sibling至少有一个RED子节点

从sibling借一个元素，即进行旋转操作。（旋转又分为LR、RL、LL、RR）
旋转之后中心节点继承parent节点的颜色。
旋转之后的左右子节点染成BLACK。
上图3棵树旋转后的结果如下图：

image.png

2、如果sibling没有1个RED子节点

由于不能从兄弟节点借元素，需要进行合并操作，将父节点挪下来和左右子节点进行合并。
将sibling染成RED，将parent染成BLACK。

image.png
如果父节点是RED的，父节点挪下来不会造成下溢；
如果父节点是黑色的，那么将父节点挪下来，依然会造成下溢。

这时只需要把parent当做被删除的节点处理即可。
image.png

4.2.3、删除-BLACK叶子节点-sibling为RED

image.png

如果sibling是RED，将sibling染成BLACK，parent染成RED。
然后进行旋转。
这样又回到了删除-BLACL叶子节点-sibling为BLACK的情况。
按照前面的分析进行处理即可。
注意上面的分析删除的节点都是作为parent的右子节点，如果删除的是parent的左子节点的话，执行的操作是对称的。
4.3、删除的具体实现

protected void afterRemove(Node<E> node, Node<E> replacement) {
    // 如果删除的是红色节点，不进行处理
    if (isRed(node))
        return;

    // 来到这里说明删除的黑色节点
    // 如果替代的子节点红色子节点
    if (isRed(replacement)) {
        // 将替代的子节点染成BLACK即可
        black(replacement);
        return;
    }

    // 来到这里,说明删除的是BLACK叶子节点
    // 如果删除的是根节点
    Node<E> parent = node.parent;
    if (parent == null)
        return;

    // 如果删除的是黑色叶子节点，如果兄弟节点是黑色的，看兄弟节点能不能借元素，能借进行旋转操作，不能借需要合并
    // 合并还会造成下溢，需要将合并的父节点作为删除的节点，执行删除逻辑。
    // 不能使用node.sibling()获取兄弟节点，因为此时parent的left或right指向的不再是node，它已被删除了
//              Node<E> sibling=node.sibling();
    boolean isLeft = parent.left == null || node.isLeftChild();
    Node<E> sibling = isLeft ? parent.right : parent.left;
    if (isLeft) { // 被删除的叶子节点在左边，兄弟节点在右边

        if (isRed(sibling)) {
            black(sibling);
            red(parent);

            rotateLeft(parent);

            sibling = parent.right;
        }

        if (isBlack(sibling.left) && isBlack(sibling.right)) { // 表示不能借

            boolean parentBlack = isBlack(parent);
            black(parent);
            red(sibling);
            if (parentBlack)
                afterRemove(parent, null);
        } else {
            if (isBlack(sibling.right)) {
                rotateRight(sibling);
                sibling = parent.right;
            }

            color(sibling, colorOf(parent));
            black(parent);
            black(sibling.right);
            rotateLeft(parent);
        }
    } else { // 被删除的叶子节点在右边，兄弟节点在左边
        // 如果兄弟节点是红色 ,由于兄弟节点是红色，需要转换成兄弟节点是黑色（将侄子节点变成兄弟节点）
        // 所以为了减少重复代码，先判断红色兄弟节点
        if (isRed(sibling)) {
            black(sibling);
            red(parent);
            // parent右旋转
            rotateRight(parent);
            // 更换兄弟
            sibling = parent.left;
        }

        // 来到这里兄弟节点必然是黑色的
        // 判断兄弟节点能不能借元素，就是兄弟节点至少有一个红色子节点
        if (isBlack(sibling.left) && isBlack(sibling.right)) { // 表示不能借
            // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
            boolean parentBlack = isBlack(parent);
            black(parent);
            red(sibling);
            if (parentBlack)
                afterRemove(parent, null);
        } else { // 兄弟节点至少有一个红色的子节点
            // 将LR转换成LL，然后统一执行LL情况的代码
            if (isBlack(sibling.left)) { // LR
                rotateLeft(sibling);
                sibling = parent.left;
            }
            // 旋转中心继承parent的颜色，左右子节点染成BLACK
            color(sibling, colorOf(parent));
            black(parent);
            black(sibling.left);
            rotateRight(parent);
        }

    }
}

5、红黑树的平衡

为何满足红黑树的5条性质，就能保证红黑树是平衡的？

满足红黑树的5条性质，就能保证红黑树是等价于4阶B树的，而4阶B树是平衡的，所以就能保证红黑树的平衡。

image.png

在节点数量固定时，左右子树的高度越接近，树就越平衡。
看到上图依然会有人有疑问：虽然等价的4阶B树高度比较低，但是对应的红黑树展开后，高度依然很高，这又怎么解释呢？

相比于AVL树，红黑树的平衡比较宽松：它能保证没有一条路径会大于其他路径的2倍。这样就能保证红黑树不会退化成链表。可以看到最短路径是只包含黑色节点的路径，而最长的路径是最短路径长度的2倍。
红黑树的平衡是一种弱平衡，黑高度平衡（每条路径上只计算黑色节点的高度）。
红黑树的最大高度=2*log2(n+1),依然是O(logn)级别。

6、平均时间复杂度

红黑树也是二叉搜索树，时间复杂度和树高相关的。而红黑树的最大高度=2*log2(n+1),依然是O(logn)级别，所以搜索、删除、添加的时间复杂度是O(logn)级别的。

搜索：O(logn)
添加：O(logn),O(1)次旋转
删除：O(logn)，O(1)次旋转。（AVL树删除的时间复杂度是O(logn)，但是需要O(logn)次的旋转）。

6.1、AVL树 VS 红黑树

AVL树

平衡比较严格：每个左右子树的高度差小于1

最大高度=1.44*log2（n+2）-1.328（100W个节点，AVL树的最大高度为28）

搜索、添加、删除的时间复杂度为O(logn)级别，添加需要O(1)此旋转，删除需要O(logn)次旋转。

红黑树

平衡比较宽松：没有一条路径大于其他路径的2倍。

最大高度=2*log2（n+1）（100W个节点，红黑树的最大高度为40）

搜索、添加、删除的时间复杂度为O(logn)级别的，添加、删除都只需O(1)此旋转。

如果搜索频率远大于删除和添加的话，建议选择AVL树（AVL对平衡要求严格，当节点数量比较大时AVL树高是小于红黑树的）。如果搜索、删除、添加次数差不多，建议选择红黑树。
相比于AVL树，红黑树是牺牲了部分平衡性，来换取添加、删除操作时比较少的旋转。整体性能优于AVL树。
红黑树的平均统计性能优于AVL树，实际应用中更多的使用红黑树。

6.2、完整代码

public class RBTree<E> extends BST<E> {
    public static final boolean RED = true;
    public static final boolean BLACK = false;

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new RBNode<E>(element, parent);
    }
    
    @Override
    protected void afterRemove(Node<E> node, Node<E> replacement) {
        // 如果删除的是红色节点，不进行处理
        if (isRed(node))
            return;

        // 来到这里说明删除的黑色节点
        // 如果替代的子节点红色子节点
        if (isRed(replacement)) {
            // 将替代的子节点染成BLACK即可
            black(replacement);
            return;
        }

        // 来到这里,说明删除的是BLACK叶子节点
        // 如果删除的是根节点
        Node<E> parent = node.parent;
        if (parent == null)
            return;

        // 如果删除的是黑色叶子节点，如果兄弟节点是黑色的，看兄弟节点能不能借元素，能借进行旋转操作，不能借需要合并
        // 合并还会造成下溢，需要将合并的父节点作为删除的节点，执行删除逻辑。
        // 不能使用node.sibling()获取兄弟节点，因为此时parent的left或right指向的不再是node，它已被删除了
//              Node<E> sibling=node.sibling();
        boolean isLeft = parent.left == null || node.isLeftChild();
        Node<E> sibling = isLeft ? parent.right : parent.left;
        if (isLeft) { // 被删除的叶子节点在左边，兄弟节点在右边

            if (isRed(sibling)) {
                black(sibling);
                red(parent);

                rotateLeft(parent);

                sibling = parent.right;
            }

            if (isBlack(sibling.left) && isBlack(sibling.right)) { // 表示不能借

                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack)
                    afterRemove(parent, null);
            } else {
                if (isBlack(sibling.right)) {
                    rotateRight(sibling);
                    sibling = parent.right;
                }

                color(sibling, colorOf(parent));
                black(parent);
                black(sibling.right);
                rotateLeft(parent);
            }
        } else { // 被删除的叶子节点在右边，兄弟节点在左边
            // 如果兄弟节点是红色 ,由于兄弟节点是红色，需要转换成兄弟节点是黑色（将侄子节点变成兄弟节点）
            // 所以为了减少重复代码，先判断红色兄弟节点
            if (isRed(sibling)) {
                black(sibling);
                red(parent);
                // parent右旋转
                rotateRight(parent);
                // 更换兄弟
                sibling = parent.left;
            }

            // 来到这里兄弟节点必然是黑色的
            // 判断兄弟节点能不能借元素，就是兄弟节点至少有一个红色子节点
            if (isBlack(sibling.left) && isBlack(sibling.right)) { // 表示不能借
                // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack)
                    afterRemove(parent, null);
            } else { // 兄弟节点至少有一个红色的子节点
                // 将LR转换成LL，然后统一执行LL情况的代码
                if (isBlack(sibling.left)) { // LR
                    rotateLeft(sibling);
                    sibling = parent.left;
                }
                // 旋转中心继承parent的颜色，左右子节点染成BLACK
                color(sibling, colorOf(parent));
                black(parent);
                black(sibling.left);
                rotateRight(parent);
            }

        }

    }

    @Override
    protected void afterAdd(Node<E> node) {
        // 添加总共分为12种情况
        // 如果添加的red节点的parent是黑色的不需要任何处理(4种情况)
        Node<E> parent = node.parent;
        if (parent == null) { // 添加的是根节点
            black(node);
            return;
        }

        if (isBlack(parent))
            return;

        // parent是RED，分为parent的sibling是RED和parent的sibling是BLACK
        // 如果parent的sibling是RED，会上溢，将parent和parent的sibling染成BLACK，将grand节点染成RED向上合并，作为新添加的节点
        // 向上合并可能会依然会造成上溢
        Node<E> sibling = parent.sibling();
        Node<E> grand = parent.parent;
        if (isRed(sibling)) {
            black(parent);
            black(sibling);
            grand = red(grand);
            afterAdd(grand);
            return;
        }

        // parent的sibling是黑色的
        if (parent.isLeftChild()) { // L
            if (node.isLeftChild()) { // LL
                black(parent);
                red(grand);
                rotateRight(grand);
            } else {// LR
                black(node);
                red(grand);
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else { // R
            if (node.isLeftChild()) { // RL
                black(node);
                red(grand);
                rotateRight(parent);
                rotateLeft(grand);
            } else {// RR
                black(parent);
                red(grand);
                rotateLeft(grand);
            }
        }

    }

    private void rotateRight(Node<E> grand) { // LL
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;

        // 让parent称为根节点
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
        } else { // 根节点
            root = parent;
        }

        grand.parent = parent;
        if (child != null)
            child.parent = grand;
    }

    private void rotateLeft(Node<E> grand) { // RR
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;

        // 让parent称为根节点
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
        } else {
            root = parent;
        }

        grand.parent = parent;
        if (child != null)
            child.parent = grand;
    }

    /**
     * 获取节点的颜色
     */
    public boolean colorOf(Node<E> node) {
        return node == null ? BLACK : ((RBNode) node).color;
    }

    /**
     * 判断节点是否是黑色
     */
    public boolean isBlack(Node<E> node) {
        return colorOf(node) == BLACK;
    }

    /**
     * 判断节点是否是红色
     */
    public boolean isRed(Node<E> node) {
        return colorOf(node) == RED;
    }

    /**
     * 对节点进行染色
     * 
     * @return 返回染色后的节点
     */
    public RBNode<E> color(Node<E> node, boolean color) {
        if (node != null)
            ((RBNode<E>) node).color = color;
        return ((RBNode<E>) node);
    }

    /**
     * 将节点染成黑色
     */
    public RBNode<E> black(Node<E> node) {
        return color(node, BLACK);
    }

    /**
     * 将节点染成红色
     */
    public RBNode<E> red(Node<E> node) {
        return color(node, RED);
    }

    public static class RBNode<E> extends Node<E> {
        // 新添加的节点默认是红色，这样就能满足1、2、3、5四条性质，不能保证性质4一定满足
        public boolean color = RED;

        public RBNode(E element, Node<E> parent) {
            super(element, parent);
        }

        @Override
        public String toString() {
            String colorString = "";
            if (color == RED)
                colorString = "_RED_";
            return colorString + element.toString();

        }

    }

}

红黑树（Red Black Tree）

1、概述

红黑树的5条性质

请问下图中的二叉树是红黑树吗？

2、红黑树的等价变换

红黑树 VS 2-3-4树

3、添加

3.1、辅助方法

3.2、添加节点

3.2.1、添加的所有情况

1、4种情况不需要任何处理

2、4种情况属于B树上溢

3、添加-修复性质4-LL/RR

4、添加-修复性质4-LR/RL

3.2.2、具体实现如下

4、删除

4.1、删除-RED节点

4.2、删除-BLACK节点

4.2.1、删除-拥有1个RED子节点的BLACK节点

4.2.2、删除-BLACK叶子节点-sibling为BLACK

4.2.3、删除-BLACK叶子节点-sibling为RED

5、红黑树的平衡

6、平均时间复杂度

6.1、AVL树 VS 红黑树

6.2、完整代码

猜你喜欢

热点阅读