手写一个红黑树_红黑树 手写

手写一个红黑树

什么是树

树（tree）是一种抽象数据类型（ADT）,用来模拟具有树状结构性质的数据集合，它是由n(n > 0)个有限节点通过连接他们的边组成一个具有层次关系的几个，把他叫’做‘是因为它看起来像一个倒挂的树，也就是它的根是朝上的，而叶子朝下的。

树有很多种，向上的一个节点有多余两个的子节点的树，称为多路树，而每个节点最多只能有两个子节点的一个形式称为二叉树。

• 节点：上图的圆圈，比如A，B，C等都是表示节点。节点一般代表一些实体，在Java面向对象编程中，节点一般代表对象。
• 边：连接节点的线称为边，边表示节点的关联关系，一般从一个节点到另一个节点的唯一方法就是沿着一条顺着有边的道路前进。在Java中通常表示引用。

树结构的常用术语

①路径：顺着节点的边从一个节点走到另一个节点，所经过的节点的顺序排列就称为“路径”。

②、根：树顶端的节点称为根。一棵树只有一个根，如果要把一个节点和边的集合称为树，那么从根到其他任何一个节点都必须有且只有一条路径。A是根节点。

③、父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点

④、子节点：一个节点含有的子树的节点称为该节点的子节点；F、G是C节点的子节点。

⑤、兄弟节点：具有相同父节点的节点互称为兄弟节点；F、G节点互为兄弟节点。

⑥、叶节点：没有子节点的节点称为叶节点，也叫叶子节点，比如上图的H、E、F、G都是叶子节点。

⑦、子树：每个节点都可以作为子树的根，它和它所有的子节点、子节点的子节点等都包含在子树中。

⑧、节点的层次：从根开始定义，根为第一层，根的子节点为第二层，以此类推。

⑨、深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；（从上往下看）

⑩、高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；（从下往上看）

二叉树：树的每个节点最多只能有两个子节点

上图的第一幅图B节点有DEF三个子节点，就不是二叉树，称为==多路树=

而第二幅图每个节点最多只有两个节点，是二叉树，并且二叉树的子节点称为“左子节点”和“右子节点”

二叉搜索树：

如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。

二叉搜索树要求：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

它的左、右子树也分别为二叉排序树。

二叉搜索树-查询：

查找某个节点，我们必须从根节点开始查找。

①，查找值比当前节点值大，则搜索右子树；

②，查找值等于当前节点值，停止搜索（终止条件）；

③，查找值小于当前节点值，则搜索左子树；
1
2
3
4
5

二叉搜索树-插入节点：

要插入节点，必须先找到插入的位置。与查找操作相似，由于二叉搜索树的特殊性，

待插入的节点也需要从根节点开始进行比较，小于根节点则与根节点左子树比较，

反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置。

二叉搜索树-遍历节点：

遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的有前序遍历，中序遍历和后序遍历。而二叉搜索树最常用的是中序遍历。

①、中序遍历:左子树——》根节点——》右子树

②、前序遍历:根节点——》左子树——》右子树

③、后序遍历:左子树——》右子树——》根节点

中序遍历示意图：

二叉搜索树-查找最大值和最小值

要找最小值，先找根的左节点，然后一直找这个左节点的左节点，直到找到没有左节点的节点，那么这个节点就是最小值。

同理要找最大值，一直找根节点的右节点，直到没有右节点，则就是最大值。

二叉搜索树-删除节点：

删除节点是二叉搜索树中最复杂的操作，删除的节点有三种情况，前两种比较简单，但是第三种却很复杂。

1、该节点是叶节点（没有子节点）

2、该节点有一个子节点

3、该节点有两个子节点

①、删除没有子节点的节点

要删除叶节点，只需要改变该节点的父节点引用该节点的值，即将其引用改为 null 即可。

②、删除有一个子节点的节点

删除有一个子节点的节点，我们只需要将其父节点原本指向该节点的引用，改为指向该节点的子节点即可

③、删除有两个子节点的节点

当删除的节点存在两个子节点，那么删除之后，两个子节点的位置我们就没办法处理了。

既然处理不了，我们就想到一种办法，用另一个节点来代替被删除的节点，那么用哪一个节点来代替呢？

我们知道二叉搜索树中的节点是按照关键字来进行排列的，某个节点的关键字次高节点是它的中序遍历后继节点。

用后继节点来代替删除的节点，显然该二叉搜索树还是有序的。

那么如何找到删除节点的中序后继节点呢？

其实我们稍微分析，这实际上就是要找比删除节点关键值大的节点集合中，最小的那一个节点，只有这样代替删除节点后才能满足二叉搜索树的特性。

后继节点也就是：比删除节点大的最小节点。

④、删除有必要吗？

通过上面的删除分类讨论，我们发现删除其实是挺复杂的，那么其实我们可以不用真正的删除该节点，只需要在Node类中增加一个标识字段isDelete，

当该字段为true时，表示该节点已经删除，反之则没有删除。这样删除节点就不会改变树的结构了。

影响就是查询时需要判断一下节点是否已被删除。二叉搜索树-时间复杂度分析：

1.回顾经典-二分查找算法

[1,2,3,4,5,6,7,8,9。。。。。。。100]

暴力算法：运气好时 性能不错，运气不好时 性能暴跌…

二分查找算法：数据源必须是有序数组，性能非常不错，每次迭代查询可以排除掉一半的结果。

   package com.zh.dichotomy;
    
    /**
     * @Description: 测试二分查找法
     * @ClassName TextDichotomy
     * @date: 2021.05.20 16:08
     * @Author: zhanghang
     */
    public class TextDichotomy {
    
        public static void main(String[] args) {
    
            int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10,11,12};
            System.out.println(binarySearch(arr, 16));
        }
    
        /**
         * description: 二分查找法
         * date: 2021年-05月-20日 16:08
         * author: zhanghang
         *
         * @param arr 有序的数组
         * @param data 要查找的数据
         * @return int 找到的下标，没有找到返回-1
         */
        public static int binarySearch(int[] arr, int data){
            int low = 0;
            int height = arr.length - 1;
            while (low <= height){
                // 获取到中心下标
                int mid = low + (height - low) / 2;
    
                if (data > arr[mid]){
                    low = mid + 1;
                }else if (data < arr[mid]){
                    height = mid - 1;
                }else {
                    return mid;
                }
            }
    
            return -1;
        }
    }
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

2.二分查找法的缺陷

强制依赖有序数组，性能才能不错。

3.数组有什么缺陷

没有办法快速插入，扩容也很麻烦

4.那怎么查能拥有二分查找的高性能又能拥有链表一样的灵活性？

二叉搜索树

5.二分查找算法时间复杂度推算过程

从上表可以看出N/(2K)肯定是大于等于1，也就是N/(2K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，

也就是是查到剩余最后一个数才查到我们想要的数据，也就是

N/(2^K)=1 => 2^K = N => K = log2 (N) => 二分查找算法时间复杂度：O(log2(N)) => O(logN)

普通二叉搜索树致命缺陷：

怎么解决 二叉搜索树 退化成线性链表的问题？

如果插入元素时，树可以自动调整两边平衡，会保持不错的查找性能

AVL树简介

AVL树有什么特点？

1. 具有二叉查找树的全部特性。
2. 每个节点的左子树和右子树的高度差最多等于1

平衡树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了！（插入或者删除时，会发生左旋、右旋操作，使这棵树再次左右保持一定的平衡）

为什么有了平衡树还需要红黑树？

虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，

因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，

几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。

显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树！！！

红黑树

红黑树的性质：

红黑树并不是一个完美平衡二叉查找树，从图上可以看到，根结点P的左子树显然比右子树高，

但左子树和右子树的黑结点的层数是相等的，也就是说，任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。

所以我们叫红黑树这种平衡为黑色完美平衡。

红黑树的性质讲完了，只要这棵树满足以上性质，这棵树就是趋近与平衡状态的，

不要问为什么，发明红黑树的科学家就是这么牛逼！

前面讲到红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。

1.变色：结点的颜色由红变黑或由黑变红。

2.左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

3.右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变

左旋图示：

右旋图示：

红黑树查找：

红黑树插入：

插入操作包括两部分工作：

1.查找插入的位置

2.插入后自平衡

注意：插入节点，必须为红色，理由很简单，红色在父节点（如果存在）为黑色节点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。

但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。

在开始每个情景的讲解前，我们还是先来约定下:

红黑树插入节点情景分析

情景1：红黑树为空树

最简单的一种情景，直接把插入结点作为根结点就行

注意：根据红黑树性质2：根节点是黑色。还需要把插入结点设为黑色。

情景2：插入结点的Key已存在

处理：更新当前节点的值，为插入节点的值

情景3：插入结点的父结点为黑结点

由于插入的结点是红色的，当插入结点的黑色时，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。

情景4：插入节点的父节点为红色

再次回想下红黑树的性质2：根结点是黑色。如果插入节点的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。

这一点很关键，因为后续的旋转操作肯定需要祖父结点的参与

插入情景4.1：叔叔结点存在并且为红结点

依据红黑树性质4可知，红色节点不能相连 ==> 祖父结点肯定为黑结点；

因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红

处理：

1.将P和U节点改为黑色

2.将PP改为红色

3.将PP设置为当前节点，进行后续处理

可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；

但如果PP的父结点是红色，则违反红黑树性质了。所以需要将PP设置为当前节点，继续做插入操作自平衡处理，直到平衡为止。

插入情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点

注意：单纯从插入前来看，叔叔节点非红即空（NIL节点），否则的话破坏了红黑树性质5，此路径会比其它路径多一个黑色节点。

插入情景4.2.1：新插入节点，为其父节点的左子节点（LL红色情况）

处理：

1.变颜色：将P设置为黑色，将PP设置为红色

2.对PP节点进行右旋

插入情景4.2.2：新插入节点，为其父节点的右子节点（LR红色情况）

处理：

1.对P进行左旋

2.将P设置为当前节点，得到LL红色情况

3.按照LL红色情况处理（1.变颜色 2.右旋PP）

插入情景4.3：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点

该情景对应情景4.2，只是方向反转，直接看图。

插入情景4.3.1：新插入节点，为其父节点的右子节点（RR红色情况）

处理：

1.变颜色：将P设置为黑色，将PP设置为红色

2.对PP节点进行左旋

插入情景4.3.2：新插入节点，为其父节点的左子节点（RL红色情况）

处理：

1.对P进行右旋

2.将P设置为当前节点，得到RR红色情况

3.按照RR红色情况处理（1.变颜色 2.左旋PP）

红黑树案例：

测试代码

package com.zh.tree;

import lombok.Data;

/**
 * @Description: 手写红黑树
 * @ClassName RBTree
 * @date: 2021.05.21 09:19
 * @Author: zhanghang
 *
 * ① 创建RBTree，定义颜色
 * ② 创建RBNode
 * ③ 辅助方法定义：parentOf(node),isRed(node),setRed(node),setBlack(node),inOrderPrint()
 * ④ 左旋方法定义：leftRotate(node)
 * ⑤ 右旋方法定义：rightRotate(node)
 * ⑥ 公开插入接口方法定义： insert(K key, V value)
 * ⑦ 内部插入接口方法定义：insert(RBNode node)
 * ⑧ 修正插入导致红黑树失衡的方法定义：insertFIxUp(RBTree node)
 * ⑨ 测试红黑树正确性
 */
@Data
public class RBTree<K extends Comparable<K>, V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    // 树根的引用
    private RBNode root;

    /**
     * description: 获取当前节点的父节点
     * date: 2021年-05月-21日 9:30
     * author: zhanghang
     *
     * @param node
     * @return
     */
    private RBNode parentOf(RBNode node){
        if (null == node) {
            return null;
        }
        return node.parent;
    }

    /**
     * description: 判断当前节点是否是红色
     * date: 2021年-05月-21日 9:31
     * author: zhanghang
     *
     * @param node
     * @return
     */
    private boolean isRed(RBNode node){
        if (null == node){
            return false;
        }
        return node.color == RED;
    }

    /**
     * description: 判断当前节点是否是黑色
     * date: 2021年-05月-21日 9:31
     * author: zhanghang
     *
     * @param node
     * @return
     */
    private boolean isBlack(RBNode node){
        if (null == node){
            return false;
        }
        return node.color == BLACK;
    }
    
    /**
     * description: 设置当前节点为红色
     * date: 2021年-05月-21日 9:35
     * author: zhanghang
     *
     * @param node
     * @return void
     */
    private void setRed(RBNode node){
        if (null != node){
            node.color = RED;
        }
    }
    
    /**
     * description: 中序打印二叉树
     * date: 2021年-05月-21日 9:49
     * author: zhanghang
     * 
     * @param 
     * @return void
     */ 
    private void inOrderPrint(){
        inOrderPrint(this.root);
    }
    // 中序打印二叉树
    private void inOrderPrint(RBNode node){
        if (null != node){
            inOrderPrint(node.left);
            System.out.println("key:" + node.key + ",value:" + node.value);
            inOrderPrint(node.right);
        }
    }

    /**
     * description: 公开的插入方法
     * date: 2021年-05月-21日 10:51
     * author: zhanghang
     *
     * @param key
    * @param value
     * @return void
     */
    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){
        RBNode parent = null;
        RBNode x = this.root;

        while (x != null){
            parent = x;
            // cmp > 0 说明，node.key 大于x.key, 需要到x的右子树查找
            // cmp == 0 说明 node.key 等于 x.key 说明需要进行替换操作
            // cmp < 0 说明，node.key 小于 x.key, 需要到x的左子树查找
            int cmp = node.key.compareTo(x.key);
            if (cmp > 0){
                x = x.right;
            }else if ((cmp == 0)){
                x.setValue(node.value);
                return;
            }else {
                x = x.left;
            }
        }

        node.parent = parent;
        if (null != parent){
            // 判断node 与 parent 的 key谁大
            int cmp = node.key.compareTo(parent.key);
            if (cmp > 0) { // 说明当前 nodo的key大于 parent的key,需要将node放入parent的右子节点
                parent.right = node;
            }else { // 说明当前 nodo的key 小于 parent的key,需要将node放入parent的左子节点
                parent.left = node;
            }
        }else {
            this.root = node;

        }
        // 需要调用修复红黑树平衡的方法
        insertFixUp(node);
    }

    /**
     * description: 插入后修复红黑树平衡的方法
     * date: 2021年-05月-21日 11:10
     * author: zhanghang
     *
     * @param null
     * @return
     *
     *  说明：
     *  |---情景1：红黑树为空树，将根节点染色为黑色
     *  |---情景2：插入节点的key已经存在，不需要处理
     *  |---情景3：插入节点的父节点为黑色，因为你所插入的路径，黑色节点没有变化，所有红黑树依然平衡，所以不需要处理
     *
     *     情景4：需要我们去处理
     *     |---情景4： 插入节点父节点为红色
     *          |---情景4.1：叔叔节点存在，并且为红色（父-叔 双红），
     *                      将爸爸和叔叔节点染色为黑色，将爷爷节点染色为红色，并且在以爷爷节点为当前节点，进行下一轮处理
     *          |---情景4.2：叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
     *              |---情景4.2.1：插入节点为其父节点的左子节点（LL情况），
     *                              将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点右旋
     *              |---情景4.2.2：插入节点为其父节点的右子节点（LR情况），
     *                              以爸爸节点进行一次左旋，得到LL双红的情景（4.2.1）,然后再以爸爸节点为当前节点进行下一轮处理
     *          |---情景4.3：叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
     *              |---情景4.3.1：插入节点为其父节点的右子节点（RR情况），
     *                              将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点左旋
     *              |---情景4.3.2：插入节点为其父节点的左子节点（RL情况），
     *                              以爸爸节点进行一次右旋，得到RR双红的情景（4.3.1），然后指定爸爸节点为当前节点进行下一轮处理
     */
    private void insertFixUp(RBNode node){
        this.root.setColor(BLACK);

        RBNode parent = parentOf(node);   // 得到当前节点的父节点
        RBNode gParent = parentOf(parent); // 得到当前节点的爷爷节点

        // 情景4：插入节点父节点为红色
        if (null != parent && isRed(parent)){
            // 如果父节点是红色，那么一定存在爷爷节点，因为跟节点不可能是红色
            RBNode uncle = null;

            // 判断父节点是不是在爷爷节点的左边
            if (parent == gParent.left){
                uncle = gParent.right;

                // 情景4.1：叔叔节点存在，并且为红色（父-叔 双红）
                if (null != uncle && isRed(uncle)){
                    //  将爸爸和叔叔节点染色为黑色，将爷爷节点染色为红色，并且在以爷爷节点为当前节点，进行下一轮处理
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gParent);
                    insertFixUp(gParent);
                    return;
                }
                // 情景4.2：叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
                if (null == uncle || isBlack(uncle)){
                    // 情景4.2.1：插入节点为其父节点的左子节点（LL情况），将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点右旋
                    if (node == parent.left){
                        setBlack(parent);
                        setRed(gParent);
                        rightRotate(gParent);
                        return;
                    }
                    // 情景4.2.2：插入节点为其父节点的右子节点（LR情况），
                    // 以爸爸节点进行一次左旋，得到LL双红的情景（4.2.1）,然后再以爸爸节点为当前节点进行下一轮处理
                    if (node == parent.right){
                        rightRotate(parent);
                        insertFixUp(parent);
                        return;
                    }
                }
            }else { //父节点为爷爷节点的右子树
                uncle = gParent.left;
                // 情景4.1：叔叔节点存在，并且为红色（父-叔 双红）
                if (null != uncle && isRed(uncle)){
                    //  将爸爸和叔叔节点染色为黑色，将爷爷节点染色为红色，并且在以爷爷节点为当前节点，进行下一轮处理
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gParent);
                    insertFixUp(gParent);
                    return;
                }

                // 情景4.3：叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
                if (null == uncle || isBlack(uncle)){
                    // 情景4.3.1：插入节点为其父节点的右子节点（RR情况）
                    // 将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点左旋
                    if (node == parent.right){
                        setBlack(parent);
                        setRed(gParent);
                        leftRotate(gParent);
                        return;
                    }

                    // 情景4.3.2：插入节点为其父节点的左子节点（RL情况）
                    // 以爸爸节点进行一次右旋，得到RR双红的情景（4.3.1），然后指定爸爸节点为当前节点进行下一轮处理
                    if (node == parent.left){
                        rightRotate(parent);
                        insertFixUp(parent);
                        return;
                    }
                }
            }
        }
    }

    /**
     * description: 设置当前节点为红色
     * date: 2021年-05月-21日 9:35
     * author: zhanghang
     *
     * @param node
     * @return void
     */
    private void setBlack (RBNode node){
        if (null != node){
            node.color = BLACK;
        }
    }

    /**
     * description: 左旋方法
     * date: 2021年-05月-21日 9:54
     * author: zhanghang
     *
     * @param null
     * @return
     *
     * 左旋示意图：左旋x节点
     *
     *    p                      p
     *    |                      |
     *    x                      y
     *   / \      ----->        / \
     * lx   y                  x   ry
     *     / \                / \
     *   ly   ry            lx   ly
     *
     * 1. 将y的左子节点的父节点更新为x, 并将x的右子节点指向y的左子节点（ly）
     * 2. 将x的父节点不为空时，更新y的父节点为x的父节点，并将x的父节点 指定 子树 （当前x的子树位置） 指定为y
     * 3. 将x的父节点 更新为y,将y的左子节点更新为x
     */
    private void leftRotate(RBNode x){
        RBNode y = x.right;
        // 1. 将x的右子节点指向y的左子节点（ly）
        x.right = y.left;
        // 1.1 如果y的左子节点不为null,将y的左子节点的父节点更新为x
        if (null != y.left){
            y.left.parent = x;
        }

        // 2. 将x的父节点不为空时，更新y的父节点为x的父节点，并将x的父节点 指定 子树 （当前x的子树位置） 指定为y
        if (null != x.parent){
            y.parent = x.parent;
            // x在x父节点的左边
            if (x == x.parent.left){
                x.parent.left = y;
            }else {
                x.parent.right = y;
            }
        }else {
            // 说明当前x为根节点，需要更新y的新的根节点
            this.root = y;
            this.root.parent = null;
        }

        // 3. 将x的父节点 更新为y,将y的左子节点更新为x
        x.parent = y;
        y.left = x;
    }

    /**
     * description: 右旋方法
     * date: 2021年-05月-21日 9:54
     * author: zhanghang
     *
     * @param null
     * @return
     *
     * 右旋示意图：右旋y节点
     *
     *          p                  p
     *          |                  |
     *          y                  x
     *        / \     ----->     / \
     *       x   ry            lx   y
     *     / \                    / \
     *   lx   ly                ly   ry
     *
     * 1. 将y的左子节点指向x的右子节点, 并且更新x的右子节点的父节点为y
     * 2. 将y的父节点不为空时，更新x的父节点为y的父节点，并将y的父节点 指定 子树 （当前y的子树位置） 指定为x
     * 3. 将y的父节点 更新为x,将x的右子节点更新为y
     */
    private void rightRotate(RBNode y){
        RBNode x = y.left;
        // 1. 将y的左子节点指向x的右子节点, 并且更新x的右子节点的父节点为y
        y.left = x.right;
        if (null != x.right){
            x.right.parent = y;
        }

        // 2. 将y的父节点不为空时，更新x的父节点为y的父节点，并将y的父节点 指定 子树 （当前y的子树位置） 指定为x
        if (null != y.parent){
            x.parent = y.parent;
            if (y == y.parent.left){
                y.parent.left = x;
            }else {
                y.parent.right = x;
            }
        }else {
            // 说明当前y为根节点，需要更新x的新的根节点
            this.root = x;
            this.root.parent = null;
        }

        // 3. 将y的父节点 更新为x,将x的右子节点更新为y
        y.parent = x;
        x.right = y;
    }


    @Data
    static class RBNode <K extends Comparable<K>, V>{
        private RBNode parent;
        private RBNode left;
        private RBNode right;
        private boolean color;
        private K key;
        private V value;
    }

}

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394

测试代码：

package com.zh.tree;

import java.util.Scanner;

/**
 * @Description: 测试红黑树
 * @ClassName RBTreeText
 * @date: 2021.05.21 14:48
 * @Author: zhanghang
 */
public class RBTreeTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        RBTree<String, Object> rbt = new RBTree<>();
        while (true){
            System.out.println("请输入key:");
            String key = scanner.next();
            System.out.println();
            rbt.insert(key,null);
            TreeOperation.show(rbt.getRoot());
        }
    }
}

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

测试时展示当前红黑树的结构：

package com.zh.tree;

/**
 * @Description:
 * @ClassName TreeOperation
 * @date: 2021.05.21 14:53
 * @Author: zhanghang
 */
public class TreeOperation {

    public static int getTreeDepth(RBTree.RBNode root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));

    }

    private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空

        if (currNode == null) return;

        // 先将当前节点保存到二维数组中

        res[rowIndex][columnIndex] = String.valueOf(currNode.getKey()+"-"+(currNode.isColor()? "R":"B")+"");

        // 计算当前位于树的第几层

        int currLevel = ((rowIndex + 1) / 2);

        // 若到了最后一层，则返回

        if (currLevel == treeDepth) return;

        // 计算当前行到下一行，每个元素之间的间隔(下一行的列索引与当前元素的列索引之间的间隔)

        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值

        if (currNode.getLeft() != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";

            writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);

        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值

        if (currNode.getRight() != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";

            writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);

        }

    }

    public static void show(RBTree.RBNode root) {
        if (root == null) System.out.println("EMPTY!");

        // 得到树的深度
        int treeDepth = getTreeDepth(root);
        // 最后一行的宽度为2的(n - 1)次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i ++) {
            for (int j = 0; j < arrayWidth; j ++) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth/ 2, res, treeDepth);
        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即
        for (String[] line: res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i ++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2: line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}

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

测试结果

请输入key:
1

1-B
请输入key:
2

   1-B 
    \  
     2-R
请输入key:
3

   2-B 
  / \  
 1-R 3-R
请输入key:
4

      2-B    
    /   \    
  1-B     3-B
           \ 
            4-R
请输入key:
5

      2-B    
    /   \    
  1-B     4-B
         / \ 
        3-R 5-R
请输入key:
6

            2-B          
         /     \         
      1-B         4-R    
                /   \    
              3-B     5-B
                       \ 
                        6-R
请输入key:
7

            2-B          
         /     \         
      1-B         4-R    
                /   \    
              3-B     6-B
                     / \ 
                    5-R 7-R
请输入key:
8

            4-B          
         /     \         
      2-R         6-R    
    /   \       /   \    
  1-B     3-B 5-B     7-B
                       \ 
                        8-R
请输入key:
9

            4-B          
         /     \         
      2-R         6-R    
    /   \       /   \    
  1-B     3-B 5-B     8-B
                     / \ 
                    7-R 9-R
请输入key:

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