欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

全网最强红黑树的理解和实现

程序员文章站 2022-05-16 11:23:55
...

红黑树我估计花费了30个小时左右来理解,看了各种视频和文章,以及阅读treemap的源码,最终自己java实现了一版。

红黑树的理解最重要最重要是 要理解234树,红黑树是由234树演变过来的。任何一颗红黑树都可以转变成一棵234树。对于234树我就这里不说了,自己百度下。

红黑树与234树的等价关系

  • 2节点 对应 红黑树 就是一个单独的黑色节点
  • 3节点 对应 红黑树 上黑下红 ,这里有2种 上黑左红 和上黑右红
  • 4节点 对应 红黑树 上黑下面2个红

这3个关系牢记在心,我们其实可以看出每个节点都会只有一个黑色节点。把一颗红黑树转变成234树,可以从下往上看,父节点是黑色,当前节点是红色的 ,可以合并3或者4节点。

查询

查询和二叉树的查询是一样的,从根下面开始找,逐个判断值,小于就继续找左子树,大于找右子树。

插入 借助3个等价关系来处理

我们这里有个约束条件,插入的默认都是红色的。为什么这样做,因为当我们把红黑树转变成234树的时候,其实234树的每个节点都应该有且只有一个黑节点,红色节点可以有多个,这样黑色节点其实就是表示一个234节点,他们就有了个映射关系。我们从空开始逐个进行。

  • 树一开始是空的,直接插入,因为根节点定义是黑色的,所以变黑
  • 树不是空的,插入的位置肯定是挂在某个父节点上面,所以有2种情况,a.父节点是黑 b父节点红色,我们看等价关系,可以知道,红色节点是可以直接挂在黑色节点下面的。但是如果是父亲是红色节点,那么违反了等价关系,不能出现2个红色连一起的情况,这个时候我们需要进行调整。

调整

我们的调整都是基于上面已经排好的情况的,因为每次我们插入都是调整好了的。调整需要和234树进行分情况处理

  • 插入到2节点(一个黑色节点)这种情况上面说了可以直接插入,就变成了3节点上黑下红。不需要调整
  • 插入到3节点(上黑下红),严格来说,这里插入的位置有6种。
    上黑左红:3种(左孩子的下面2种+黑节点的右边)
    上黑右红:3种(右孩子的下面2种+黑色节点的左边)
    上面讲了,只有插入的位置父节点是红色情况才需要调整,如果直接插入到黑节点的左边或者右边,那么就变成了4节点,无需调整。
    因此需要调整的是3节点的4种情况。而这里面的4种情况我们只需要分析2种就行了,另外2种镜像操作。
    分析上黑左红情况,插入点:左红的左孩子。现在的状态是从上到下为 黑 -红 - 红,想一想4节点是什么样的,4节点为上黑左右红,那我们可以把这个转变成4节点。
    怎么转变:黑(A)- 红(B)-红(C待插入) 他们是在一条线上。
    最终是变成4节点,可以通过把A进行右旋,那么就变成了


     A (黑)                                        B
    /                                              /   \
  B (红)                   =>                   C      A        然后B变黑,A变红,调整完成
 /
C (红)

分析上黑右红 可以把B左旋成上一种情况进行处理

        A(黑)								   A()                 B
      /                                        /                    / \
     B (红)               =>                B(红)    =>        C     A
      \                                      /
       C  (红)                            C(红)

如果直接把A进行右旋,虽然整体大小顺序合法,但是B没有左子树,那么当B变成A为父节点的那个位置时候,B的左边就空了,整颗树就不平衡了。

           B
            \
            A
            /
          C 

这个形态不属于任何234节点任何一种。

  • 插入到4节点(3个元素)
      A()
     / \
  B(红)C(红)
 /
D(红 待插入) 

D的位置可以有4个方向,对于234树的4节点插入,总会产生裂变 分裂出2个子节点,一个是2节点,一个是3节点。对于父节点可能是单独的黑节点,也可能是与别人组合的红节点,都是可能的。而且裂变之后,上升的父节点可能还会跟别的兄弟节点进行合并继续裂变。这里就是继续递归父节点的过程。
那么我们也要把他转变成2种节点,一个黑色节点和上黑下红,也就是说得至少得有2个黑色的节点。
这里D可以与父节点B组成一个上黑下红的3节点,而另一边的C可以变成一个独立的黑色2结点。因此可以把B和C变黑。问题来了,如果B和C变黑色,A不变色,那么这个局部的树就会多了一个黑色节点,那么整个树会黑色不平衡,因此我们还得把A变成红色才行。
根据234树的裂变规则,父亲节点可能还会继续合并后裂变,对应于我们红黑树,A变成了红色节点,那么A得上面可能也是红色的,所以我们继续递归A节点就行了。

以上就是红黑树的插入过程。

删除 略微复杂

  • 删除和二叉树的删除一样,当删除的节点有左右孩子的时候,直接找它的前驱或者后继节点,然后交换值,这样就变成了删下面的前驱或者后继节点了。
  • 前驱或者后继节点的位置有3种:a. 落在叶子节点上 b 落在倒数第二层且有一个孩子的节点上 c落在上层节点 。画个图想一想就知道了,这个不懂的可以百度下查找前驱或者后继节点的博客。
  • 问题就变成了删除叶子节点或者倒数第二层有一个孩子的节点。而对于删除,落在上层节点的情况可以不考虑,因为如果是落在上层节点上,那么这个节点肯定没有左孩子或者右孩子,那就是倒数第二层。

调整

删除为叶子节点情况

a. 叶子是红色
红色节点不影响黑色的平衡,直接删除
b.叶子是黑色
删除了会影响平衡 需要调整。
红黑树的黑色叶子节点,对应于234树就是一个2节点 。删除了他,那么他需要找兄弟节点去借。所以继续分析兄弟节点能不能借出的情况。
能借出的情况 兄弟节点是3或者4结点,因为他们有>1个的元素,有红节点。

		      兄弟3节点 删除B情况                   兄弟4节点
       A(?)                   A(?)                      A(?)
      / \                     /  \                       / \
    B() C(黑)            B() C()             B(黑) C()
           \                       /                       /   \ 
            D ()                D()                   D(红)E(红)

怎么借?我们肯定不能通过直接赋值的方式借过来,因为还要考虑顺序,所以得通过旋转的方式来借。我总结的核心点就是相互顶替来达到原来的颜色状态且顺序合法

  • 拿3节点第一种情况来说,B是将要删除的点,他是黑色的,父亲我们不确定,可以为黑也可以为红,因为不影响这个局部的树的黑色平衡。B - A - C- D,只要我们把A顶替B,把C顶替A,D顶替C就行得通了。其实这个顶替在函数上实现就是旋转操作在这里就是A左旋,不过也不能直接随便旋转的,为什么?
    因为旋转不会考虑C有没有右孩子的情况,假如C没有了右孩子,那么左旋后C变成了父亲,C的右边就空的了。所以必须得要一个元素来顶替C。因此对于3节点是第二种情况,我们得把C进行右旋就变成
         A(?)
        /  \
       B()D()
             \
              C() 

然后用第一种情况处理

  • 4节点处理: 4节点左边和右边都有孩子,不需要经过什么特殊的旋转处理,直接用3节点第一种情况处理即可。

不能接出情况 兄弟节点是2节点只有一个元素 这个情况兄弟无法接出,那么就看父亲了

   A(?)
  / \
B()C(黑色) 
  • 假如父亲是红色节点,可以拿父亲来顶替下面2个孩子,注意是2个,因为B和C 是在同一层,B是要删除的,那么把C也删了(C变红),整棵树仍然只少了一个,而父亲是红色的,直接把父亲变成黑色就顶替上就OK了。
  • 假如父亲是黑色的,父亲借不了。我们先把C变红,相当于这棵树还是只少了一个黑色的,我们再把父亲当做要删除的黑色叶子节点,继续下一轮递归调整。
删除为倒数第二层且有一个孩子的情况
   A
   /
 B(黑)
  \
   C(红)  

要删除B,把B唯一的孩子顶上去就行了,假如B是黑色,C顶上去也变成黑色。因为删除最终也是落在234树的叶子节点,无非就3种,2节点,3节点和4节点,B只能是黑色,C只能是红色。

关于兄弟节点是红色情况
 						  转变为234树
     A(只能是黑)                              AC                              C
   /  \                                       /|\                             / \
  B()C(红色)                  =>           B  D E          =>A左旋          A   E 
      / \                              										/ \
     D()E()															   B   D			

肯定有人说兄弟节点还有是红色情况呢,如果在红黑树上兄弟节点是红色,那么这个兄弟节点在234树上对应起来其实并不是真正的兄弟节点,比如这个里的C,他其实是和A在一起的,组成一个3节点,且C下面肯定还有节点。那么我们得要先找打真正的兄弟节点,或许你也可以直接在大脑种想象,C的左孩子是他的兄弟节点,但是为了在红黑2叉树上处理方便,我们可以把他转变下,把A进行左旋,那么B和D就成了真正的兄弟节点,然后同样套用之前的方式进行处理。

实现的JAVA代码

package com.lsz.im.test;

import lombok.Getter;
import lombok.Setter;


public class RBTree<K extends Comparable<K>, V> {
    public static final boolean BLACK = true;
    public static final boolean RED = false;
    private Node<K, V> root = null;

    @Getter
    @Setter
    public static class Node<K extends Comparable<K>, V> {
        private K key;
        private V value;
        private boolean color = BLACK;
        private Node<K, V> parent;
        private Node<K, V> left;
        private Node<K, V> right;

        public Node(K key, V value, Node<K, V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        public Node() {
        }

    }

    private void writeArray(Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null) return;
        // 先将当前节点保存到二维数组中
        res[rowIndex][columnIndex] = String.valueOf(currNode.key + "(" + (currNode.color ? "黑" : "红") + ")");

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层,则返回
        if (currLevel == treeDepth) return;
        // 计算当前行到下一行,每个元素之间的间隔(下一行的列索引与当前元素的列索引之间的间隔)
        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断,若有左儿子,则记录相应的"/"与左儿子的值
        if (currNode.left != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

        // 对右儿子进行判断,若有右儿子,则记录相应的"\"与右儿子的值
        if (currNode.right != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }

    public void show() {
        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());
        }
    }

    private int getTreeDepth(Node root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
    }


    public boolean colorOf(Node<K, V> node) {
        return node == null ? BLACK : node.color;
    }

    public Node<K, V> parentOf(Node<K, V> node) {
        return node == null ? null : node.parent;
    }

    private Node<K, V> leftOf(Node<K, V> node) {
        return (node == null) ? null : node.left;
    }

    private Node<K, V> rightOf(Node<K, V> node) {
        return (node == null) ? null : node.right;
    }

    private void setColor(Node<K, V> node, boolean color) {
        if (node != null) {
            node.color = color;
        }
    }

    /**
     * <pre>
     *        tp               tp
     *       /                 /
     *      a                 c
     *     / \    =>左旋      / \
     *    b   c             a    e
     *       / \          / \
     *      d   e        b   d
     *
     * </pre>
     * <p>
     * 左旋 必备条件 target 有右孩子
     *
     * @param a
     */
    public void leftRotate(Node<K, V> a) {
        if (a == null || a.right == null) {
            return;
        }
        Node<K, V> c = a.right;
        Node<K, V> d = c.left;
        Node<K, V> targetParent = a.parent;
        c.left = a;
        a.parent = c;
        a.right = d;
        //考虑a的父节点
        c.parent = targetParent;
        if (targetParent == null) {
            root = c;
        } else if (targetParent.left == a) {
            targetParent.left = c;
        } else if (targetParent.right == a) {
            targetParent.right = c;
        }
    }

    /**
     * 右旋 必备条件 target 有左孩子
     *
     * @param c
     */
    public void rightRotate(Node<K, V> c) {
        if (c == null || c.left == null) {
            return;
        }
        Node<K, V> a = c.left;
        Node<K, V> d = a.right;
        Node<K, V> targetParent = c.parent;
        a.right = c;
        c.parent = a;
        c.left = d;
        a.parent = targetParent;
        if (targetParent == null) {
            root = a;
        } else if (targetParent.left == c) {
            targetParent.left = a;
        } else if (targetParent.right == c) {
            targetParent.right = a;
        }
    }

    public V get(K key) {
        Node<K, V> node = getNode(key);
        return node == null ? null : node.value;
    }

    private Node<K, V> getNode(K key) {
        Node<K, V> find = root;
        while (find != null) {
            int cmp = key.compareTo(find.key);
            if (cmp > 0) {
                find = find.right;
            } else if (cmp < 0) {
                find = find.left;
            } else {
                break;
            }
        }
        return find;
    }


    /**
     * 插入
     *
     * @param key
     * @param value
     * @return
     */
    public V put(K key, V value) {
        if (key == null) {
            throw new UnsupportedOperationException("key 不能为空");
        }
        if (root == null) {
            root = new Node<>(key, value, null);
        }
        //查找应该放到哪个节点下面 从跟开始找
        Node<K, V> tmp = this.root;
        Node<K, V> parent = null;
        int cmp = 0;
        while (tmp != null) {
            parent = tmp;
            cmp = key.compareTo(tmp.key);
            if (cmp > 0) {
                tmp = tmp.right;
            } else if (cmp < 0) {
                tmp = tmp.left;
            } else {
                V oldValue = tmp.getValue();
                tmp.value = value;
                return oldValue;
            }
        }
        Node<K, V> newNode = new Node<>(key, value, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        fixAfterInsert(newNode);
        return null;
    }

    /**
     * 插入都是红色的<br>
     * 调整插入后的红黑树,需要调整的基本条件是 插入的值父亲是红色<br>
     * 1.插入到3节点6种情况的4种情况<br>
     * 2.插入4节点的4种情况<br>
     *
     * @param newNode
     */
    private void fixAfterInsert(Node<K, V> newNode) {
        if (newNode == null) {
            return;
        }
        if (newNode == root) {
            root.color = BLACK;
            return;
        }
        newNode.color = RED;
        if (colorOf(parentOf(newNode)) == RED) {
            if (parentOf(newNode) == leftOf(parentOf(parentOf(newNode)))) { //左倾情况
                Node<K, V> uncle = rightOf(parentOf(parentOf(newNode)));
                if (colorOf(uncle) == BLACK) {              //3节点 parent.parent可能发送空指针异常,所以得封装
                    if (newNode == rightOf(parentOf(newNode))) {
                        //当前是处于右边 旋转成 左边情况减少处理
                        newNode = parentOf(newNode);
                        leftRotate(newNode);
                    }
                    setColor(parentOf(newNode), BLACK);
                    setColor(parentOf(parentOf(newNode)), RED);
                    rightRotate(parentOf(parentOf(newNode)));    //右旋爷节点
                } else {                                     //4节点
                    //父亲和叔叔 红变黑 爷爷变红
                    setColor(parentOf(newNode), BLACK);
                    setColor(uncle, BLACK);
                    setColor(parentOf(parentOf(newNode)), RED);  //爷爷变红了就转变成插入是爷爷红节点的情况 循环一遍
                    fixAfterInsert(parentOf(parentOf(newNode)));
                }
            } else {   //右倾
                Node<K, V> uncle = leftOf(parentOf(parentOf(newNode)));
                if (colorOf(uncle) == BLACK) {  //3节点
                    if (newNode == leftOf(parentOf(newNode))) {
                        newNode = parentOf(newNode);
                        rightRotate(newNode);
                    }
                    setColor(parentOf(newNode), BLACK);
                    setColor(parentOf(parentOf(newNode)), RED);
                    leftRotate(parentOf(parentOf(newNode)));
                } else {                                    //4节点
                    setColor(parentOf(newNode), BLACK);
                    setColor(uncle, BLACK);
                    setColor(parentOf(parentOf(newNode)), RED);
                    fixAfterInsert(parentOf(parentOf(newNode)));
                }
            }
        }
    }

    /**
     * 删除 <br>
     * <p>
     * 1.要删除的如果是有2个孩子,寻找他的后继。后继和要删除的互换值,再删除后继节点。后继必然是处于234的叶子上,
     * 对应于红黑树的倒数1或倒数2层 <br>
     * 2.要删除的处于倒数第一层,如果是红色节点不需要调整,如果是黑色需要调整   <br>
     * 3.要删除的处于倒数第二层,属于3节点,所以该节点必然是黑节点,且下面是一个红色孩子,删除黑色节点,然后把下面的红色节点顶替上来,颜色变成黑色<br>
     *
     * @param key
     */
    public V remove(K key) {
        Node<K, V> node = getNode(key);
        if (node == null)
            return null;
        V oldValue = node.value;
        //删除
        if (node.left != null && node.right != null) {   //值交换,变成删除后继
            Node<K, V> s = successor(node);
            node.key = s.key;
            node.value = s.value;
            node = s;
        }

        Node<K, V> child = node.left == null ? node.right : node.left;
        if (child == null) {                       //处理倒数第一
            if (node.parent == null) {
                root = null;
            } else {
                if (node.color == BLACK) {
                    fixAfterDelete(node);
                }
                if (node == node.parent.left) node.parent.left = null;
                if (node == node.parent.right) node.parent.right = null;
                node.parent = null;
            }
        } else {                                //处理倒数第二
            child.parent = node.parent;
            if (node.parent == null) root = child;
            else if (node == node.parent.left)
                node.parent.left = child;
            else
                node.parent.right = child;
            node.parent = node.left = node.right = null;
            if (node.color == BLACK)
                fixAfterDelete(child);
            else {
                System.err.println("出现了删除2节点倒数第二层不是黑色情况!");
            }
        }
        return oldValue;
    }

    private void fixAfterDelete(Node<K, V> node) {
        if (node.color == RED || node == root) setColor(node, BLACK); //上黑下红,删除黑,红色顶替,变色,或者根节点
        else {                                                      //找兄弟借
            //右倾情况 删除的在左边
            if (node == leftOf(parentOf(node))) {
                Node<K, V> brother = rightOf(parentOf(node));
                if (colorOf(brother) == RED) {  //这种情况 红黑树的兄弟并不是234树对应的兄弟,左旋
                    setColor(brother, BLACK);
                    setColor(parentOf(node), RED);
                    leftRotate(parentOf(node));
                    brother = rightOf(parentOf(node));  //其实就是之前的红色节点的左孩子
                }
                //然后找兄弟节点,兄弟节点有3种。1.兄弟节点是2节点单独一个黑色,无法接 2.为3节点,有一个可以借 3.4节点有2个可以借
                //总结来说,34节点都可以借得到,借的过程其实就是相互顶替过程,包括颜色。所以分成2大类,兄弟能借,兄弟没得借

                if (noChild(brother)) {  //兄弟没得借
                    //兄弟没得借,那么大家一起损失,问题就变成待删除是父节点的情况。
                    // 父节点2种 1父节点是红色,直接变黑就行了,相当于补了一个黑色。为黑,那么就需要再一次循环
                    //方法一开始就进行了判断为红色情况,所以可以统一处理 这里记住并没有实际删除,删除是在外层操作的,这里是假设删除。
                    //所以整体删除的其实只有一个
                    setColor(brother, RED);
                    fixAfterDelete(parentOf(node));
                } else {                                                                    //兄弟34节点,可以借
                    //相互顶替过程,要保证顺序合法,旋转可以保证顺序,但是无法保证颜色。
                    // 相互顶替含义包含2个意思就是待删除-父节点-兄弟节点-兄弟子节点 ,a.颜色相互顶替 b.节点相互顶替
                    //左旋是 兄弟节点的左子树会挂在父节点的右孩子上 如果兄弟节点没有右孩子,那么兄弟节点称为父节点之后就没有右子树,然而我们是需要顶替之后还要保证黑色节点和原来一致,
                    //原来的兄弟节点是黑色节点,那么兄弟节点顶替父节点后,父节点顶替待删除的,兄弟的子节点必须要顶替兄弟节点,不然黑色节点达不到原来的分布情况,因此3节点兄弟节点需要做一次旋转
                    //兄弟节点的右孩子必须保证有,这样旋转变色之后,树的左右2边颜色又会恢复到原来状态
                    if (colorOf(rightOf(brother)) == BLACK) {
                        setColor(brother, RED);
                        setColor(leftOf(brother), BLACK);
                        rightRotate(brother);
                        brother = rightOf(parentOf(node));
                    }
                    //34节点可以一起处理了  待删除-父节点-兄弟节点-兄弟右子节点
                    setColor(brother, colorOf(parentOf(node)));
                    setColor(parentOf(node), BLACK);
                    setColor(rightOf(brother), BLACK);
                    leftRotate(parentOf(node));
                }
            } else {           //左倾情况,删除的再右边,镜像操作
                Node<K, V> brother = leftOf(parentOf(node));
                if (colorOf(brother) == RED) {  //找真正的兄弟
                    setColor(brother, BLACK);
                    setColor(parentOf(node), RED);
                    rightRotate(parentOf(node));
                    brother = leftOf(parentOf(node));
                }
                if (noChild(node)) {
                    setColor(brother, RED);
                    fixAfterDelete(parentOf(node));
                } else {
                    if (colorOf(leftOf(brother)) == BLACK) {
                        setColor(brother, RED);
                        setColor(rightOf(brother), BLACK);
                        leftRotate(brother);
                        brother = leftOf(parentOf(node));
                    }
                    setColor(brother, colorOf(parentOf(node)));
                    setColor(parentOf(node), BLACK);
                    setColor(leftOf(brother), BLACK);
                    rightRotate(parentOf(node));
                }
            }
        }
    }

    private boolean noChild(Node node) {
        return colorOf(leftOf(node)) == BLACK && colorOf(rightOf(node)) == BLACK;
    }

    Node<K, V> successor(Node<K, V> node) {
        if (node == null) {
            return null;
        }
        //右边的最小值(最左边)
        if (node.right != null) {
            Node<K, V> tmp = node.right;
            while (tmp.left != null) {
                tmp = tmp.left;
            }
            return tmp;
        } else {
            //往上找 后继,找第一个父子关系是左关系的父亲,在删除中这里走不到,因为如果没有左右节点的删除,可以直接删,不需要找后继
            Node<K, V> cur = node;
            Node<K, V> p = node.parent;
            while (p != null && cur == p.right) {
                cur = p;
                p = p.parent;
            }
            return p;
        }
    }

}

测试代码

package com.lsz.im.test;

import lombok.extern.slf4j.Slf4j;

import java.util.Scanner;
// -XX:+UseG1GC
@Slf4j
public class Test {
    private String[] a;
    Test(){
        a=new String[1024*5];
        int l=a.length;
    }
    public static void main(String[] args) {
        RBTree<Integer,String> tree=new RBTree<>();
        String next = null;
        Scanner scanner=new Scanner(System.in);
        System.out.println("开始插入,请输入");
        while(true){
            next = scanner.next();
            if(next.equals("stop")){
                break;
            }
            tree.put(Integer.valueOf(next),next);
            tree.show();
        }
        System.out.println("开始删除,请输入");
        while (true){
            next = scanner.next();
            if(next.equals("quit")) break;
            tree.remove(Integer.valueOf(next));
            tree.show();
        }

    }


//    public void sayA() throws InterruptedException {
//        System.out.println(Thread.currentThread().getName()+"---> A");
//        Thread.sleep(1000);
//    }
//
//    public void sayB() throws InterruptedException {
//        System.out.println(Thread.currentThread().getName()+"---> B");
//
//        Thread.sleep(500);
//    }
}