十八、红黑树

作者: 咸鱼Jay | 来源:发表于2022-02-02 17:52 被阅读0次

十八、红黑树
数据结构—树—红黑树
TreeMap
数据结构与算法-AVL 红黑树
[转载]红黑树
拿下红黑树
红黑树
彻底理解红黑树（二）之插入
彻底理解红黑树（三）之删除
Golang红黑树

1、红黑树的定义

红黑树也是一种自平衡的二叉搜索树
以前也叫做平衡二叉B树（Symmetric Binary B-tree）

红黑树必须满足以下 5 条性质

节点是 $\color{red}{RED}$ 或者 $\color{black}{BLACK}$
根节点是 $\color{black}{BLACK}$
$\color{#ed7d30}{叶子节点}$ （外部节点，空节点）都是 $\color{black}{BLACK}$
节点的子节点都是
- $\color{red}{RED}$ 节点的 $\color{blue}{parent}$ 都是 $\color{black}{BLACK}$
- 从根节点到 $\color{#ed7d30}{叶子节点}$ 的所有路径上不能有 2 个连续的 $\color{red}{RED}$ 节点
从任一节点到 $\color{#ed7d30}{叶子节点}$ 的所有路径都包含相同数目的 $\color{black}{BLACK}$ 节点

可以看一下下面这棵是红黑树么？

2、红黑树的等价变换

红黑树和4阶B树（2-3-4树）具有等价性
$\color{black}{BLACK}$ 节点与它的 $\color{red}{RED}$ 子节点融合在一起，形成1个B树节点
红黑树的 $\color{black}{BLACK}$ 节点个数与4阶B树的节点总个数相等
网上有些教程：用 2-3树与红黑树进行类比，这是极其不严谨的，2-3树并不能完美匹配红黑树的所有情况
注意：后面展示的红黑树都会省略 NULL 节点

2.1、红黑树 vs 2-3-4树

思考：如果上图最底层的

\color{black}{BLACK}

节点是不存在的，在B树中是什么样的情形？
整棵B树只有1个节点，而且是超级节点

3、代码实现

3.1、几个英文单词的意义

截图.png

$\color{blue}{parent}$ ：父节点
$\color{blue}{sibling}$ ：兄弟节点，例如：17和33。
$\color{blue}{uncle}$ ：叔父节点（ $\color{blue}{parent}$ 的兄弟节点）例如：50的叔父节点是25。
$\color{blue}{grand}$ ：祖父节点（ $\color{blue}{parent}$ 的父节点）例如：38是50的祖父节点。

3.2、实现前准备

3.2.1、创建红黑树的类

3.2.2、实现RBNode类

因为红黑树的节点多两个颜色，所以跟AVL树一样需要创建自己的Node类

3.2.3、封装一些辅助方法

3.2.4、在Node类中新增sibling方法

4、添加

已知
- B树中，新元素必定是添加到叶子节点中
- 4阶B树所有节点的元素个数 $\color{green}{x}$ 都符合 1 ≤ $\color{green}{x}$ ≤ 3
建议新添加的节点默认为 $\color{red}{RED}$ ，这样能够让红黑树的性质尽快满足（性质 1、2、3、5 都满足，性质 4 不一定）

◼ 如果添加的是根节点，染成 $\color{black}{BLACK}$ 即可

4.1、添加的所有情况

添加只可能添加到最底层，既然是添加到最后一层，那么我们就要考虑最后一层叶子节点都有那些情况。
其实就4大情况：红黑红、黑红、红黑、黑。因为这个是4阶B树，所有只有这4种情况。

那么现在新添加节点有多少情况呢？
因为新添加节点只能是最后一层，所以新添加的节点只能添加到上面4中情况节点的左右节点。这里共有12种情况：
17节点的左右边、33节点的左右边、46节点的左边、50节点的左右边、72节点的左右边、76节点的右边、88节点的左右边。

添加节点的 $\color{blue}{parent}$ 为BLACK
如果添加时，新添加节点的 $\color{blue}{parent}$ 为 $\color{BLACK}{BLACK}$ ，那么会满足红黑树的性质4。同样也满足4阶B树的性质。因此不用做任何额外处理。

添加节点的parent为BLACK

上图中有4种情况插入情况：46的左节点、76的右节点、88的左右节点

添加节点的 $\color{blue}{parent}$ 为 $\color{red}{RED}$
剩下的8种情况是不满足红黑树的性质4(新添加节点的 $\color{blue}{parent}$ 为 $\color{red}{RED}$ )，因此需要进行相应的处理。

添加节点的parent为RED

上图中有8种情况插入情况:17的左右节点、33的左右节点、50的左右节点、72的左右节点

4.2、添加 – 修复性质4

4.2.1、添加 – 修复性质4 – LL\RR

上面讲到添加共有12种情况，其中有4种情况是不用处理的(也就是它的父节点是 $\color{BLACK}{BLACK}$ 就不用处理)，如果添加时它的父节点是 $\color{red}{RED}$ 也就是8种情况，是需要进行处理的，这8种情况违背了红黑树的性质4(性质4：不能有连续2个 $\color{red}{RED}$ 节点)。

添加 – 修复性质4 – LL\RR

上图新添加52和60节点，它们是RR和LL情况。
1、染色：先把新添加的节点的parent染成黑色，祖父节点 $\color{blue}{grand}$ 染成红色。
2、旋转：进行相应的旋转，分别是对46左旋转和对76右旋转。

添加 – 修复性质4 – LL\RR

4.2.2、添加 – 修复性质4 – LR\RL

下图新添加节点48和74，它们是RL和LR情况。

旋转：添加48节点时先50右旋转，46左旋转；添加74节点时先72左旋转，76右旋转
染色：添加48节点时先48染成黑色，46染成红色；添加74节点时74染成黑色，76染成红色
添加 – 修复性质4 – LR\RL

上面要处理的8种情况已经讲了4种情况，还剩下4种情况，这剩下4种跟我们已经讲完的4种有什么区别呢？我们可以通过叔父节点来判断。已经讲完的4种情况的新添加节点的叔父节点都是黑色，剩下的4种情况的新添加节点的叔父节点都是红色。

4.2.3、添加 – 修复性质4 – 上溢 – LL

添加 – 修复性质4 – 上溢 – LL

4.2.4、添加 – 修复性质4 – 上溢 – RR

添加 – 修复性质4 – 上溢 – RR

4.2.5、添加 – 修复性质4 – 上溢 – LR

添加 – 修复性质4 – 上溢 – LR

4.2.7、添加 – 情况总结

添加 – 情况总结

4.3、代码实现

在RBTree类中实现afterAdd方法：

上面是实现了如果添加的节点的父节点是黑色的不用处理，和如果添加节点的叔父节点是红色的处理。
下面就是添加节点的叔父节点是黑色的情况，这种情况就需要进行旋转了。这里我们在AVLTree和RBTree之间在搞一个父类BBST：

public class BBST<E> extends BST<E> {
    public BBST() {
        this(null);
    }
    
    public BBST(Comparator<E> comparator){
        super(comparator);
    }
    
    protected void rotateLeft(Node<E> g) {
        // 因为是左旋转，那么p节点肯定是g节点的右子树
        Node<E> p = g.right;
        Node<E> child = p.left;
        g.right = child;
        p.left = g;
        afterRotate(g,p,child);
    }
    
    protected void rotateRight(Node<E> g) {
        Node<E> p = g.left;
        Node<E> child = p.right;
        g.left = child;
        p.right = g;
        afterRotate(g,p,child);
    }
    
    /**
     * 公共代码，不管左旋转、右旋转，都要执行
     * @param g 失衡节点
     * @param p 失衡节点的tallerChild
     * @param child g和p需要交换的子树(本来是p的子树，后面会变成g的子树)
     */
    protected void afterRotate(Node<E> g, Node<E> p, Node<E> child) {
        // 让p成为这棵子树的根节点
        p.parent = g.parent;
        if(g.isLeftChild()) {
            g.parent.left = p;
        }else if(g.isRightChild()) {
            g.parent.right = p;
        }else {// g是root节点
            root = p;
        }
        
        // 更新child的parent
        if(child != null) {
            child.parent = g;
        }
        
        // 更新g的parent
        g.parent = p;
        
        
    }
    
    protected void rotate(
            Node<E> r,// 子树的根节点
            Node<E> b,Node<E> c,
            Node<E> d,
            Node<E> e,Node<E> f) {
        // 让d成为这棵树的根节点
        d.parent = r.parent;
        if(r.isLeftChild()) {
            r.parent.left = d;
        }else if(r.isRightChild()) {
            r.parent.right = d;
        }else {
            root = d;
        }
        
        // b-c
        b.right = c;
        if(c != null) c.parent = b;
        
        // e-f
        f.left = e;
        if(e != null) e.parent = f;
        
        //b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
    }
}

public class AVLTree<E> extends BBST<E>{
    public AVLTree() {
        this(null);
    }
    
    public AVLTree(Comparator<E> comparator){
        super(comparator);
    }
    
    @Override
    protected void afterAdd(Node<E> node) {
        while((node = node.parent) != null) {
            if(isBalanced(node)) {
                // 更新高度
                updateHeight(node);
            }else {
                // 恢复平衡
                reblalance(node);
                // 整棵树恢复平衡
                break;
            }
        }
    }
    
    @Override
    protected void afterRemove(Node<E> node) {
        while((node = node.parent) != null) {
            if(isBalanced(node)) {
                // 更新高度
                updateHeight(node);
            }else {
                // 恢复平衡
                reblalance(node);
            }
        }
    }
    
    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element, parent);
    }
     
    private boolean isBalanced(Node<E> node) {
        // 平衡因子的绝对值小于等于1，就表示该节点是平衡的。
        return Math.abs(((AVLNode)node).balanceFactor()) <= 1;
    }
    
    private void updateHeight(Node<E> node) {
        ((AVLNode)node).updateHeight();
    }
    
    @Override
    protected void afterRotate(Node<E> g, Node<E> p, Node<E> child) {
        super.afterRotate(g, p, child);
        // 更新高度(先更新比较矮的g，再更新比较高的p)
        updateHeight(g);
        updateHeight(p);
    }
    
    @Override
    protected void rotate(Node<E> r, Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f) {
        super.rotate(r, b, c, d, e, f);
        updateHeight(b);
        updateHeight(f);
        updateHeight(d);
    }
    
    /**
     * 恢复平衡
     * @param node 高度最低的那个不平衡节点
     */
    private void reblalance(Node<E> g) {
        Node<E> p = ((AVLNode)g).tallerChild();
        Node<E> n = ((AVLNode)p).tallerChild();
        if(p.isLeftChild()) {// L
            if(n.isLeftChild()) {// LL
                rotate(g, n, n.right, p, p.right, g);
            }else {// LR
                rotate(g, p, n.left, n, n.right, g);
            }
        }else {// R
            if(n.isLeftChild()) {// RL
                rotate(g, g, n.left, n, n.right, p);
            }else {// RR
                rotate(g, g, p.left, p, n.left, n);
            }
        }
    }
    
    /**
     * 恢复平衡
     * @param node 高度最低的那个不平衡节点
     */
    private void reblalance2(Node<E> g) {
        Node<E> p = ((AVLNode)g).tallerChild();
        Node<E> n = ((AVLNode)p).tallerChild();
        if(p.isLeftChild()) {// L
            if(n.isLeftChild()) {// LL
                rotateRight(g);
            }else {// LR
                rotateLeft(p);
                rotateRight(g);
            }
        }else {// R
            if(n.isLeftChild()) {// RL
                rotateRight(p);
                rotateLeft(g);
            }else {// RR
                rotateLeft(g);
            }
        }
    }
    
    private static class AVLNode<E> extends Node<E>{
        int height = 1;
        
        public AVLNode(E element, Node<E> parent) {
            super(element, parent);
        }
        
        /**
         * 平衡因子
         */
        public int balanceFactor() {
            int leftHeight = left == null ? 0 : ((AVLNode)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode)right).height;
            return leftHeight - rightHeight;
        }
        
        private void updateHeight() {
            int leftHeight = left == null ? 0 : ((AVLNode)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode)right).height;
            height = 1 + Math.max(leftHeight, rightHeight);
        }
        
        /**
         * 当前节点左右子树那个比较高
         */
        public Node<E> tallerChild() {
            int leftHeight = left == null ? 0 : ((AVLNode)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode)right).height;
            if(leftHeight > rightHeight) return left;
            if(leftHeight < rightHeight) return right;
            return isLeftChild() ? left : right;
        }
        
        @Override
        public String toString() {
            String parentString = null;
            if(parent != null) {
                parentString = parent.element.toString();
            }
            return element + "_p(" + parentString + ")_h("+height+")";
        }
    }
}

public class RBTree<E> extends BBST<E>{
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    public RBTree() {
        this(null);
    }
    
    public RBTree(Comparator<E> comparator){
        super(comparator);
    }
    
    @Override
    protected void afterAdd(Node<E> node) {
        Node<E> parent = node.parent;
        
        //  添加的是根节点或者上溢到达了根节点
        if(parent == null) {
            black(node);
            return;
        }
        
        // 如果父节点是黑色，直接返回
        if(isBlack(parent)) return;
        
        // 叔父节点
        Node<E> uncle = parent.sibling();
        // 祖父节点
        Node<E> grand = parent.parent;
        if(isRed(uncle)) {// 叔父节点是红色【B树节点上溢】
            black(parent);
            black(uncle);
            // 把祖父节点当做是新添加的节点
            afterAdd(red(grand));
            return;
        }
        
        // TODO 叔父节点不是红色 
        
    }
    
    private RBNode<E> color(Node<E> node,boolean color){
        if(node != null) {
            ((RBNode<E>)node).color = color;
        }
        return (RBNode<E>)node;
    }
    
    private RBNode<E> red(Node<E> node){
        return color(node, RED);
    }
    
    private RBNode<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;
    }
    
    private static class RBNode<E> extends Node<E>{
        boolean color = RED;
        public RBNode(E element, Node<E> parent) {
            super(element, parent);
        }
        
    }
}

下面进行叔父节点是黑色的情况的逻辑处理：
可以根据上面《4.2.1、添加 – 修复性质4 – LL\RR》和《4.2.2、添加 – 修复性质4 – LR\RL》来实现代码

我们还可以对其代码进行优化一下

我们可以发现上溢和不上溢，都会进行grand节点进行染红色，那么还可以进一步代码优化：

4.4、测试

给RBNode重写toString方法

RBNode类里还要重写createNode方法：

最终运行效果如下：

5、删除

B树中，最后真正被删除的元素都在叶子节点中

5.1、删除 – RED节点

直接删除，不用作任何调整

protected void afterRemove(Node<E> node,Node<E> replacement) {
        // 如果删除的节点是红色
        if(isRed(node)) return;
        ......      
    }

5.2、删除 – BLACK节点

删除 – BLACK节点

有3种情况：

拥有2个子节点的节点(25节点)
- 不可能被直接删除，因为会找到它的子节点替代删除，这里可能是17或者33子节点。
- 因此不用考虑这种情况
拥有1个 $\color{red}{RED}$ 子节点的 $\color{black}{BLACK}$ 节点(46和76节点)
$\color{black}{BLACK}$ 叶子节点(88节点)
上面3种情况，只有第2和第3需要进行特殊处理，第1是不用特殊处理的。

5.2.1、删除 – 拥有1个RED子节点的BLACK节点

截图.png
代码实现
在RBTree类种实现afterRemove方法，但是这里afterRemove方法是只传一个Node参数(46节点或者76节点)，这里我们是需要被删除节点的子节点(50节点或者72节点)用于取代被删除节点，所以我们需要在afterRemove方法里在传一个参数：
在BST类中：

在RBTree类中：

5.2.2、删除 – BLACK叶子节点 – sibling为BLACK

5.2.2.1、删除节点的兄弟节点是黑色，但它子节点至少有一个红色，可以借

这里要删除的是88节点，它的兄弟节点76是黑色的。
我们删除的叶子节点88，删掉后假设需要向兄弟借一个元素，有一个前提条件：

\color{red}{它的兄弟节点必须是黑色，并且它的兄弟节点的子节点必须至少有一个是红色}

。

5.2.2.2、删除节点的兄弟节点是黑色，但它子节点没有红色，不可以借

5.2.3、删除 – BLACK叶子节点 – sibling为RED

这里要删除的是88节点，它的兄弟节点55是红色的。
如果要删除的叶子节点它的兄弟是红色的话，那么这个红色节点(55)是在父节点里面的。所以这里55作为它的兄弟是没法借过来的，要借的是左右临近的。
这里只能是将红色节点(55)的子节点变成要删除节点的兄弟。这个时候就变成了5.2.2.2的情况了。
代码实现：
这里要实现代码，是需要拿到要删除节点的兄弟节点的，在afterRemove方法里通过Node<E> sibling = node.sibling();方法拿兄弟节点是错误的，因为node.sibling()方法里的判断是根据删除节点是否是左右节点来判断的，而afterRemove方法又是在删除节点之后调用的，因此这个方法获取兄弟节点是不对的。

protected void afterRemove(Node<E> node,Node<E> replacement) {
     ......
    
    // 删除的是黑色叶子节点
    // 判断被删除的node是左还是右
    boolean left = parent.left == null || node.isLeftChild();
    Node<E> sibling = left ? parent.right : parent.left;
    if(left) {// 被删除的节点在左边，兄弟节点在右边
        if (isRed(sibling)) { // 兄弟节点是红色
            black(sibling);
            red(parent);
            rotateLeft(parent);
            // 更换兄弟
            sibling = parent.right;
        }
        
        // 兄弟节点必然是黑色
        if (isBlack(sibling.left) && isBlack(sibling.right)) {
            // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
            boolean parentBlack = isBlack(parent);
            black(parent);
            red(sibling);
            if (parentBlack) {
                afterRemove(parent, null);
            }
        } else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
            // 兄弟节点的左边是黑色，兄弟要先旋转
            if (isBlack(sibling.right)) {
                rotateRight(sibling);
                sibling = parent.right;
            }
            
            color(sibling, colorOf(parent));
            black(sibling.right);
            black(parent);
            rotateLeft(parent);
        }
    }else {// 被删除节点在右边，兄弟节点在左边
        if (isRed(sibling)) {// 兄弟节点是红色
            black(sibling);
            red(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 {// 兄弟节点至少有1个红色子节点，向兄弟节点借元素
            // 兄弟节点的左边是黑色，兄弟要先旋转
            if(isBlack(sibling.left)) {
                rotateLeft(sibling);
                sibling = parent.left;
            }
            color(sibling, colorOf(parent));
            black(sibling.left);
            black(parent);
            rotateRight(parent);
        }
    }
}

afterRemove方法去除replacement参数

private void remove(Node<E> node) {
    if(node == null) return;
    size--;
    if(node.hasTwoChildren()) {// 度为2的节点
        // 找到后继节点
        Node<E> s = successor(node);
        // 用后继节点的值覆盖度为2的节点的值
        node.element = s.element;
        // 删除后继节点
        node = s;
    }
    
    // 删除node节点（node的度必然是1或者0）
    Node<E> replacement = node.left != null ? node.left : node.right;
    if (replacement != null) { // node是度为1的节点
        // 更改parent
        replacement.parent = node.parent;
        // 更改parent的left、right的指向
        if (node.parent == null) { // node是度为1的节点并且是根节点
            root = replacement;
        } else if (node == node.parent.left) {
            node.parent.left = replacement;
        } else { // node == node.parent.right
            node.parent.right = replacement;
        }
        
        // 删除节点之后的处理
        afterRemove(replacement);
    } else if (node.parent == null) { // node是叶子节点并且是根节点
        root = null;
        // 删除节点之后的处理
        afterRemove(node);
    } else { // node是叶子节点，但不是根节点
        if (node == node.parent.left) {
            node.parent.left = null;
        } else { // node == node.parent.right
            node.parent.right = null;
        }
        // 删除节点之后的处理
        afterRemove(node);
    }
}

@Override
protected void afterRemove(Node<E> node) {
    // 如果删除的节点是红色
//      if(isRed(node)) return;
    // 或者 用以取代删除节点的子节点是红色
    if (isRed(node)) {
        black(node);
        return;
    }
    
    Node<E> parent = node.parent;
    // 删除的是根节点
    if (parent == null) return;
    
    // 删除的是黑色叶子节点【下溢】
    // 判断被删除的node是左还是右
    boolean left = parent.left == null || node.isLeftChild();
    Node<E> sibling = left ? parent.right : parent.left;
    if (left) { // 被删除的节点在左边，兄弟节点在右边
        if (isRed(sibling)) { // 兄弟节点是红色
            black(sibling);
            red(parent);
            rotateLeft(parent);
            // 更换兄弟
            sibling = parent.right;
        }
        
        // 兄弟节点必然是黑色
        if (isBlack(sibling.left) && isBlack(sibling.right)) {
            // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
            boolean parentBlack = isBlack(parent);
            black(parent);
            red(sibling);
            if (parentBlack) {
                afterRemove(parent);
            }
        } else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
            // 兄弟节点的左边是黑色，兄弟要先旋转
            if (isBlack(sibling.right)) {
                rotateRight(sibling);
                sibling = parent.right;
            }
            
            color(sibling, colorOf(parent));
            black(sibling.right);
            black(parent);
            rotateLeft(parent);
        }
    } else { // 被删除的节点在右边，兄弟节点在左边
        if (isRed(sibling)) { // 兄弟节点是红色
            black(sibling);
            red(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);
            }
        } else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
            // 兄弟节点的左边是黑色，兄弟要先旋转
            if (isBlack(sibling.left)) {
                rotateLeft(sibling);
                sibling = parent.left;
            }
            
            color(sibling, colorOf(parent));
            black(sibling.left);
            black(parent);
            rotateRight(parent);
        }
    }
}