├─ 红黑树的性质
 ├─ 红黑树有几种变化策略？(为满足红黑树性质)
 │    ├─ 改变颜色
 │    ├─ 左旋
 │    ├─ 右旋
 ├─ 红黑树的查找
 ├─ 红黑树的插入
 │    ├─ 情景1：红黑树为空树
 │    ├─ 情景2：插入节点的Key已经存在
 │    ├─ 情景3：插入节点的父节点为黑色
 │    ├─ 情景4：插入节点的父节点为红色
 │    │    ├─ 情景4.1：叔叔节点存在，并且为红色(父 - 叔 双红)
 │    │    ├─ 情景4.2：叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
 │    │    │    ├─ 情景4.2.1：插入节点为其父节点的左子节点(LL情况)
 │    │    │    ├─ 情景4.2.2：插入节点为其父节点的右子节点(LR情况)
 │    │    ├─ 情景4.3：叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
 │    │    │    ├─ 情景4.3.1：插入节点为其父节点的右子节点(RR情况)
 │    │    │    ├─ 情景4.3.2：插入节点为其父节点的左子节点(RL情况)
 ├─ 红黑树的插入案例分析

// RBTree.java
package cn.icanci.tree;

/**
 * @Author: icanci
 * @ProjectName: list-set-map
 * @PackageName: cn.icanci.tree
 * @Date: Created in 2020/7/28 14:48
 * @ClassAction: RBTree
 * 
 * 3.1 创建RBTree，定义颜色
 * 3.2 创建RBNode
 * 3.3 辅助方法定义：parentOf(node)、isRed(node)、isBlack(node)、setRed(node)、setBlack(node)、inOrderPrint()
 * 3.4 左旋方法定义：leftRotate(node)
 * 3.5 右旋方法定义：rightRotate(node)
 * 3.6 公开插入接口方法定义：insert(K key,V value)
 * 3.7 内部插入接口方法定义：insert(RBNode node)
 * 3.8 修正插入导致红黑树失衡的方法定义：insertFlxUp(RBNode node)
 * 3.9 测试红黑树的正确性
 */

/**
 * 创建 创建RBTree，定义颜色
 *
 * @param <K> Key
 * @param <V> Value
 */
public class RBTree<K extends Comparable<K>, V> {
    /**
     * RED 红色节点
     */
    private static final boolean RED = true;
    /**
     * BLACK 黑色节点
     */
    private static final boolean BLACK = false;

    /**
     * 树根的引用
     */
    private RBNode root;

    public RBNode getRoot() {
        return root;
    }

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

    /**
     * 获取当前节点的父节点
     *
     * @param node 当前节点
     * @return 返回当前节点的父节点，没有就返回null
     */
    private RBNode parentOf(RBNode node) {
        if (node != null) {
            return node.parent;
        }
        return null;
    }

    /**
     * 节点是否为红色
     *
     * @param node 当前节点
     * @return 返回当前节点的颜色，节点为null就返回false
     */
    private boolean isRed(RBNode node) {
        if (node != null) {
            return node.color == RED;
        }
        return false;
    }

    /**
     * 节点是否为黑色
     *
     * @param node 当前节点
     * @return 返回当前节点的颜色，节点为null就返回false
     */
    private boolean isBlack(RBNode node) {
        if (node != null) {
            return node.color == BLACK;
        }
        return false;
    }

    /**
     * 设置节点为红色
     *
     * @param node 当前的节点
     */
    private void setRed(RBNode node) {
        if (node != null) {
            node.color = RED;
        }
    }


    /**
     * 设置节点为黑色
     *
     * @param node 当前的节点
     */
    private void setBlack(RBNode node) {
        if (node != null) {
            node.color = BLACK;
        }
    }

    /**
     * 红黑树的中序打印
     */
    public void inOrderPrint() {
        inOrderPrint(this.root);
    }

    /**
     * 红黑树的中序打印
     *
     * @param node 根节点
     */
    private void inOrderPrint(RBNode node) {
        if (node != null) {
            inOrderPrint(node.left);
            System.out.println("Key:" + node.key + " Value:" + node.value);
            inOrderPrint(node.right);
        }
    }

    /**
     * 左旋方法
     * 左旋示意图：左旋x节点
     *    p                   p
     *    |                   |
     *    x                   y
     *   / \         ---->   / \
     *  lx  y               x   ry
     *     / \             / \
     *    ly  ry          lx  ly
     */

    /**
     * 左旋做了几件事？
     * 1.并将x的右子节点指向y的左子节点(ly) 将y的左子节点的父节点更新为x
     * 2.当x的父节点不为空的时候，更新y的父节点为x的父节点，并将x的父节点指定子树(当前x的子树位置)指定为y
     * 3.将x的父节点更新为y，将y的左子节点指向x
     */

    private void leftRotate(RBNode x) {
        // 先拿到当前节点的右子节点
        RBNode y = x.right;
        // 将x的右子节点指向y的左子节点(ly)
        x.right = y.left;
        if (y.left != null) {
            // 将y的左子节点的父节点更新为x
            y.left.parent = x;
        }
        // 当x的父节点不为空的时候，更新y的父节点为x的父节点
        // 并将x的父节点指定子树(当前x的子树位置)指定为y
        if (x.parent != null) {
            y.parent = x.parent;
            if (x == x.parent.left) {
                x.parent.left = y;
            } else {
                x.parent.right = y;
            }
        } else {
            // 说明x为根节点
            this.root = y;
            this.root.parent = null;
        }
        // 将x的父节点更新为y，将y的左子节点指向x
        x.parent = y;
        y.left = x;
    }


    /**
     * 右旋方法
     * 右旋示意图：右旋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;
        // 将y的左子节点指向x的有子节点，并且更新x的有子节点的父节点为y
        y.left = x.right;
        if (x.right != null) {
            x.right.parent = y;
        }
        if (y.parent != null) {
            x.parent = y.parent;
            if (y == y.parent.left) {
                y.parent.left = x;
            } else {
                y.parent.right = x;
            }
        } else {
            this.root = x;
            this.root.parent = null;
        }
        // 更新y的父节点为x。更新x的右子节点为y
        y.parent = x;
        x.right = y;
    }

    /**
     * 公开的插入方法
     *
     * @param key
     * @param value
     */
    public void insert(K key, V value) {
        RBNode node = new RBNode();
        node.setKey(key);
        node.setValue(value);
        // 新节点一定是红色
        node.setColor(RED);
        this.insert(node);
    }

    /**
     * 私有的插入方法
     *
     * @param node 需要插入的节点
     */
    private void insert(RBNode node) {
        //第一步：查找当前的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 = x.left;
            } else {
                x.value = node.value;
                return;
            }
        }
        node.parent = parent;
        if (parent != null) {
            // 判断node与parent的key谁大
            int cmp = node.key.compareTo(parent.key);
            // 当前node的key比parent的key大，那么就要把node放入parent的右子节点
            if (cmp > 0) {
                parent.right = node;
            } else {
                // 当前node的key比parent的key小，那么就要把node放入parent的左子节点
                parent.left = node;
            }
        } else {
            this.root = node;
        }
        // 需要调用修复红黑树平衡的方法
        this.insertFlxUp(node);
    }

    /**
     * 插入后修复红黑树平衡的方法
     *     |---情景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）的场景
     *                              然后指定父亲节点进行下一论处理
     */


    /**
     * 修复红黑树的方法
     *
     * @param node
     */
    private void insertFlxUp(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);
                    // 并且再以爷爷节点为当前节点，进行下一轮处理
                    insertFlxUp(gParent);
                    return;
                }
                // 情景4.2：叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
                if (uncle == null || isBlack(uncle)) {
                    // 情景4.2.1：插入节点为其父节点的左子节点（LL情况）
                    // 将父亲染色为黑色，将爷爷染色为红色，
                    // 然后以爷爷点右旋，就完成了
                    if (node == parent.left) {
                        setBlack(parent);
                        setBlack(gParent);
                        rightRotate(gParent);
                        return;
                    }
                    // 情景4.2.2：插入节点为其父节点的右子节点（LR情况）
                    // 以父亲节点进行一次左旋，得到LL（4.2.1） 的场景
                    // 然后指定父亲节点为当前节点，进行下一个处理
                    if (node == parent.right) {
                        leftRotate(parent);
                        insertFlxUp(parent);
                        return;
                    }
                }
            } else {
                // 父节点为爷爷节点的右子树
                uncle = gParent.left;
                // 情景4.1：叔叔节点存在，并且为红色（父-叔 双红）
                if (uncle != null && isRed(uncle)) {
                    // 将父亲节点和叔叔节点染色为黑色
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gParent);
                    // 并且再以爷爷节点为当前节点，进行下一轮处理
                    insertFlxUp(gParent);
                    return;
                }
                // 情景4.3：叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
                if (uncle == null || 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);
                        insertFlxUp(parent);
                        return;
                    }
                }
            }
        }
    }

    /**
     * 创建 内部类 RBNode
     *
     * @param <K> Key
     * @param <V> Value
     */
    static class RBNode<K extends Comparable<K>, V> {
        // parent 父节点
        private RBNode parent;
        // left 左节点
        private RBNode left;
        // right 右节点
        private RBNode right;
        // 节点的颜色
        private boolean color;
        // key
        private K key;
        // value
        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;
        }
    }
}

// TreeOperation.java 用来打印方法
package cn.icanci.tree;

/**
 * @Author: icanci
 * @ProjectName: list-set-map
 * @PackageName: cn.icanci.tree
 * @Date: Created in 2020/7/28 17:13
 * @ClassAction: 打印红黑树
 */
public class TreeOperation {
  /*
    树的结构示例：
              1
            /   \
          2       3
         / \     / \
        4   5   6   7
    */

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

// RBTree.java 测试类
package cn.icanci.tree;

import java.util.Scanner;

/**
 * @Author: icanci
 * @ProjectName: list-set-map
 * @PackageName: cn.icanci.tree
 * @Date: Created in 2020/7/28 16:32
 * @ClassAction: 手写 RBTree 测试类
 */
public class RBTreeTest {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        RBTree<String, Object> rbt = new RBTree();
        while (true) {
            System.out.print("请输入Key>");
            String key = sc.next();
            System.out.println();
            rbt.insert(key, null);
            TreeOperation.show(rbt.getRoot());
        }
    }
}