红黑树解析——从概念到Code

古城微笑少年丶 2022-09-10 04:28 133阅读 0赞

## 一、基本概念 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]

## 二、红黑树的性质，原理： ##

> 红黑树的本质还是对链表的优化：使得查询的效率提升。

**红黑树原理**  
[https://note.youdao.com/ynoteshare1/index.html?id=9b50b184f00f75af266fd53e334bb819&type=note?auto][https_note.youdao.com_ynoteshare1_index.html_id_9b50b184f00f75af266fd53e334bb819_type_note_auto]

## 三、红黑树Node节点 ##

/**
     * 红黑树Node
     */
    static class RBNode<K extends Comparable<K>, V> {
        
        //颜色
        private boolean color;
        //左子节点
        private RBNode left;
        //右子节点
        private RBNode right;
        //父节点
        private RBNode parent;
        //key
        private K key;
        //value
        private V value;
    
        public RBNode(boolean color, RBNode left, RBNode right, RBNode parent, K key, V value) {
        
            this.color = color;
            this.left = left;
            this.right = right;
            this.parent = parent;
            this.key = key;
            this.value = value;
        }
    
        public RBNode() {
        
        }
    
        public boolean isColor() {
        
            return color;
        }
    
        public void setColor(boolean color) {
        
            this.color = color;
        }
        ……get、set方法
    }

## 四、操作红黑树 ##

### 1）插入元素 ###

插入这里涉及到类似结构型的设计模式，对外界公开设置值的方法，自己隐藏复杂的逻辑实现

/**
     * 公开的插入接口
     * @param key 键
     * @param value 值
     */
    public void insert(K key, V value) {
        
       RBNode node = new RBNode();
       node.setKey(key);
       node.setValue(value);
       node.setColor(RED);
       insert(node);
    }
    
    /**
     * 内部插入接口定义
     */
    private void insert(RBNode node) {
        
        //1.找到插入的位置
        RBNode parent = null;
        RBNode x = this.root;
        while(x != null) {
        
            parent = x;
            //a > b 则返回 1，否则返回 -1 ，相等返回0
            int cmp = node.key.compareTo(parent.key);
            if(cmp < 0) {
        
                x = x.left;
            } else if(cmp == 0) {
        
            	// 遇到值相等的直接将对应key位置上的value做替换操作直接return了
                parent.setValue(node.value);
                return;
            } else {
        
                x = x.right;
            }
        }
        // 找到parent，开始将node放到parent底下
        node.parent = parent;
    
        if(parent != null) {
        
            if(node.key.compareTo(parent.key) < 0) {
        
                parent.left = node;
            } else {
        
                parent.right = node;
            }
        } else {
        
            this.root = node;
        }
        //插入之后需要进行修复红黑树，让红黑树再次平衡。
        insertFixUp(node);
    }

### 2）左旋右旋的方法： ###

左旋：  
1）安顿好叔叔的孩子，首先把原来节点的孩子指向然后再接上父亲节点，放到左边的下面（注意有null的情况）  
2）叔叔上位，可能叔叔变成根节点，这个要考虑到（x.parent 不等于 null）判断x是左边节点还是右边节点  
3）叔叔上位之后安顿好原来的节点

#### ⭐动图： ####

![在这里插入图片描述][8352e8fffd50ca5dcc0842eadb6dbc64.gif]  
![在这里插入图片描述][7e03cbe1fdc172bcc2d5c2dc4d1d2244.gif]

/**
     * 左旋方法
     * 左旋示意图：左旋x节点
     *    p                   p
     *    |                   |
     *    x                   y
     *   / \         ---->   / \
     *  lx  y               x   ry
     *     / \             / \
     *    ly  ry          lx  ly
     *
     * 左旋做了几件事？
     * 1.将y的左子节点赋值给x的右边，并且把x设置为y的左子节点的父节点
     * 2.将x的父节点（非空时）指向y，更新y的父节点为x的父节点
     * 3.将y的左子节点指向x，更新x的父节点为y
     */
    private void leftRotate(RBNode x) {
        
        RBNode y = x.right;
        //将y的左子节点赋值给x的右边
        x.right = y.left;
        //并且把x设置为y的左子节点的父节点
        if(y.left != null) {
        
            y.left.parent = x;
        }
    
        //将x的父节点（非空时）指向y
        if(x.parent != null) {
        
            //如果x是parent左子树，则把y安放到parent的左边
            if(x.parent.left == x) {
        
                x.parent.left = y;
            } else {
        //否则把y安放到parent的右边
                x.parent.right = y;
            }
            //更新y的父节点为x的父节点
            y.parent = x.parent;
        } else {
        
            this.root = y;
            this.root.parent = null;
        }
    
        y.left = x;
        x.parent = y;
    }
    
    /**
     * 右旋方法
     * 右旋示意图：右旋y节点
     *
     *    p                       p
     *    |                       |
     *    y                       x
     *   / \          ---->      / \
     *  x   ry                  lx  y
     * / \                         / \
     *lx  ly                      ly  ry
     *
     * 右旋都做了几件事？
     * 1.将x的右子节点 赋值 给了 y 的左子节点，并且更新x的右子节点的父节点为 y
     * 2.将y的父节点（不为空时）指向x，更新x的父节点为y的父节点
     * 3.将x的右子节点指向y，更新y的父节点为x
     */
    private void rightRotate(RBNode y) {
        
        //1.将x的右子节点赋值给y的左子节点，并将y赋值给x右子节点的父节点（x右子节点非空时）
        RBNode x = y.left;
        y.left = x.right;
        if(x.right != null) {
        
            x.right.parent = y;
        }
    
        //2.将y的父节点p（非空时）赋值给x的父节点，同时更新p的子节点为x（左或右）
        x.parent = y.parent;
    
        if(y.parent != null) {
        
            if(y.parent.left == y) {
        
                y.parent.left = x;
            } else {
        
                y.parent.right = x;
            }
        } else {
        
            this.root = x;
            this.root.parent = null;
        }
    
        //3.将x的右子节点赋值为y，将y的父节点设置为x
        x.right = y;
        y.parent = x;
    }

### 3）修复节点的红黑位置 ###

其实很简单，简单的需要处理的几种情况：

1.  parent红、uncle红，只负责染色，将parent和uncle染色为黑色，pp染色为红，将pp作为下一个需要调整的节点进行处理修正
2.  parent红， uncle黑/不存在，分为parent 左右两种情况
    
    1.  parent为左结点
        
        1.  添加到左边LL，变色，pp红，右旋
        2.  添加到右边LR，左旋，变为LL代码复用
    2.  parent为右节点
        
        1.  添加到左边RL，父节点右旋，变为RR，代码复用
        2.  添加到右边RR，变色后，pp红，左旋

/**
     * 插入后修复红黑树平衡的方法
     *     |---情景1：红黑树为空树
     *     |---情景2：插入节点的key已经存在，（前面已经处理了）
     *     |---情景3：插入节点的父节点为黑色
     *
     *     情景4 需要咱们去处理
     *     |---情景4：插入节点的父节点为红色
     *          |---情景4.1：叔叔节点存在，并且为红色（父-叔 双红）
     *          |---情景4.2：叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
     *               |---情景4.2.1：插入节点为其父节点的左子节点（LL情况）
     *               |---情景4.2.2：插入节点为其父节点的右子节点（LR情况）
     *          |---情景4.3：叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
     *               |---情景4.3.1：插入节点为其父节点的右子节点（RR情况）
     *               |---情景4.3.2：插入节点为其父节点的左子节点（RL情况）
     */
    private void insertFixUp(RBNode node) {
        
        RBNode parent = parentOf(node);
        RBNode gparent = parentOf(parent);
        // 不存在父节点 或者存在父节点，父节点为黑色
        if (parent == null || isBlack(parent)) {
        
            setBlack(this.root);
        }
        //parent是红色，那么一定存在爷爷节点
        //父节点为爷爷节点的左子树
        if (parent == gparent.left) {
        
            RBNode uncle = gparent.right;
            //4.1：叔叔节点存在，并且为红色（父-叔 双红）
            //将父和叔染色为黑色，再将爷爷染红，并将爷爷设置为当前节点，进入下一次循环判断
            if (uncle != null && isRed(uncle)) {
        
                setBlack(parent);
                setBlack(uncle);
                setRed(gparent);
                insertFixUp(gparent);
                return;
            }
    
            //叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
            if (uncle == null || isBlack(uncle)) {
        
                //插入节点为其父节点的右子节点（LR情况）=>
                //左旋（父节点），当前节点设置为父节点，进入下一次循环
                if (node == parent.right) {
        
                    leftRotate(parent);
                    insertFixUp(parent);
                    return;
                }
    
                //插入节点为其父节点的左子节点（LL情况）=>
                //变色（父节点变黑，爷爷节点变红），右旋爷爷节点
                if (node == parent.left) {
        
                    setBlack(parent);
                    setRed(gparent);
                    rightRotate(gparent);
                }
            }
    
        } else {
        //父节点为爷爷节点的右子树
            RBNode uncle = gparent.left;
            //4.1：叔叔节点存在，并且为红色（父-叔 双红）
            //将父和叔染色为黑色，再将爷爷染红，并将爷爷设置为当前节点，进入下一次循环判断
            if (uncle != null && isRed(uncle)) {
        
                setBlack(parent);
                setBlack(uncle);
                setRed(gparent);
                insertFixUp(gparent);
                return;
            }
    
            //叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
            if (uncle == null || isBlack(uncle)) {
        
                //插入节点为其父节点的左子节点（RL情况）
                //右旋（父节点）得到RR情况，当前节点设置为父节点，进入下一次循环
                if (node == parent.left) {
        
                    rightRotate(parent);
                    insertFixUp(parent);
                    return;
                }
    
                //插入节点为其父节点的右子节点（RR情况）=>
                //变色（父节点变黑，爷爷节点变红），右旋爷爷节点
                if (node == parent.right) {
        
                    setBlack(parent);
                    setRed(gparent);
                    leftRotate(gparent);
                }
            }
    
        }
        setBlack(this.root);
    }

### 4）删除节点的操作： ###

八种情况，待写……

主要由前驱后驱节点指定，删除的节点  
1）没有子树，直接删除  
黑色需要平衡操作，红色不用操作（删除黑色会影响黑高）  
2）只有一个节点的时候，删除节点必为黑，需要使得删除节点重新指向自己的孩子。（孩子变黑）  
4）有左右孩子：涉及到前驱后驱节点的转换

## 五、画图解释修复LL、LR、RR、RL情况 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 2]

## 六、问题： ##

### 分类： ###

### 红黑树的引入解决了什么问题 ###

1）解决查找效率问题  
2）尾插法解决了死循环问题

尾插法是JDK1.8之后才有的，尾插法可以解决1.7以前的头插法带来的环形链表的问题（thread1使用添加元素，而thread2对其进行扩容）

红黑树的调整：加入有五种情况，删除有八种情况需要考虑。

**关于HashMap：**  
这里的介绍更为详细：  
https://blog.csdn.net/weixin\_43801418/article/details/120074520  
[【源码解析】深入理解HashMap][HashMap]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/35b03a02b6684884a221e533856d4281.png
[https_note.youdao.com_ynoteshare1_index.html_id_9b50b184f00f75af266fd53e334bb819_type_note_auto]: https://note.youdao.com/ynoteshare1/index.html?id=9b50b184f00f75af266fd53e334bb819&type=note
[8352e8fffd50ca5dcc0842eadb6dbc64.gif]: /images/20220829/24ff38ca54ec45efa2953b47a857afcc.png
[7e03cbe1fdc172bcc2d5c2dc4d1d2244.gif]: /images/20220829/12c385f414a44dbf9df734dfd23b4768.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/8448a36b998f41819b7e7cb97bb53868.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/14fcead2750d453a93bd8c16233361e8.png
[HashMap]: https://blog.csdn.net/weixin_43801418/article/details/120074520