devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构之红黑树_红黑树ll rr lr rl

作者：IT小白 | 2024-03-16 01:29:05

赞

踩

红黑树ll rr lr rl

1. 红黑树（Red Black Tree）

简称RBTree，也是一种自平衡的二叉搜索树。
大名鼎鼎红黑树。

在这里插入图片描述

1.1 性质

  1. 节点是RED或者BLACK；
  2. 根节点是BLACK；
  3. 叶子节点（外部节点，空节点）都是BLACK；它会让之前度为0或者度为1的节点添加两个null节点，变成度为2的节点；
  4. RED的子节点必须都是BLACK；
    RED节点的parent都是BLACK；
    从根节点到叶子节点的所有路径上不能有2个连续的RED节点；
  5. 从任一节点出发到叶子节点的所有路径都包含相同数目的BLACK节点（包括“不存在的null节点”）。

1.2 红黑树的等价变换

  • 红黑树
    在这里插入图片描述
  • 红黑树所有红色节点上升一层
    在这里插入图片描述
  • 转为B树显示
    在这里插入图片描述

红黑树和4阶B树具有等价性：

  1. BLACK节点与它的RED子节点融合在一起，形成一个B树节点；
  2. 红黑树的BLACK节点个数与4阶B树的节点总个数相等；

1.3 红黑树常用概念

  1. parent：父节点；
  2. sibling：兄弟节点；
  3. uncle：叔父节点-parent的兄弟节点；
  4. grand：祖父节点；

1.4 节点设计和全局变量

这里直接继承BST代码。

  • 二叉树节点：
	 // 节点类
    protected static class Node<E>{
        // 元素值
        E e;
        // 左子节点
        Node<E> left;
        // 右子节点
        Node<E> right;
        // 父节点
        Node<E> parent;
        public Node(E e, Node<E> parent){
            this.e = e;
            this.parent = parent;
        }
        /**
         * 判断当前节点是否是叶子节点
         * @return
         */
        protected boolean isLeaf(){
            return left == null && right == null;
        }

        /**
         * 判断当前节点是否存在左右子节点
         * @return
         */
        protected boolean hasTwoChildren(){
            return left != null && right != null;
        }

        /**
         * 判断是不是父节点的左子树
         * @return
         */
        public boolean isLeftChild(){
            return parent != null && this == parent.left;
        }

        /**
         * 判断是不是父节点的右子树
         * @return
         */
        public boolean isRightChild(){
            return parent != null && this == parent.right;
        }

        /**
         * 返回兄弟节点
         * @return
         */
        public Node<E> sibling(){
            if (isLeftChild()){
                return parent.right;
            }
            if (isRightChild()){
                return parent.left;
            }
            return null;
        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 红黑树节点（继承自node节点）:
	private static class RBNode<E> extends Node<E>{
        boolean color = RED;
        public RBNode(E e, Node<E> parent) {
            super(e, parent);
        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 全局变量：
	 // 节点数量
    protected int size;

    // 根节点
    protected Node<E> root;

  • 1
  • 2
  • 3
  • 4
  • 5
	private static final boolean RED = false;
    private static final boolean BLACK = true;

  • 1
  • 2

1.5 红黑树辅助函数

	/**
     * 染色
     */
    private Node<E> color(Node<E> node,boolean color){
        if (node == null){
            return node;
        }else {
            ((RBNode<E>)node).color = color;
            return node;
        }
    }

    /**
     * 染色成红色
     * @param node
     * @return
     */
    private Node<E> red(Node<E> node){
        return color(node, RED);
    }

    /**
     * 染色成黑色
     * @param node
     * @return
     */
    private Node<E> black(Node<E> node){
        return color(node, BLACK);
    }

    /**
     * 判断颜色
     * @param node
     * @return
     */
    private boolean colorOf(Node<E> node){
        return node == null ? BLACK : ((RBNode<E>)node).color;
    }

    /**
     * 是否为黑色
     * @param node
     * @return
     */
    private boolean isBlack(Node<E> node){
        return colorOf(node) == BLACK;
    }

    /**
     * 是否为红色
     * @param node
     * @return
     */
    private boolean isRed(Node<E> node){
        return colorOf(node) == RED;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56

1.6 添加

添加时的元素都是添加到叶子节点。

1.6.1 情况分析

默认新添加的节点为红色。

  • 共有图中12种添加情况。
    在这里插入图片描述
  • 其中下列四种情况满足红黑树性质，不需要处理：
    在这里插入图片描述
  • 下列的八种情况，不满足红黑树性质4（不能有了两个连续的RED），需要进行处理。
    在这里插入图片描述
1.6.1 black - uncle - LL\RR

在这里插入图片描述

  • 染色：将parent染色成BLACK，将grand染色成RED；
  • grand进行单旋：
    在这里插入图片描述
  • 旋转之后：重新满足红黑树性质。
    在这里插入图片描述
1.6.2 black - uncle - LR\RL

在这里插入图片描述

  • 把自己染成BLACK，grand染成RED；
  • 进行双旋：
    在这里插入图片描述
  • 重新恢复红黑树性质：
    在这里插入图片描述
1.6.3 red- uncle - 上溢

四种情况：LL、RR、LR、RL都采用上溢的方法来恢复平衡，可以参考上篇博客。

这里只展示了LL：

在这里插入图片描述

  • 将uncle和parent都染成BLACK；
  • 将grand染色为RED作为新节点向上合并，可能会继续触发上溢，如果持续到根节点，只需将根节点染成BLACK。
    在这里插入图片描述
1.6.4 代码实现
  • 修改继承逻辑：之前AVL和RBTree都继承自BST，单因为RBTree需要复用AVL的代码，所以这里新建一个平衡二叉搜索树BBST，将旋转代码放到里面，原先AVL更新高度的代码放到AVL中自己去实现。
/**
 * @Description 平衡二叉搜索树
 * @date 2022/4/20 15:15
 */
public class BBST<E> extends BinarySearchTree<E> {

    public BBST(){
        this(null);
    }

    public BBST(Comparator<E> Comparator){
        super(Comparator);
    }

    /**
     * 左旋
     * @param grand
     */
    protected void rotateLeft(Node<E> grand){
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;
        afterRotate(grand, parent, child);
    }

    /**
     * 右旋
     * @param grand
     */
    protected void rotateRight(Node<E> grand){
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;
        afterRotate(grand, parent, child);
    }

    /**
     * 旋转之后 更新 parent 和 height
     * @param grand
     * @param parent
     * @param child
     */
    protected void afterRotate(Node<E> grand,Node<E> parent,Node<E> child){
        // 更新 parent

        // 更新 p 的 parent 使成为当前子树的根节点
        parent.parent = grand.parent;
        if (grand.isLeftChild()){
            grand.parent.left = parent;
        }else if (grand.isRightChild()){
            grand.parent.right = parent;
        }else { // grand 是根节点
            root = parent;
        }

        // 更新 p.left 的 parent
        if (child != null){
            child.parent = grand;
        }
        // 更新 g 的 parent
        grand.parent = parent;
    }

    /**
     * 旋转
     * @param r 子树根节点
     * @param a
     * @param b
     * @param c
     * @param d
     * @param e
     * @param f
     * @param g
     */
    protected void rotate(
            Node<E> r,
            Node<E> a, Node<E> b, Node<E> c,
            Node<E> d,
            Node<E> e, Node<E> f, Node<E> g){

        // 让 d 成为这颗子树的根节点
        d.parent = r.parent;
        if (r.isRightChild()){
            r.parent.right = d;
        }else if (r.isLeftChild()){
            r.parent.left = d;
        }else {
            root = d;
        }

        // a b c
        b.left = a;
        if (a != null){
            a.parent = b;
        }
        b.right = c;
        if (c != null){
            c.parent = b;
        }

        // e f g
        f.left = e;
        if (e != null){
            e.parent = f;
        }
        f.right = g;
        if (g != null){
            g.parent = f;
        }

        // b d f
        d.left = b;
        b.parent = d;
        d.right = f;
        f.parent = d;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119

1.7 删除

B树中，所以真正被删除的元素都是在叶子节点中。红黑树也遵循相同的性质。

修改代码结构： 在原先afterRemove()方法的基础上新增参数replacement替代被删除的节点。修改BinarySearchTree.remove()：传入replacement参数。

1.7.1 RED

不需要做任何处理。

1.7.2 BLACK

有两个RED子节点：找它的子节点代替删除；

1.7.3 有一个RED子节点

判定条件：用以替代的子节点是RED。

  • 要删除的节点：‘46’、‘76’：
    在这里插入图片描述
  • 使用它的子节点代替它，删除子节点：
    在这里插入图片描述
  • 将子节点染黑：使保持红黑树性质。
    在这里插入图片描述
1.7.3 BLACK叶子节点 - sibling为 BLACK 并且至少有一个 RED 子节点

等同于B树的性质，如果删除节点是发生下溢，优先看兄弟节点是否可以“借”一个节点。这就要求兄弟节点为BLACK，并且至少有一个RED的子节点。

  • 如图：要删除节点 88：删除之后导致B树产生下溢。
    在这里插入图片描述
  • 需要从左侧兄弟节点“ 借 ”一个节点：
    在这里插入图片描述
  • 节点78为LR情况：
    在这里插入图片描述
  • 需要对其进行双旋来保证性质：
    在这里插入图片描述
  • 旋转之后：新的中心节点（78）继承parent（80）的颜色；左右节点染为BLACK。
    在这里插入图片描述
  • 还有下图两种LL情况：进行右单旋。
    在这里插入图片描述在这里插入图片描述
1.7.4 BLACK叶子节点 - sibling为 BLACK 没有 RED 子节点

当兄弟节点没有红色子节点无法借出时，需要让父节点下来合并。

  • 假如要删除节点88，它的兄弟节点又无法借出节点。
    在这里插入图片描述
  • 让父节点80下来合并并染色成BLACK，将原先的兄弟节点染色成RED。
    在这里插入图片描述
  • 但有一种特殊情况：如果parent是BLACK，就会导致parent也下溢（父节点必然没有红色子节点）。
    在这里插入图片描述

在这里插入图片描述

  • 这时之需要递归调用将parent节点传入即可。
1.7.4 BLACK叶子节点 - sibling为 RED
  • 要删除节点88：
    在这里插入图片描述
  • 将兄弟节点染色成BLACK，parent染色成RED，进行右旋：又回到了兄弟节点是黑色的情况。
    在这里插入图片描述
  • 将父节点下来合并：
    在这里插入图片描述
1.7.3 代码实现
protected void afterRemove(Node<E> node) {
        // 如果删除的节点是红色
        // 或者 用以取代删除节点的子节点是红色
        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;
            }

            // 兄弟节点必然是黑色
            System.out.println(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);
            }
        }
    }


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/246070
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号