红黑树学习笔记（自己实现一个简单的红黑树）

红黑树学习笔记（自己实现一个简单的红黑树）

最近在学习树的一些东西，想把树从头开始总结一下巩固自己的印象。

1、树结构入门 1.1、什么是树？

树（tree）是一种抽象数据类型（ADT），用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点通过连接它们的边组成一个具有层次关系的集合。

把它叫做树是因为它看起来像一颗倒挂的树，也就是说它是根朝上的，而叶是朝下的。

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

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

1.2、树结构常用术语

• 路径：顺着节点的边从一个节点走到另一个节点，所经过的节点的顺序排列就称为路径。
• 根：树顶端的节点称为根。一棵树只有一个根，如果要把一个节点和边的集合称为树，那么从根到其他任何一个节点都必须有且只有一条路径。A是根节点。
• 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
• 子节点：一个节点含有的子树的节点称为该节点的子节点；F、G是C节点的子节点。
• 兄弟节点：具有相同父节点的节点互称为兄弟节点；F、G节点互为兄弟节点。
• 叶子节点：没有子节点的节点称为叶子节点，也叫叶节点，比如上图的H、E、F、G都是叶子节点。
• 子树：每个节点都可以作为子树的根，它和它所有的子节点、子节点的子节点等都包含在子树中。
• 节点的层次：从根节点开始定义，根为第一层，根的子节点为第二层，以此类推。
• 深度：对于任意节点n，n的深度为从根到n的唯一路径长，根的深度为0；（从上往下看）
• 高度：对于任意节点n，n的高度为从n到一片树叶的最长路径长，所有树叶的高度为 0;(从下往上看)

public class BinaryTreeDemo {
    public static void main(String[] args) {
        //先需要创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建需要的节点
        HeroNode heroNode1 = new HeroNode(1, "宋江");
        HeroNode heroNode2 = new HeroNode(2, "吴用");
        HeroNode heroNode3 = new HeroNode(3, "花荣");
        HeroNode heroNode4 = new HeroNode(4, "林冲");
        HeroNode heroNode5 = new HeroNode(5, "关胜");
        HeroNode heroNode6 = new HeroNode(6, "武松");
        HeroNode heroNode7 = new HeroNode(7, "鲁智深");

        //说明 我们先手动创建二叉树 后面我们学习递归的方式创建二叉树
        heroNode1.setLeft(heroNode2);
        heroNode1.setRight(heroNode3);
        heroNode2.setLeft(heroNode4);
        heroNode2.setRight(heroNode5);
        heroNode3.setLeft(heroNode6);
        heroNode3.setRight(heroNode7);

        binaryTree.setRoot(heroNode1);
        

        //System.out.println(binaryTree.postOrderSearch(3));

       // System.out.println("删除前:=============");
        binaryTree.binaryTreeBFS();
        //System.out.println("删除后:=============");
        //binaryTree.delNode(1);
        //binaryTree.preOrder();
    }
}

//定义BinaryTree类  二叉树类
class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("当前二叉树为空 无法遍历");
        }
    }

    public void preOrdeNoRecur(){
        if (this.root != null) {
            this.root.preOrdeNoRecur();
        } else {
            System.out.println("当前二叉树为空 无法遍历");
        }
    }

    public void postOrderNORecur(){
        if (this.root != null) {
            this.root.postOrderNORecur();
        } else {
            System.out.println("当前二叉树为空 无法遍历");
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("当前二叉树为空 无法遍历");
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("当前二叉树为空 无法遍历");
        }
    }

    public void binaryTreeBFS(){
        if (this.root != null) {
            this.root.binaryTreeBFS();
        } else {
            System.out.println("当前二叉树为空 无法遍历");
        }
    }

    //前序查找
    public HeroNode preOrderSearch(int no){
        if(this.root!=null){
            return this.root.preOrderSearch(no);
        }else{
            return null;
        }
    }

    //中序查找
    public HeroNode infixOrderSearch(int no){
        if(this.root!=null){
            return this.root.infixOrderSearch(no);
        }else{
            return null;
        }
    }

    //后序查找
    public HeroNode postOrderSearch(int no){
        if(this.root!=null){
            return this.root.postOrderSearch(no);
        }else{
            return null;
        }
    }

    //删除节点
    public void delNode(int no){
        if(root!=null){
            if(root.getNo()==no){
                root=null;
            }else{
                //递归删除
                root.delNode(no);
            }
        }else{
            System.out.println("空树无法删除");
        }
    }
}

//先创建Heronode 节点
class HeroNode {
    private int no;
    private String name;
    private HeroNode left; //默认为null
    private HeroNode right; //默认null

    //在初始化节点的时候不需要初始化左右子节点 在遍历树的时候需要用来判断是否为空来进行遍历
    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public HeroNode() {
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + ''' +
                '}';
    }

    //编写前序遍历的方法
    public void preOrder() {
        System.out.println(this); //先输出当前节点
        //递归向左子树进行先序遍历
        if (this.getLeft() != null) {
            this.getLeft().preOrder();
        }
        //递归向右子树进行遍历
        if (this.getRight() != null) {
            this.right.preOrder();
        }
    }

    //中序遍历
    public void infixOrder() {
        //递归向左子树中序遍历
        if (this.getLeft() != null) {
            this.getLeft().infixOrder();
        }
        //输出当前节点
        System.out.println(this);
        //递归向右子树中序遍历
        if (this.getRight() != null) {
            this.getRight().infixOrder();
        }
    }

    //后序遍历
    public void postOrder() {
        //递归向左子树进行遍历
        if (this.getLeft() != null) {
            this.getLeft().postOrder();
        }
        //递归向右子树进行遍历
        if (this.getRight() != null) {
            this.getRight().postOrder();
        }
        //输出当前节点
        System.out.println(this);
    }

    
    public void preOrdeNoRecur(){
        HeroNode temp = this; // 注意，此时this 代表的是root节点
        Stack stack = new Stack<>();
        stack.push(temp); // 根节点入栈
        while (!stack.isEmpty()){ // 当栈为空的时候结束循环
            // 1.访问根节点
            HeroNode heronode = stack.pop();
            System.out.println(heroNode);
            // 2.如果根节点存在右子树，则将右子树入栈
            if(heroNode.getRight() != null){
                stack.push(heroNode.getRight());
            }
            // 3.如果根节点存在左子树，则将左子树入栈
            if(heroNode.getLeft() != null){
                stack.push(heroNode.getLeft());
            }
        }
    }

    
    public void infixOrderNoRecur(){
        HeroNode temp = this; // 注意，此时this 代表的是root节点
        Stack stack = new Stack<>();
        while (temp != null || !stack.isEmpty()){
            // 将根节点入栈
            // 2.将所有的左子树入栈
            while (temp != null){
                stack.push(temp);
                temp = temp.getLeft();
            }
            // 3.访问栈顶元素
            temp = stack.pop();
            System.out.println(temp);
            // 4.如果栈顶元素存在右子树，则将右子树赋值给temp，也就是将右孩子入栈
            if(temp.getRight() != null){
                temp = temp.getRight();
            }else{
                // 否则，将temp置为null，表示下次要访问的是栈顶元素
                temp = null;
            }
        }
    }

    
    public void postOrderNORecur(){
        HeroNode temp = this; // 注意，此时this 代表的是root节点
        Stack stack = new Stack<>();
        HeroNode prev = null; // 代表上一次访问的节点
        while (temp != null || !stack.isEmpty()){
            // 1.将根节点及其左子树入栈
            while (temp != null){
                stack.push(temp);
                temp = temp.getLeft();
            }
            if(!stack.isEmpty()){
                // 2.获取栈顶元素
                temp = stack.peek();
                // 3.没有右子树或者已经被访问过了
                if(temp.getRight() == null || temp.getRight() == prev){
                    // 则可以访问栈顶元素
                    temp = stack.pop();
                    System.out.println(temp);
                    // 标记上一次访问的节点
                    prev = temp;
                    temp = null;
                }else {
                    temp = temp.getRight();
                }
            }
        }
    }

    // 层序遍历
    public void binaryTreeBFS(){
        List temp;
        List queue = new linkedList<>();
        queue.add(this);

        while (!queue.isEmpty()){
            temp = new linkedList<>();
            for (HeroNode node : queue){
                if(node.left != null) temp.add(node.left);
                if(node.right != null) temp.add(node.right);
                System.out.print(node.no + " ");
            }
            queue = temp;
        }
    }

    //前序遍历查找
    
    public HeroNode preOrderSearch(int no) {
        //先与当前节点进行比较
        if (this.getNo() == no) {
            return this;
        }
        //如果当前节点不是 则判断当前节点的左子节点是否为空 如果不为空 则递归前序查找
        //如果左递归的前序查找 找到节点 则返回
        HeroNode result = null;
        if (this.getLeft() != null) {
            result = this.getLeft().preOrderSearch(no);
        }
        if (result != null) { //说明我们左子树找到该对应节点
            return result;
        }
        //如果左递归的前序查找 找到节点 则返回 否则继续判断
        //当前节点的右子节点是否为空 如果不为空 则继续向右递归前序查找
        if (this.getRight() != null) {
            result = this.getRight().preOrderSearch(no);
        }
        return result;
    }

    //中序遍历查找
    public HeroNode infixOrderSearch(int no){
        //先判断当前节点的左子节点是否为空
        HeroNode result=null;
        if(this.getLeft()!=null){ //注意 这里必须要使用一个变量来进行接收 否则返回左子树的的最后一个子节点
            result=this.getLeft().infixOrderSearch(no);
        }
        if(result!=null){
            return result;
        }
        //如果找到 则返回 如果没有找到 就和当前节点比较 如果是则返回当前节点
        if(this.getNo()==no){
            return this;
        }
        //如果比较为falae 则继续向右递归进行中序查找
        if(this.getRight()!=null){
            result=this.getRight().infixOrderSearch(no);
        }
        return result;
    }

    //后序查找
    public HeroNode postOrderSearch(int no){
        //先判断当前节点的左子节点是否为空 如果为空 则递归向后查找
        HeroNode result=null;
        if(this.getLeft()!=null){
            result =this.getLeft().postOrderSearch(no);
        }
        if(result!=null){ //说明在左子树找到
            return result;
        }
        //如果左子树没有找到 则向右子树递归进行后序查找
        if(this.getRight()!=null){
            result=this.getRight().postOrderSearch(no);
        }
        if(result!=null){
            return result;
        }
        //如果左右子树都没有找到 就比较当前节点
        if(this.getNo()==no){
            return this;
        }
        return result;
    }

    // 递归删除节点
    // 1.如果删除的是叶子节点，则删除该节点
    // 2.如果删除的结点是非叶子节点，则删除该子树
    public void delNode01(int no){
        
    }

    //递归删除节点
    //1.如果删除的是叶子节点 则删除该节点
    //2.如果删除的节点是非叶子节点 则删除该子树
    public void delNode(int no){
         

        //如果当前节点的左子节点不为空 并且左子节点就是要删除的节点 就将this.left=null即可(并且就结束递归删除)
        if(this.getLeft()!=null && this.getLeft().getNo()==no){
             this.setLeft(null);
             return;
         }
        //3>如果当前节点的右子节点不为空 并且右子节点就是要删除的节点 就将this.right=null
        if(this.getRight()!=null && this.getRight().getNo()==no){
            //删除的话return回到上一个节点 然后这个节点已经被置空了 回到上一个节点继续判断右子树进行递归判断删除
            this.setRight(null);
            return;
        }
        //4>如果第2步和第3步没有删除节点 那么我们就需要向左子树进行递归删除
        if(this.getLeft()!=null){
            this.getLeft().delNode(no);
        }
        //5>如果第2步和第3步和第4步没有删除节点 那么我们就需要向右子树进行递归删除
        if(this.getRight()!=null){
            this.getRight().delNode(no);
        }
    }

    
    public int maxDepth(){
        if(this == null){
            return 0;
        }
        return Math.max(this.left.maxDepth(), this.right.maxDepth()) + 1;
    }

    
    public int maxDepth1(HeroNode root){

        if(root == null){
            return 0;
        }
        List queue = new linkedList<>();
        queue.add(root);
        List temp;
        int res = 0; // 用于统计二叉树的层数

        while (!queue.isEmpty()){
            temp = new linkedList<>();
            for (HeroNode node : queue){
                if(node.left != null){
                    temp.add(node.left);
                }
                if(node.right != null){
                    temp.add(node.right);
                }
                queue = temp;
                res ++;
            }
        }
        return res;
    }
}

1.3、二叉搜索树

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

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

若它的右子树不空，则右子树上所有节点的值均小于它的根节点的值

它的左右子树也分别都为二叉搜索树。

二叉搜索树 - 查找节点

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

• 查找值比当前节点值大的话，则搜索右子树
• 查找值等于当前节点的值，则停止搜索（终止条件）
• 查找值小于当前节点值，则所搜左子树

二叉搜索树 - 插入节点

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

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

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

二叉搜索树 - 遍历节点

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

• 中序遍历：左子树 —> 根节点 —> 右子树
• 前序遍历：根节点 —> 左子树 —> 右子树
• 后续遍历：左子树 —> 右子树 —> 根节点

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

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

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

二叉搜索树 - 删除节点

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

• 该节点是叶子节点（没有子节点）
• 该节点有一个子节点
• 该节点有两个子节点

删除没有子节点的节点

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

删除有一个子节点的节点

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

删除有两个子节点的节点

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

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

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

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

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

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

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

删除有必要吗？

通过上面的删除分类讨论，我们发现删除其实是挺复杂的，那么其实我们可以不用真正的删除该节点，只需要在 Node 类中添加一个标识字段 isDelete，当该字段为true的时候，表示该节点已经被删除，反之则没有删除，这样删除节点就不会改变树的结构了。

影响就是查询时需要判断一下节点是否已经被删除。

二叉树搜索树 - 时间复杂度分析

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

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

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

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

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(arr[mid] < data){
            low = mid + 1;
        }else if(arr[mid] == data){
            return mid;
        }else{
            height = mid - 1;
        }
    }
    return -1;
}


public static int binarySearch(int[] arr, int left, int right, int data){
    // 递归结束条件
    if(left > right){
        return -1;
    }
    int mid = left + (right - left) / 2;
    if(arr[mid] < data){
        return binarySearch(arr, mid + 1, right, data);
    }else if(arr[mid] == data){
        return mid;
    }else{
        return binarySearch(arr, left, mid - 1, data);
    }
}

2、二分查找最大的缺陷是什么？

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

3、数组有什么缺陷？

没有办法快速插入，也没有办法扩容（想要扩容只能创建一个容量更大的新数组来拷贝原数组）以达到扩容的目的

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

使用 二叉搜索树

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

第几次查询剩余待查询元素数量1N / 22N / (2 ^ 2)3N / (2 ^ 3)KN / (2 ^ K)

从上表可以看出N / (2 ^ k)肯定是大于等于1，也就是N / (2 ^ K) >= 1，我们计算时间复杂度是按照最坏的情况进行计算，也就是查到剩余最后一个数才查到我们想要的数据，也就是

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

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

这颗二叉树的查询效率如何？

O(N)

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

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

那这个时候 AVL树就应运而生，这里不再细说，推荐一个博主：java程序员 - 天天，看完以后你就明白了

这里附上 AVL 树的代码

public class BinaryTree,V> {

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree<>();
        
        Scanner scanner = new Scanner(System.in);
        //TreeOperation.show(binaryTree.root);
        while (true){
            System.out.println("请输入要插入的节点：");
            String next = scanner.next();
            //binaryTree.delete(Integer.parseInt(next));
            binaryTree.insert(Integer.parseInt(next),next);
            TreeOperation.show(binaryTree.root);
        }


        //TreeOperation.show(binaryTree.root);

        

    }

    private Node root; // 二叉树的根节点

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    // 二叉查找树的插入
    public void insert(K key,V value){
        // 先判断该二叉树是否是空树
        if(this.root == null){
            this.root = new Node(key,value);
            return;
        }

        // 保存每次比较的节点，因为第一次比较的是根节点，所以此时用根节点作为起始值
        Node temp = this.root;
        // 定义其父节点
        Node parent = null;
        int i =0;
        while (temp != null){
            parent = temp;
            i = key.compareTo((K) temp.getKey());
            if( i > 0){
                temp = temp.getRight();
            }else if(i == 0){
                temp.setValue(value);
                return;
            }else{
                temp = temp.getLeft();
            }
        }
        // 注意，此时退出循环的时候，因为temp为null，而且二叉树是单向指针，所以应该以父节点来寻找要插入节点的位置
        if(i > 0){
            parent.setRight(new Node(key,value,null,null,parent));
        }else{
            parent.setLeft(new Node(key,value,null,null,parent));
        }
        // 插入的时候调整二叉树的平衡（因为我们插入的是叶子节点，所以不存在叶子节点的情况，需要从父节点开始找起）
        rebalance(parent);
    }

    // 调整二叉树的平衡（平衡二叉树的每个节点的左子树和右子树的高度最多差1）
    public void rebalance(Node node){
        // 如果父节点为空，则不需要进行平衡了
        if(node == null){
            return;
        }
        // 由于子树的平衡旋转可能影响父节点的平衡，所以要往上依次进行递推 *** 作
        while (node != null){
            if(BFValue(node) == 2){
                // 左子树的高度 - 右子树的高度 = 2 则进行右旋 *** 作
                
                Node left =node.getLeft();
                if(left.getRight() != null){
                    // 先以左子节点进行左旋 *** 作
                    leftRoate(left);
                }
                // 左子节点没有右子节点的话以node进行右旋 *** 作
                rightRoate(node);
            }else if(BFValue(node) == -2){
                // 这里同上也有两种情况
                Node right = node.getRight();
                if(right.getLeft() != null){
                    rightRoate(right);
                }
                leftRoate(node);
            }
            node = node.getParent();
        }
    }

    // 左旋 *** 作
    public void leftRoate(Node a){
        if(a == null){
            return;
        }
        Node b = a.getRight();
        Node d = b.getLeft();
        // 注意，这一步不能忘，当右子树的没有左子树的时候，要把当前节点的右子树设置为空
        a.setRight(d);
        if(d != null){
            d.setParent(a);
        }
        b.setParent(a.getParent());
        if(b.getParent() != null){
            if(b.getParent().getLeft() == a){
                b.getParent().setLeft(b);
            }else{
                b.getParent().setRight(b);
            }
        }else{
            this.root = b;
        }
        b.setLeft(a);
        a.setParent(b);
    }

    // 右旋 *** 作
    public void rightRoate(Node a){
        if(a == null){
            return;
        }
        Node b = a.getLeft();
        Node d = b.getRight();
        a.setLeft(null);
        if(d != null){
            d.setParent(a);
        }
        b.setParent(a.getParent());
        if(b.getParent() != null){
            if(b.getParent().getLeft() == a){
                b.getParent().setLeft(b);
            }else{
                b.getParent().setRight(b);
            }
        }else{
            this.root = b;
        }
        b.setRight(a);
        a.setParent(b);
    }

    // 计算左子树和右子树的高度差，也叫做平衡因子
    public int BFValue(Node node){
        // 如果当前节点为 null，则说明其没有左右子树所以高度差为0
        if(node == null){
            return 0;
        }
        return getHeighNode(node);
    }

    // 返回高度差
    public int getHeighNode(Node node){
        if(node == null){
            return 0;
        }
        return getHeight(node.getLeft()) - getHeight(node.getRight());
    }

    // 返回对应二叉树的高度
    public int getHeight(Node node){
        if(node == null){
            return -1;
        }
        return 1 + Math.max(getHeight(node.getLeft()), getHeight(node.getRight()));
    }

    // 二叉树的查找
    public Node select(K key){
        if(this.root == null){
            return null;
        }

        Node temp = this.root;
        while (temp != null){
            int i = key.compareTo((K) temp.getKey());
            if(i == 0){
                return temp;
            }else if(i > 0){
                temp = temp.getRight();
            }else{
                temp = temp.getLeft();
            }
        }
        return null;
    }

    // 前序遍历
    public void preOrder(Node root){
        // 递归结束的条件
        if(root == null){
            return;
        }
        System.out.print(root.getKey() + "  ");
        if(root.getLeft() != null){
            preOrder(root.getLeft());
        }
        if(root.getRight() != null){
            preOrder(root.getRight());
        }
    }

    // 中序遍历
    public void infixOrder(Node root){
        if(root == null){
            return;
        }
        if(root.getLeft() != null){
            infixOrder(root.getLeft());
        }
        System.out.print(root.getKey() + "  ");
        if(root.getRight() != null){
            infixOrder(root.getRight());
        }
    }

    // 后序遍历
    public void postOrder(Node root){
        if(root == null){
            return;
        }
        if(root.getLeft() != null){
            postOrder(root.getLeft());
        }
        if(root.getRight() != null){
            postOrder(root.getRight());
        }
        System.out.print(root.getKey() + "  ");
    }

    // 层序遍历
    
    public void cengXuOrder(Node root){
        // 保证二叉树非空
        if(root == null){
            return;
        }
        Deque queue = new linkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            // d出队头元素
            Node remove = queue.remove();
            System.out.print(remove.getKey() + "  ");
            if(remove.getLeft() != null){
                queue.add(remove.getLeft());
            }
            if(remove.getRight() != null){
                queue.add(remove.getRight());
            }
        }
    }

    // 二叉树的删除
    
    
    public void delete(K key){
        // 先判断该二叉树中是否存在该节点
        Node select = select(key);
        if(select ==null){
            System.out.println("二叉树中没有该节点");
            return;
        }
        // 要删除节点，必须找到父节点，然后将其左子树或者右子树置为空
        Node parent = select.getParent();
        // 第一种情况：删除的节点是叶子节点
        if(select.getLeft() == null && select.getRight() == null){
            // 当parent 为null的时候，则代表该节点是根节点（因为父节点为空而且没有左右子树）
            if(parent == null){
                root = null;
            }else{
                // 判断要删除的节点select是parent的左子节点还是右子节点
                if(parent.getLeft() == select){
                    parent.setLeft(null);
                }else{
                    parent.setRight(null);
                }
            }
        }else if(select.getLeft() == null || select.getRight() == null){ // 说明要删除的节点只有一个子节点
            // 定义一个临时节点用来存储要删除节点的子节点
            Node temp = select.getLeft() != null ? select.getLeft() : select.getRight();
            // 如果父节点为null 说明当前节点是根节点
            if (parent == null){
                root = temp;
                temp.setParent(null);
            }else{
                if(parent.getLeft() == select){
                    parent.setLeft(temp);
                }else{
                    parent.setRight(temp);
                }
                temp.setParent(parent);
            }
        }else{ // 这种情况说明有两个子节点
            
            // 要先去寻找要删除节点的前驱节点或者后继节点（这里以后继节点为例）
            Node temp = sucNode(select);
            
            if(select.getRight() == temp){
                // 后继节点是删除节点的右子树
                if(parent == null){ // 说明要删除的节点是根节点
                    root = temp;
                    temp.setParent(null);
                }else{
                    if(parent.getLeft() == select){
                        parent.setLeft(temp);
                    }else{
                        parent.setRight(temp);
                    }
                    temp.setParent(parent);
                }
                temp.setLeft(select.getLeft());
                select.getLeft().setParent(temp);
            }else{ // 这里说明，后继节点不是要删除节点的右子树

                // 注意，此时后继节点如果有子树的话只有右子树，没有左子树，所以需要把右子树放到后继节点的父节点的左子树上
                Node replaceNodeParent = temp.getParent();

                // 这里，又分为两种情况，后继节点是否有右子树
                
                if(temp.getRight() == null){
                    // 将后继节点的左子树设置为null
                    replaceNodeParent.setLeft(null);
                }else{
                    
                    replaceNodeParent.setLeft(temp.getRight());
                    temp.getRight().setParent(replaceNodeParent);
                }
                // 设置删除节点的左右子树为后继节点的左右子树
                temp.setLeft(select.getLeft());
                temp.setRight(select.getRight());
                if(parent == null){
                    root = temp;
                    temp.setParent(null);
                }else{
                    if(parent.getLeft() == select){
                        parent.setLeft(temp);
                    }else{
                        parent.setRight(temp);
                    }
                    temp.setParent(parent);
                }
            }
        }
    }

    // 寻找当前节点的后继节点
    public Node sucNode(Node node){
        Node right = null;
        if(node != null){
            right = node.getRight();
            if(right != null){
                while (right.getLeft() != null){
                    right = right.getLeft();
                }
            }
        }
        return right;
    }
}

class Node,V>{
    private K key;
    private V value;

    private Node left; // 左节点
    private Node right; // 右节点
    private Node parent; // 父节点（用以实现二叉查找树）

    public Node(){

    }

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

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

    public K getKey() {
        return key;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }
}

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

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

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

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

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

下面再学习红黑树之前，推荐先去看两篇文章，可以更好的理解下面的内容：

什么是2-3树？

清晰理解红黑树的演变—红黑的含义

红黑树的性质

• 性质一：每个节点要么是黑色，要么是红色
• 性质二：根节点是黑色
• 性质三：每个叶子节点的（NIL（即为 null 节点））是黑色
• 性质四：每个红色节点的两个子节点一定都是黑色，不能有两个红色节点相连（不然会出现2-3-4树的情况）
• 性质五：任意一节点到每个叶子节点的路径包含数量相同的黑色节点，俗称：黑高
• 性质5.1：如果一个节点存在黑色子节点，那么该节点肯定有两个子节点

红黑树并不是一个完美平衡二叉树，可以看到，根节点 root 的左子树显然比右子树高

但左子树和右子树的黑节点的层数是相等的，也即任意一节点到每个叶子节点的路径都包括数量相同的黑节点

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

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

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

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

• 变色：节点的颜色由红变黑或者由黑变红
• 左旋：以某个节点作为支点（旋转节点），其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，（右子节点的）右子节点保持不变
• 右旋：以某个节点作为支点（旋转节点），其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，（左子节点的）左子节点保持不变。

左旋示意图：

右旋示意图：

红黑树查找：

红黑树的插入：

插入 *** 作包括两个部分工作：

1、查找插入的位置

2、插入后自平衡

注意：插入节点，必须为红色，理由很简单，红色在父节点（如果存在）为黑色节点的时候，红黑树的黑色平衡没被破坏，不需要做自平衡 *** 作。但如果插入节点是黑色，那么插入位置所在的子树黑色节点总是多1，必须做自平衡 *** 作。

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

红黑树插入节点情景分析：

情景1：红黑树为空树

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

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

情景2：插入节点的 key 已经存在

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

情景三：插入节点的父节点为黑色

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

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

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

这一点很关键，因为后续 *** 作肯定需要祖父节点的参与。

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

依据红黑树性质四可知：红色节点不能相连 --> 祖父节点一定为黑节点

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

处理：

• 将 P 和 U节点改为黑色
• 将 PP 改为红色
• 将 PP 设置为当前节点，进行后续处理

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

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

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

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

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

处理：

• 将 P 设置为黑色，将 PP 设置为红色
• 对 PP 节点进行右旋

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

处理：

• 对 P 进行左旋
• 将 P 设置为当前节点，得到 LL 双红色情况
• 按照 LL 双红情况处理（1、变颜色 2、右旋 PP）

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

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

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

处理：

• 变颜色：将 P 设置为黑色，将 PP 设置为红色
• 对 PP 节点进行左旋

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

处理：

• 对 P 进行右旋
• 将 P 设置为当前节点，得到 RR 双红色情况
• 按照 RR 双红色情况处理（1、变颜色 2、左旋 PP）

2.2、红黑树案例

3、手写红黑树

• 创建 RBTree，定义颜色
• 创建 RBNode
• 辅助定义方法：parentOf(node)，isRed(node)，setRed(node)，setBlack(node)，inorderPrint()
• 左旋方法定义：leftRoate(node)
• 右旋方法定义：rightRoate(node)
• 公开插入接口方法定义：insert(K key,V value)
• 内部插入接口方法定义：insert(RBNode node)
• 修正插入导致红黑树失衡的方法定义：insertFixUp(RBNode node)
• 测试红黑树正确性

public class RBTree, V> {

    

    // 定义红黑树节点的颜色
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    // 树根节点的引用
    private RBNode root;

    public RBNode getRoot() {
        return root;
    }

    
    private RBNode parentOf(RBNode node){
        if(node != null){
            return node.parent;
        }
        return null;
    }

    
    private boolean isRed(RBNode node){
        if(node != null){
            return node.color == RED;
        }
        return false;
    }

    
    private boolean isBlack(RBNode node){
        if(node != null){
            return node.color == BLACK;
        }
        return false;
    }

    
    private void setRed(RBNode node){
        if(node != null){
            node.color = RED;
        }
    }

    
    private void setBlack(RBNode node){
        if(node != null){
            node.color = BLACK;
        }
    }

    
    public void inorderPrint(){
        inorderPrint(this.root);
    }

    
    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){
        // 第一步：查找当前node的父节点
        RBNode parent = null;
        RBNode x = this.root;
        int compare = -1; // 用于比较当前节点和node的值，确定循环的子树位置

        // 循环进行查找，当循环结束，x为空，然后parent为为要插入节点的父节点
        while (x != null){
            parent = x; // 将x赋值给parent
            // compare > 0，说明node.key 大于 x.key，需要到x的右子树进行查找
            // compare == 0，说明node.key 等于 x.key，说明需要进行替换 *** 作
            // compare < 0，说明node.key 小于 x.key，需要到x的左子树进行查找
            compare = node.key.compareTo(x.key);
            if(compare > 0){
                x = x.right;
            }else if(compare == 0){
                x.setValue(node.getValue());
                return;
            }else{
                x = x.left;
            }
        }
        // 设置node的父节点
        node.parent = parent;
        if(parent != null){
            // 这里注意，需要根据compare的值来判断node是parent的子树类型
            if(compare > 0){ // 说明node应该位于parent的右子树
                parent.right = node;
            }
            if(compare < 0){ // 说明node应该位于parent的左子树
                parent.left = node;
            }
        }else{ // 说明当前红黑树没有节点，即把node设置为根节点
            this.root = node;
            node.setParent(null);
        }

        // 插入之后，可能会破坏红黑树的平衡性，需要对当前红黑树进行调整平衡操作
        // 注意，这里以插入节点为当前节点开始调整平衡
        insertFixUp(node);
    }

    
    private void insertFixUp(RBNode node){
        this.root.setColor(BLACK);
        RBNode parent = parentOf(node); // 父节点
        RBNode gparent = parentOf(parent); // 祖父节点

        // 情景4：插入节点的父节点为红色
        if(parent != null && isRed(parent)){
            // 注意，如果父节点存在，那么一定存在祖父节点，因为根节点不可能为红色
            RBNode uncle = null; // 叔叔节点
            if(parent == gparent.left){ // 父节点为祖父节点的左子树
                // 所以这里不需要判断祖父节点是否为空，因为一定不为空
                uncle = gparent.right;
                // 情景4.1：叔叔节点存在，并且为红色（父-叔 双红）
                if(uncle != null && isRed(uncle)){
                    // 将父节点和叔叔染色为黑色，将祖父染色为红色，并且再以祖父节点为当前节点，进行下一轮处理
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gparent);
                    node = gparent;
                    insertFixUp(node);
                    return;
                }

                // 情景4.2：叔叔节点不存在，或者为黑色
                if(uncle == null || isBlack(uncle)){
                    // 情景4.2.1：插入节点为其父节点的左子节点（LL 双红情况）
                    // 将父节点染色为黑色，祖父节点染色为红色，然后以爷爷节点右旋，就完成了
                    if(node == parent.left){
                        setBlack(parent);
                        setRed(gparent);
                        rightRotate(gparent);
                        return;
                    }else{ // 情景4.2.2：插入节点为其父节点的右子节点（LR 双红情况）
                        // 以父节点进行一次左旋，得到LL双红情景（4.2.1情景），然后指定父节点为当前节点进行下一轮操作
                        leftRoate(parent);
                        insertFixUp(parent);
                        return;
                    }
                }
            }else{ // 父节点为祖父节点的右子节点
                // 所以这里不需要判断祖父节点是否为空，因为一定不为空
                uncle = gparent.left;
                // 情景4.1：叔叔节点存在，并且为红色（父-叔 双红）
                if(uncle != null && isRed(uncle)){
                    // 将父节点和叔叔染色为黑色，将祖父染色为红色，并且再以祖父节点为当前节点，进行下一轮处理
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gparent);
                    insertFixUp(gparent);
                    return;
                }

                // 情景4.3：叔叔节点不存在，或者为黑色，父节点为祖父节点的右子树
                if(uncle == null || isBlack(uncle)){
                    // 情景4.3.1：插入节点为其父节点的右子节点（RR 双红情况）
                    if(node == parent.right){
                        // 将父节点染色为黑色，祖父节点染色为红色，然后以祖父节点进行左旋，就完成了
                        setBlack(parent);
                        setRed(gparent);
                        leftRoate(gparent);
                        return;
                    }else{ // 情景4.3.2：插入节点为其父节点的左子节点（RL 双红情况）
                        // 以父节点进行一次右旋，得到RR 双红情景（4.3.1情景），然后指定父节点为当前节点进行下一轮操作
                        rightRotate(parent);
                        insertFixUp(parent);
                        return;
                    }
                }
            }
        }
    }

    
    private void leftRoate(RBNode x){
        RBNode y = x.right; // 获取旋转节点的右子节点
        // 1.将y的左子节点的父节点更新为x（ly）
        if(y.left != null){
            y.left.parent = x;
        }
        // 并将x的右子节点指向y的左子节点（ly）不管y的左子节点是否为空
        x.right = y.left;

        // 2.当x的父节点不为空的时候（即x不为根节点），更新y的父节点为x的父节点，并将x的父节点指定子树（当前x的子树位置）指定为y
        if(x.parent != null){
            // 注意这里，无论x的父节点是否为空，都要更新y的父节点为x的父节点
            y.parent = x.parent;
            if(x == x.parent.left){
                x.parent.left = y;
            }else{
                x.parent.right = y;
            }
        }else{ // 说明x节点是根节点，此时需要更新y为根节点
            this.root = y;
            // 注意，这一步一定不能忘
            y.parent = null;
        }

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

    
    private void rightRotate(RBNode y){
        RBNode x = y.left;
        // 1.将y的的左子节点指向x的右子节点
        if(x.right != null){
            x.right.parent = y;
        }
        // 并且更新x的右子节点的父节点为y(ly)，无论x的右子节点是否为空
        y.left = x.right;

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

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

    private void inorderPrint(RBNode root){
        if(root.left != null){
            inorderPrint(root.left);
        }
        System.out.print(root.key + "  ");
        if(root.right != null){
            inorderPrint(root.right);
        }
    }

    static class RBNode, V>{
        private RBNode parent; // 父节点
        private RBNode left; // 左节点
        private RBNode right; // 右节点
        private boolean color; // 节点颜色
        private K key;
        private V value;

        public RBNode(){}

        public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.color = color;
            this.key = key;
            this.value = value;
        }

        public RBNode getParent() {
            return parent;
        }

        public void setParent(RBNode parent) {
            this.parent = parent;
        }

        public RBNode getLeft() {
            return left;
        }

        public void setLeft(RBNode left) {
            this.left = left;
        }

        public RBNode getRight() {
            return right;
        }

        public void setRight(RBNode right) {
            this.right = right;
        }

        public boolean isColor() {
            return color;
        }

        public void setColor(boolean color) {
            this.color = color;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }
}

代码测试：

在网上找的一个打印红黑树的工具类：

public class RedAndBlackTreeOperation {
    

    // 用于获得树的层数
    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());
        }
    }
}

测试：

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    RBTree rbTree = new RBTree<>();
    while (true){
        System.out.println("请输入要插入的节点的key：");
        Integer key = Integer.parseInt(scanner.next());
        System.out.println();
        rbTree.insert(key,key);
        RedAndBlackTreeOperation.show(rbTree.root);
    }
}

测试结果如下：

请输入要插入的节点的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：
10

                        4-B                      
                    /                           
                2-B             6-B              
             /              /                  
          1-B         3-B 5-B         8-R        
                                    /           
                                  7-B     9-B    
                                                
                                            10-R 
请输入要插入的节点的key：
-1

                        4-B                      
                    /                           
                2-B             6-B              
             /              /                  
          1-B         3-B 5-B         8-R        
        /                           /           
      -1-R                        7-B     9-B    
                                                
                                            10-R 
请输入要插入的节点的key：
-2

                        4-B                      
                    /                           
                2-B             6-B              
             /              /                  
          -1-B        3-B 5-B         8-R        
        /                          /           
      -2-R    1-R                 7-B     9-B    
                                                
                                            10-R 
请输入要插入的节点的key：
-3

                        4-B                      
                    /                           
                2-B             6-B              
             /              /                  
          -1-R        3-B 5-B         8-R        
        /                          /           
      -2-B    1-B                 7-B     9-B    
     /                                          
    -3-R                                    10-R 
请输入要插入的节点的key：
11

                        4-B                      
                    /                           
                2-B             6-B              
             /              /                  
          -1-R        3-B 5-B         8-R        
        /                          /           
      -2-B    1-B                 7-B     10-B   
     /                                   /      
    -3-R                                9-R 11-R 
请输入要插入的节点的key：
12

                        4-B                      
                    /                           
                2-B             8-B              
             /              /                  
          -1-R        3-B 6-R         10-R       
        /              /          /           
      -2-B    1-B     5-B     7-B 9-B     11-B   
     /                                          
    -3-R                                    12-R

至此，手写红黑树已经完成了，虽然刚学挺麻烦感觉，其实仔细回想觉得思路也是很清晰的，只要好好理解，代码还是可以的！