@Test
public void test03() {
    int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10};
    System.out.println(binarySearch(arr,3));
}
/*
 * 二分查找
 * @param: arr
 * @param: data
 * @return: int
 * @create: 2020/11/6 13:29
 * @author: csp1999
 */
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;
}

package com.haust.map;
/**
 * @Auther: csp1999
 * @Date: 2020/11/06/18:00
 * @Description: ①創(chuàng)建RBTree，定義顏色
 * <p>
 * ②創(chuàng)建RBNode
 * <p>
 * ③輔助方法定義：parentOf(node)，isRed(node)，setRed(node)，setBlack(node)，inOrderPrint()
 * <p>
 * ④左旋方法定義：leftRotate(node)
 * <p>
 * ⑤右旋方法定義：rightRotate(node)
 * <p>
 * ⑥公開(kāi)插入接口方法定義：insert(K key, V value);
 * <p>
 * ⑦內(nèi)部插入接口方法定義：insert(RBNode node);
 * <p>
 * ⑧修正插入導(dǎo)致紅黑樹(shù)失衡的方法定義：insertFIxUp(RBNode node);
 * <p>
 * ⑨測(cè)試紅黑樹(shù)正確性
 */
public class RBTree<K extends Comparable<K>, V> {
    private static final boolean RED = true;// 紅
    private static final boolean BLACK = false;// 黑
    /**
     * 樹(shù)根的引用
     **/
    private RBNode root;
    public RBNode getRoot() {
        return root;
    }
    /**
     * 獲取當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
     *
     * @param node
     * @return
     */
    private RBNode parentOf(RBNode node) {
        if (node != null) {
            return node.parent;
        }
        return null;
    }
    /**
     * 節(jié)點(diǎn)是否為紅色
     *
     * @param node
     * @return
     */
    private boolean isRed(RBNode node) {
        if (node != null) {
            return node.color == RED;
        }
        return false;
    }
    /**
     * 節(jié)點(diǎn)是否為黑色
     *
     * @param node
     * @return
     */
    private boolean isBlack(RBNode node) {
        if (node != null) {
            return node.color == BLACK;
        }
        return false;
    }
    /**
     * 設(shè)置節(jié)點(diǎn)為紅色
     *
     * @param node
     */
    private void setRed(RBNode node) {
        if (node != null) {
            node.color = RED;
        }
    }
    /**
     * 設(shè)置節(jié)點(diǎn)為黑色
     *
     * @param node
     */
    private void setBlack(RBNode node) {
        if (node != null) {
            node.color = BLACK;
        }
    }
    /**
     * 中序打印二叉樹(shù)
     */
    public void inOrderPrint() {
        inOrderPrint(this.root);
    }
    private void inOrderPrint(RBNode node) {
        if (node != null) {
            inOrderPrint(node.left);
            System.out.println("key:" + node.key + ",value:" + node.value);
            inOrderPrint(node.right);
        }
    }
    /**
     * 左旋方法
     * 左旋示意圖：左旋x節(jié)點(diǎn)
     *   p                   p
     *   |                   |
     *   x                   y
     *  / \      ---->      / \
     * lx  y               x   ry
     *    / \             / \
     *   ly  ry          lx  ly
     *
     * 左旋做了幾件事？
     * 1.將x的右子節(jié)點(diǎn)指向y的左子節(jié)點(diǎn)(ly)，并且把y的左子節(jié)點(diǎn)更新為x
     * 2.當(dāng)x的父節(jié)點(diǎn)(不為空時(shí))，更新y的父節(jié)點(diǎn)為x的父節(jié)點(diǎn)，并將x的父節(jié)點(diǎn) 指定 子樹(shù)(當(dāng)前x的子樹(shù)位置) 指定為y
     * 3.將x的父節(jié)點(diǎn)更新為y，將y的左子節(jié)點(diǎn)更新為x
     */
    private void leftRotate(RBNode x) {
        RBNode y = x.right;// 獲得y
        // 1.將x的右子節(jié)點(diǎn)指向y的左子節(jié)點(diǎn)(ly)，并且把y的左子節(jié)點(diǎn)更新為x
        x.right = y.left;
        if (y.left != null) {
            y.left.parent = x;
        }
        // 2.當(dāng)x的父節(jié)點(diǎn)(不為空時(shí))，更新y的父節(jié)點(diǎn)為x的父節(jié)點(diǎn)，并將x的父節(jié)點(diǎn) 指定 子樹(shù)(當(dāng)前x的子樹(shù)位置) 指定為y
        if (x.parent != null) {
            y.parent = x.parent;
            if (x == x.parent.left) {// 如果x是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)，則將y放在x父節(jié)點(diǎn)的左邊
                x.parent.left = y;
            } else {
                x.parent.right = y;// 如果x是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)，則將y放在x父節(jié)點(diǎn)的右邊
            }
        } else {// 說(shuō)明x為根節(jié)點(diǎn)，此時(shí)需要更新y為根節(jié)點(diǎn) 的引用
            this.root = y;
            this.root.parent = null;// 根節(jié)點(diǎn)無(wú)父節(jié)點(diǎn)
        }
        // 3.將x的父節(jié)點(diǎn)更新為y，將y的左子節(jié)點(diǎn)更新為x
        x.parent = y;
        y.left = x;
    }
    /**
     * 右旋方法
     * 右旋示意圖：右旋y節(jié)點(diǎn)
     *
     *     p                       p
     *     |                       |
     *     y                       x
     *    / \          ---->      / \
     *   x   ry                  lx  y
     *  / \                         / \
     * lx  ly                      ly  ry
     *
     * 右旋都做了幾件事？
     * 1.將y的左子節(jié)點(diǎn)指向x的右子節(jié)點(diǎn)，并且更新x的右子節(jié)點(diǎn)的父節(jié)點(diǎn)為y
     * 2.當(dāng)y的父節(jié)點(diǎn)不為空時(shí)，更新x的父節(jié)點(diǎn)為y的父節(jié)點(diǎn)，更新y的父節(jié)點(diǎn)的指定子節(jié)點(diǎn)（y當(dāng)前位置） 為x
     * 3.更新y 的父節(jié)點(diǎn)為x ,更新x 的右子節(jié)點(diǎn)為y
     */
    private void rightRotate(RBNode y) {
        RBNode x = y.left;// 獲得 x
        // 1.將x的右子節(jié)點(diǎn) 賦值 給了 y 的左子節(jié)點(diǎn)，并且更新x的右子節(jié)點(diǎn)的父節(jié)點(diǎn)為 y
        y.left = x.right;
        if(x.right != null) {
            x.right.parent = y;
        }
        // 2.將y的父節(jié)點(diǎn)p（非空時(shí)）賦值給x的父節(jié)點(diǎn)，同時(shí)更新p的子節(jié)點(diǎn)為x（左或右）
        if(y.parent != null) {
            x.parent = y.parent;
            if(y.parent.left == y) {// 如果y是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)，則將x放在y父節(jié)點(diǎn)的左邊
                y.parent.left = x;
            } else {// 如果y是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)，則將x放在y父節(jié)點(diǎn)的右邊
                y.parent.right = x;
            }
        } else {// 說(shuō)明y為根節(jié)點(diǎn)，此時(shí)需要更新x為根節(jié)點(diǎn) 的引用
            this.root = x;
            this.root.parent = null;// 根節(jié)點(diǎn)無(wú)父節(jié)點(diǎn)
        }
        // 3.將x的右子節(jié)點(diǎn)賦值為y，將y的父節(jié)點(diǎn)設(shè)置為x
        x.right = y;
        y.parent = x;
    }
    /**
     * public插入方法
     *
     * @param key
     * @param value
     */
    public void insert(K key, V value) {
        RBNode node = new RBNode<>();
        node.setKey(key);
        node.setValue(value);
        // 新節(jié)點(diǎn) 一定要是紅色！
        node.setColor(RED);
        insert(node);
    }
    private void insert(RBNode node) {
        // 第一步：查找當(dāng)前要插入節(jié)點(diǎn)node的父節(jié)點(diǎn)
        RBNode parent = null;// 聲明要插入節(jié)點(diǎn)node的父節(jié)點(diǎn)
        RBNode x = this.root;
        while (x != null) {
            parent = x;
            /**
             * cmp > 0 說(shuō)明node.key 大于 x.key 需要到x 的右子樹(shù)查找
             * cmp == 0 說(shuō)明node.key 等于 x.key 需要進(jìn)行替換操作
             * cmp < 0 說(shuō)明node.key 小于 x.key 需要到x 的左子樹(shù)查找
             */
            int cmp = node.key.compareTo(x.key);
            if (cmp > 0) {
                x = x.right;
            } else if (cmp == 0) {
                x.setValue(node.getValue());
                return;// 修改完后 就不再繼續(xù)往下面的代碼執(zhí)行了
            } else {
                x = x.left;
            }
        }
        /**
         * 退出上面的while循環(huán)后，到這里，說(shuō)明樹(shù)中沒(méi)有相同key 的元素
         *
         * 需要添加新元素node到 x(parent) 目前位置的左子樹(shù)/右子樹(shù)
         */
        node.parent = parent;
        if (parent != null) {
            // 判斷node與parent 的key 誰(shuí)大
            int cmp = node.key.compareTo(parent.key);
            if (cmp > 0) {// 當(dāng)前node的key比parent 的key大，需要把node放入parent 的右子節(jié)點(diǎn)
                parent.right = node;
            } else {// 當(dāng)前node的key比parent 的key小，需要把node放入parent 的左子節(jié)點(diǎn)
                parent.left = node;
            }
        } else {// parent == null; 說(shuō)明為空樹(shù)
            this.root = node;// 直接給樹(shù)根賦值為node
        }
        // 新元素node 加入樹(shù)中之后，要調(diào)用修復(fù)紅黑樹(shù)平衡的方法
        insertFixUp(node);
    }
    /**
     * 插入后修復(fù)紅黑樹(shù)平衡的方法
     * |---情景1：如果紅黑樹(shù)為空樹(shù),需要將根節(jié)點(diǎn)染為黑色
     * |---情景2：如果插入節(jié)點(diǎn)的key已經(jīng)存在,(這種情況不需要處理,因?yàn)樾薷臉?shù)中的值不會(huì)觸發(fā)紅黑樹(shù)修復(fù)平衡方法)
     * |---情景3：如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)為黑色,這種情況不需要處理,(參考紅黑樹(shù)的性質(zhì)4和性指5去理解)
     * (因?yàn)樗迦氲穆窂街?黑色節(jié)點(diǎn)數(shù)沒(méi)發(fā)生變化,所以紅黑樹(shù)依然平衡)
     * <p>
     * 情景4 需要去處理的情景
     * |---情景4：插入節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色,(違反紅黑樹(shù)性質(zhì)4,不能有兩個(gè)紅色節(jié)點(diǎn)相連)
     * |---情景4.1：叔叔節(jié)點(diǎn)存在，并且為紅色（父-叔 雙紅）
     * 處理：將爸爸和叔叔染成黑色，將爺爺染成紅色，并且再以爺爺節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)，進(jìn)行下一輪處理
     * |---情景4.2：叔叔節(jié)點(diǎn)不存在，或者為黑色，父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的左子樹(shù)
     * 處理：
     * |---情景4.2.1：插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)（LL情況）
     * 處理：將父節(jié)點(diǎn)染為黑色，將爺爺染為紅色，然后以爺爺節(jié)點(diǎn)右旋即可
     * |---情景4.2.2：插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)（LR情況）
     * 處理：將父節(jié)點(diǎn)進(jìn)行一次左旋，得到LL雙紅情景(4.2.1),然后指定父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)進(jìn)行下一輪處理
     * |---情景4.3：叔叔節(jié)點(diǎn)不存在，或者為黑色，父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的右子樹(shù)
     * |---情景4.3.1：插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)（RR情況）
     * 處理：將父節(jié)點(diǎn)染為黑色，將爺爺節(jié)點(diǎn)染為紅色，然后以爺爺節(jié)點(diǎn)左旋即可
     * |---情景4.3.2：插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)（RL情況）
     * 處理：以父節(jié)點(diǎn)進(jìn)行一次右旋，得到RR雙紅情景(4.3.1),然后指定父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)進(jìn)行下一輪處理
     */
    private void insertFixUp(RBNode node) {
        RBNode parent = parentOf(node);// 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
        RBNode gparent = parentOf(parent);// 當(dāng)前節(jié)點(diǎn)的爺爺節(jié)點(diǎn)
        // 存在父節(jié)點(diǎn)且父節(jié)點(diǎn)為紅色
        if (parent != null && isRed(parent)) {
            // 父節(jié)點(diǎn)是紅色的，那么一定存在爺爺節(jié)點(diǎn)(性質(zhì)2：根節(jié)點(diǎn)只能是黑色)
            // 父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的左子樹(shù)
            if (parent == gparent.left) {
                RBNode uncle = gparent.right;
                // 情景4.1：叔叔節(jié)點(diǎn)存在，并且為紅色（父-叔 雙紅）
                // 將父和叔染色為黑色，再將爺爺染紅，并將爺爺設(shè)置為當(dāng)前節(jié)點(diǎn)，進(jìn)入下一次循環(huán)判斷
                if (uncle != null && isRed(uncle)) {
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gparent);
                    insertFixUp(gparent);
                    return;
                }
                // 情景4.2：叔叔節(jié)點(diǎn)不存在，或者為黑色，父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的左子樹(shù)
                if (uncle == null || isBlack(uncle)) {
                    /**
                     * 情景4.2.1：插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)（LL情況）
                     * 處理：將父節(jié)點(diǎn)染為黑色，將爺爺染為紅色，然后以爺爺節(jié)點(diǎn)右旋即可
                     */
                    // 插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)（LL情況）=>
                    // 變色（父節(jié)點(diǎn)變黑，爺爺節(jié)點(diǎn)變紅），右旋爺爺節(jié)點(diǎn)
                    if (node == parent.left) {
                        setBlack(parent);
                        setRed(gparent);
                        rightRotate(gparent);// 以gparent 右旋
                    }
                    /**
                     * 情景4.2.2：插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)（LR情況）
                     * 處理：將父節(jié)點(diǎn)進(jìn)行一次左旋，得到LL雙紅情景(4.2.1),然后指定父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)進(jìn)行下一輪處理
                     */
                    // 插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)（LR情況）=>
                    // 左旋（父節(jié)點(diǎn)），當(dāng)前節(jié)點(diǎn)設(shè)置為父節(jié)點(diǎn)，進(jìn)入下一次循環(huán)
                    if (node == parent.right) {
                        leftRotate(parent);// parent 左旋
                        insertFixUp(parent);// 進(jìn)行下一輪處理
                        return;
                    }
                }
            } else {// 父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的右子樹(shù)
                RBNode uncle = gparent.left;
                // 情景4.1：叔叔節(jié)點(diǎn)存在，并且為紅色（父-叔 雙紅）
                // 將父和叔染色為黑色，再將爺爺染紅，并將爺爺設(shè)置為當(dāng)前節(jié)點(diǎn)，進(jìn)入下一次循環(huán)判斷
                if (uncle != null && isRed(uncle)) {
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gparent);
                    insertFixUp(gparent);// 進(jìn)行下一輪處理
                    return;
                }
                // 情景4.3：叔叔節(jié)點(diǎn)不存在，或者為黑色，父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的右子樹(shù)
                if (uncle == null || isBlack(uncle)) {
                    /**
                     * 情景4.3.1：插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)（RR情況）
                     * 處理：將父節(jié)點(diǎn)染為黑色，將爺爺節(jié)點(diǎn)染為紅色，然后以爺爺節(jié)點(diǎn)左旋即可
                     */
                    // 插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)（RR情況）=>
                    // 變色（父節(jié)點(diǎn)變黑，爺爺節(jié)點(diǎn)變紅），右旋爺爺節(jié)點(diǎn)
                    if (node == parent.right) {
                        setBlack(parent);
                        setRed(gparent);
                        leftRotate(gparent);
                    }
                    /**
                     * 情景4.3.2：插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)（RL情況）
                     * 處理：以父節(jié)點(diǎn)進(jìn)行一次右旋，得到RR雙紅情景(4.3.1),然后指定父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)進(jìn)行下一輪處理
                     */
                    // 插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)（RL情況）
                    // 右旋（父節(jié)點(diǎn)）得到RR情況，當(dāng)前節(jié)點(diǎn)設(shè)置為父節(jié)點(diǎn)，進(jìn)入下一次循環(huán)
                    if (node == parent.left) {
                        rightRotate(parent);
                        insertFixUp(parent);
                        return;
                    }
                }
            }
        }
        setBlack(this.root);
    }
    // 靜態(tài)內(nèi)部類
    static class RBNode<K extends Comparable<K>, V> {
        private RBNode parent;// 父節(jié)點(diǎn)
        private RBNode left;// 左子樹(shù)
        private RBNode right;// 右子樹(shù)
        private boolean color;// 顏色
        private K key;// 鍵
        private V value;// 值
        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() {
        }
        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;
        }
    }
}

package com.haust.map;
/**
 * @Auther: csp1999
 * @Date: 2020/11/09/15:10
 * @Description: 打印紅黑樹(shù)的工具類
 */
public class TreeOperation {
    /*
           樹(shù)的結(jié)構(gòu)示例：
              1
            /   \
          2       3
         / \     / \
        4   5   6   7
    */
    // 用于獲得樹(shù)的層數(shù)
    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) {
        // 保證輸入的樹(shù)不為空
        if (currNode == null) return;
        // 先將當(dāng)前節(jié)點(diǎn)保存到二維數(shù)組中
        res[rowIndex][columnIndex] = String.valueOf(currNode.getKey() /*+ "-" + (currNode.isColor() ? "R" : "B") + ""*/);
        // 計(jì)算當(dāng)前位于樹(shù)的第幾層
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一層，則返回
        if (currLevel == treeDepth) return;
        // 計(jì)算當(dāng)前行到下一行，每個(gè)元素之間的間隔（下一行的列索引與當(dāng)前元素的列索引之間的間隔）
        int gap = treeDepth - currLevel - 1;
        // 對(duì)左兒子進(jìn)行判斷，若有左兒子，則記錄相應(yīng)的"/"與左兒子的值
        if (currNode.getLeft() != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }
        // 對(duì)右兒子進(jìn)行判斷，若有右兒子，則記錄相應(yīng)的"\"與右兒子的值
        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!");
        // 得到樹(shù)的深度
        int treeDepth = getTreeDepth(root);
        // 最后一行的寬度為2的（n - 1）次方乘3，再加1
        // 作為整個(gè)二維數(shù)組的寬度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一個(gè)字符串?dāng)?shù)組來(lái)存儲(chǔ)每個(gè)位置應(yīng)顯示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 對(duì)數(shù)組進(jìn)行初始化，默認(rèn)為一個(gè)空格
        for (int i = 0; i < arrayHeight; i++) {
            for (int j = 0; j < arrayWidth; j++) {
                res[i][j] = " ";
            }
        }
        // 從根節(jié)點(diǎn)開(kāi)始，遞歸處理整個(gè)樹(shù)
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth / 2, res, treeDepth);
        // 此時(shí)，已經(jīng)將所有需要顯示的元素儲(chǔ)存到了二維數(shù)組中，將其拼接并打印即可
        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());
        }
    }
}

package com.haust.map;
import java.util.Scanner;
/**
 * @Auther: csp1999
 * @Date: 2020/11/09/15:08
 * @Description: RBTree紅黑樹(shù) 測(cè)試
 */
public class RBTreeTest {
    public static void main(String[] args) {
        RBTree<String, Object> rbtree = new RBTree();
        //測(cè)試輸入：ijkgefhdabc
        while(true) {
            Scanner sc = new Scanner(System.in);
            System.out.println("請(qǐng)輸入key:");
            String key = sc.next();
            rbtree.insert(key, null);
            TreeOperation.show(rbtree.getRoot());
        }
    }
}

請(qǐng)輸入key:
i
i-B
請(qǐng)輸入key:
j
   i-B 
    \  
     j-R
請(qǐng)輸入key:
k
   j-B 
  / \  
 i-R k-R
請(qǐng)輸入key:
g
      j-B    
    /   \    
  i-B     k-B
 /           
g-R          
請(qǐng)輸入key:
e
      j-B    
    /   \    
  g-B     k-B
 / \         
e-R i-R      
請(qǐng)輸入key:
f
            j-B          
         /     \         
      g-R         k-B    
    /   \                
  e-B     i-B            
   \                     
    f-R                  
請(qǐng)輸入key:
h
            j-B          
         /     \         
      g-R         k-B    
    /   \                
  e-B     i-B            
   \     /               
    f-R h-R              
請(qǐng)輸入key:
d
            j-B          
         /     \         
      g-R         k-B    
    /   \                
  e-B     i-B            
 / \     /               
d-R f-R h-R              
請(qǐng)輸入key:
a
            g-B          
         /     \         
      e-R         j-R    
    /   \       /   \    
  d-B     f-B i-B     k-B
 /           /           
a-R         h-R          
請(qǐng)輸入key:
b
            g-B          
         /     \         
      e-R         j-R    
    /   \       /   \    
  b-B     f-B i-B     k-B
 / \         /           
a-R d-R     h-R          
請(qǐng)輸入key:
c
                        g-B                      
                    /       \                    
                e-B             j-B              
             /     \         /     \             
          b-R         f-B i-B         k-B        
        /   \           /                        
      a-B     d-B     h-R                        
             /                                   
            c-R  

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;// 父節(jié)點(diǎn)
        TreeNode<K,V> left;// 左子樹(shù)
        TreeNode<K,V> right;// 右子樹(shù)
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;// 顏色
    	/**
    	 * 有參構(gòu)造函數(shù)
    	 */
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
        /**
         * 獲取紅黑樹(shù)的根節(jié)點(diǎn)
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }
        /**
         * 確保給定的根root是樹(shù)的第一個(gè)節(jié)點(diǎn)
         */
        static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
           ...
        }
       /**
        * 調(diào)用find方法查找.
        */        
       final TreeNode<K, V> getTreeNode(int h, Object k) {
            // 從樹(shù)的根節(jié)點(diǎn)開(kāi)始查找
            return ((parent != null) ? root() : this).find(h, k, null);
        }
        /**
         * 從根節(jié)點(diǎn)出發(fā)查找具有給定哈希值和鍵的節(jié)點(diǎn).從根節(jié)點(diǎn)出發(fā)
         * 查找當(dāng)前要插入節(jié)點(diǎn)node的父節(jié)點(diǎn)
         *
         * 經(jīng)典二叉查找樹(shù)的查找過(guò)程，先根據(jù)hash值比較，再根據(jù)key值比較決定是查左子樹(shù)還是右子樹(shù)。
         */
        final TreeNode<K, V> find(int h, Object k, Class<?> kc) {
            TreeNode<K, V> p = this;
            do {
                int ph, dir;
                K pk;
                TreeNode<K, V> pl = p.left, pr = p.right, q;
                if ((ph = p.hash) > h)
                    // 左子樹(shù)
                    p = pl;
                else if (ph < h)
                    // 右子樹(shù)
                    p = pr;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    // 找到了直接返回
                    return p;
                else if (pl == null)
                    // hash相同但key不同，左子樹(shù)為空查右子樹(shù)
                    p = pr;
                else if (pr == null)
                    // 右子樹(shù)為空查左子樹(shù)
                    p = pl;
                else if ((kc != null ||
                        (kc = comparableClassFor(k)) != null) &&
                        (dir = compareComparables(kc, k, pk)) != 0)
                    // 通過(guò)compare方法比較key值的大小決定使用左子樹(shù)還是右子樹(shù)
                    p = (dir < 0) ? pl : pr;
                else if ((q = pr.find(h, k, kc)) != null)
                    // 如果以上條件都不通過(guò)，則嘗試在右子樹(shù)查找
                    return q;
                else
                    // 都沒(méi)找到就在左子樹(shù)查找
                    p = pl;
            } while (p != null);
            return null;
        }
        /**
         * 用于在a 和 b 的hash值相等且不可比較時(shí)對(duì)插入進(jìn)行排序
         */
        static int tieBreakOrder(Object a, Object b) {
           ...
        }
        /**
         * 對(duì)鏈表進(jìn)行樹(shù)化的方法
         *（1）從鏈表的第一個(gè)元素開(kāi)始遍歷；
		*（2）將第一個(gè)元素作為根節(jié)點(diǎn)；
		*（3）其它元素依次插入到紅黑樹(shù)中，再做平衡；
		*（4）將根節(jié)點(diǎn)移到鏈表第一元素的位置（因?yàn)槠胶獾臅r(shí)候根節(jié)點(diǎn)會(huì)改變）；
         */
        final void treeify(Node<K, V>[] tab) {
            TreeNode<K, V> root = null;
            for (TreeNode<K, V> x = this, next; x != null; x = next) {
                next = (TreeNode<K, V>) x.next;
                x.left = x.right = null;
                // 第一個(gè)元素作為根節(jié)點(diǎn)且為黑節(jié)點(diǎn)，其它元素依次插入到樹(shù)中再做平衡
                if (root == null) {
                    x.parent = null;
                    x.red = false;
                    root = x;
                } else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    // 從根節(jié)點(diǎn)查找元素插入的位置
                    for (TreeNode<K, V> p = root; ; ) {
                        int dir, ph;
                        K pk = p.key;
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
                        else if ((kc == null &&
                                (kc = comparableClassFor(k)) == null) ||
                                (dir = compareComparables(kc, k, pk)) == 0)
                            dir = tieBreakOrder(k, pk);
                        // 如果最后沒(méi)找到元素，則插入
                        TreeNode<K, V> xp = p;
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            // 插入后平衡，默認(rèn)插入的是紅節(jié)點(diǎn)，在balanceInsertion()方法里
                            root = balanceInsertion(root, x);
                            break;
                        }
                    }
                }
            }
            // 把根節(jié)點(diǎn)移動(dòng)到鏈表的頭節(jié)點(diǎn)，因?yàn)榻?jīng)過(guò)平衡之后原來(lái)的第一個(gè)元素不一定是根節(jié)點(diǎn)了
            moveRootToFront(tab, root);
        }
        /**
         * 對(duì)紅黑樹(shù)進(jìn)行反樹(shù)化的方法
         */
        final Node<K,V> untreeify(HashMap<K,V> map) {
            Node<K,V> hd = null, tl = null;
            for (Node<K,V> q = this; q != null; q = q.next) {
                Node<K,V> p = map.replacementNode(q, null);
                if (tl == null)
                    hd = p;
                else
                    tl.next = p;
                tl = p;
            }
            return hd;
        }
        /**
         * 向樹(shù)種插入數(shù)據(jù)的方法
         *（1）尋找根節(jié)點(diǎn)；
         *（2）從根節(jié)點(diǎn)開(kāi)始查找；
         *（3）比較hash值及key值，如果都相同，直接返回，在putVal()方法中決定是否要替換value值；
         *（4）根據(jù)hash值及key值確定在樹(shù)的左子樹(shù)還是右子樹(shù)查找，找到了直接返回；
         *（5）如果最后沒(méi)有找到則在樹(shù)的相應(yīng)位置插入元素，并做平衡；
         */
        final TreeNode<K, V> putTreeVal(HashMap<K, V> map, Node<K, V>[] tab,
                                int h, K k, V v) {
            Class<?> kc = null;
            // 標(biāo)記是否找到這個(gè)key的節(jié)點(diǎn)
            boolean searched = false;
            // 找到樹(shù)的根節(jié)點(diǎn)
            TreeNode<K, V> root = (parent != null) ? root() : this;
            // 從樹(shù)的根節(jié)點(diǎn)開(kāi)始遍歷
            for (TreeNode<K, V> p = root; ; ) {
                // dir=direction，標(biāo)記是在左邊還是右邊
                // ph=p.hash，當(dāng)前節(jié)點(diǎn)的hash值
                int dir, ph;
                // pk=p.key，當(dāng)前節(jié)點(diǎn)的key值
                K pk;
                if ((ph = p.hash) > h) {
                    // 當(dāng)前hash比目標(biāo)hash大，說(shuō)明在左邊
                    dir = -1;
                }
                else if (ph < h)
                    // 當(dāng)前hash比目標(biāo)hash小，說(shuō)明在右邊
                    dir = 1;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    // 兩者h(yuǎn)ash相同且key相等，說(shuō)明找到了節(jié)點(diǎn)，直接返回該節(jié)點(diǎn)
                    // 回到putVal()中判斷是否需要修改其value值
                    return p;
                else if ((kc == null &&
                        // 如果k是Comparable的子類則返回其真實(shí)的類，否則返回null
                        (kc = comparableClassFor(k)) == null) ||
                        // 如果k和pk不是同樣的類型則返回0，否則返回兩者比較的結(jié)果
                        (dir = compareComparables(kc, k, pk)) == 0) {
                    // 這個(gè)條件表示兩者h(yuǎn)ash相同但是其中一個(gè)不是Comparable類型或者兩者類型不同
                    // 比如key是Object類型，這時(shí)可以傳String也可以傳Integer，兩者h(yuǎn)ash值可能相同
                    // 在紅黑樹(shù)中把同樣hash值的元素存儲(chǔ)在同一顆子樹(shù)，這里相當(dāng)于找到了這顆子樹(shù)的頂點(diǎn)
                    // 從這個(gè)頂點(diǎn)分別遍歷其左右子樹(shù)去尋找有沒(méi)有跟待插入的key相同的元素
                    if (!searched) {
                        TreeNode<K, V> q, ch;
                        searched = true;
                        // 遍歷左右子樹(shù)找到了直接返回
                        if (((ch = p.left) != null &&
                                (q = ch.find(h, k, kc)) != null) ||
                                ((ch = p.right) != null &&
                                        (q = ch.find(h, k, kc)) != null))
                            return q;
                    }
                    // 如果兩者類型相同，再根據(jù)它們的內(nèi)存地址計(jì)算hash值進(jìn)行比較
                    dir = tieBreakOrder(k, pk);
                }
                TreeNode<K, V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    // 如果最后確實(shí)沒(méi)找到對(duì)應(yīng)key的元素，則新建一個(gè)節(jié)點(diǎn)
                    Node<K, V> xpn = xp.next;
                    TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((TreeNode<K, V>) xpn).prev = x;
                    // 插入樹(shù)節(jié)點(diǎn)后平衡
                    // 把root節(jié)點(diǎn)移動(dòng)到鏈表的第一個(gè)節(jié)點(diǎn)
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }
        // remove 調(diào)用 removeNode
        //public V remove(Object key) {
        //    Node<K, V> e;
        //    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        //            null : e.value;
        //}
        
        final Node<K, V> removeNode(int hash, Object key, Object value,
                                    boolean matchValue, boolean movable) {
            Node<K, V>[] tab;
            Node<K, V> p;
            int n, index;
            // 如果桶的數(shù)量大于0且待刪除的元素所在的桶的第一個(gè)元素不為空
            if ((tab = table) != null && (n = tab.length) > 0 &&
                    (p = tab[index = (n - 1) & hash]) != null) {
                Node<K, V> node = null, e;
                K k;
                V v;
                if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                    // 如果第一個(gè)元素正好就是要找的元素，賦值給node變量后續(xù)刪除使用
                    node = p;
                else if ((e = p.next) != null) {
                    if (p instanceof TreeNode)
                        // 如果第一個(gè)元素是樹(shù)節(jié)點(diǎn)，則以樹(shù)的方式查找節(jié)點(diǎn)
                        node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
                    else {
                        // 否則遍歷整個(gè)鏈表查找元素
                        do {
                            if (e.hash == hash &&
                                    ((k = e.key) == key ||
                                            (key != null && key.equals(k)))) {
                                node = e;
                                break;
                            }
                            p = e;
                        } while ((e = e.next) != null);
                    }
                }
                // 如果找到了元素，則看參數(shù)是否需要匹配value值，如果不需要匹配直接刪除，
                // 如果需要匹配則看value值是否與傳入的value相等
                if (node != null && (!matchValue || (v = node.value) == value ||
                        (value != null && value.equals(v)))) {
                    if (node instanceof TreeNode)
                        // 如果是樹(shù)節(jié)點(diǎn)，調(diào)用樹(shù)的刪除方法（以node調(diào)用的，是刪除自己）
                        ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
                    else if (node == p)
                        // 如果待刪除的元素是第一個(gè)元素，則把第二個(gè)元素移到第一的位置
                        tab[index] = node.next;
                    else
                        // 否則刪除node節(jié)點(diǎn)
                        p.next = node.next;
                    ++modCount;
                    --size;
                    // 刪除節(jié)點(diǎn)后置處理
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }
   /**
	*（1）先查找元素所在的節(jié)點(diǎn)；
	*（2）如果找到的節(jié)點(diǎn)是樹(shù)節(jié)點(diǎn)，則按樹(shù)的移除節(jié)點(diǎn)處理；
     *（3）如果找到的節(jié)點(diǎn)是桶中的第一個(gè)節(jié)點(diǎn)，則把第二個(gè)節(jié)點(diǎn)移到第一的位置；
     *（4）否則按鏈表刪除節(jié)點(diǎn)處理；
     *（5）修改size，調(diào)用移除節(jié)點(diǎn)后置處理等；
     */    
    final void removeTreeNode(HashMap<K, V> map, Node<K, V>[] tab,
                                  boolean movable) {
            int n;
            // 如果桶的數(shù)量為0直接返回
            if (tab == null || (n = tab.length) == 0)
                return;
            // 節(jié)點(diǎn)在桶中的索引
            int index = (n - 1) & hash;
            // 第一個(gè)節(jié)點(diǎn)，根節(jié)點(diǎn)，根左子節(jié)點(diǎn)
            TreeNode<K, V> first = (TreeNode<K, V>) tab[index], root = first, rl;
            // 后繼節(jié)點(diǎn)，前置節(jié)點(diǎn)
            TreeNode<K, V> succ = (TreeNode<K, V>) next, pred = prev;
            if (pred == null)
                // 如果前置節(jié)點(diǎn)為空，說(shuō)明當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn)，則把后繼節(jié)點(diǎn)賦值到第一個(gè)節(jié)點(diǎn)的位置，相當(dāng)于刪除了當(dāng)前節(jié)點(diǎn)
                tab[index] = first = succ;
            else
                // 否則把前置節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)，相當(dāng)于刪除了當(dāng)前節(jié)點(diǎn)
                pred.next = succ;
            // 如果后繼節(jié)點(diǎn)不為空，則讓后繼節(jié)點(diǎn)的前置節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)的前置節(jié)點(diǎn)，相當(dāng)于刪除了當(dāng)前節(jié)點(diǎn)
            if (succ != null)
                succ.prev = pred;
            // 如果第一個(gè)節(jié)點(diǎn)為空，說(shuō)明沒(méi)有后繼節(jié)點(diǎn)了，直接返回
            if (first == null)
                return;
            // 如果根節(jié)點(diǎn)的父節(jié)點(diǎn)不為空，則重新查找父節(jié)點(diǎn)
            if (root.parent != null)
                root = root.root();
            // 如果根節(jié)點(diǎn)為空，則需要反樹(shù)化（將樹(shù)轉(zhuǎn)化為鏈表）
            // 如果需要移動(dòng)節(jié)點(diǎn)且樹(shù)的高度比較小，則需要反樹(shù)化
            if (root == null
                    || (movable
                    && (root.right == null
                    || (rl = root.left) == null
                    || rl.left == null))) {
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            // 分割線，以上都是刪除鏈表中的節(jié)點(diǎn)，下面才是直接刪除紅黑樹(shù)的節(jié)點(diǎn)（因?yàn)門(mén)reeNode本身即是鏈表節(jié)點(diǎn)又是樹(shù)節(jié)點(diǎn)）
            // 刪除紅黑樹(shù)節(jié)點(diǎn)的大致過(guò)程是尋找右子樹(shù)中最小的節(jié)點(diǎn)放到刪除節(jié)點(diǎn)的位置，然后做平衡，此處不過(guò)多注釋
            TreeNode<K, V> p = this, pl = left, pr = right, replacement;
            if (pl != null && pr != null) {
                TreeNode<K, V> s = pr, sl;
                while ((sl = s.left) != null) // find successor
                    s = sl;
                boolean c = s.red;
                s.red = p.red;
                p.red = c; // swap colors
                TreeNode<K, V> sr = s.right;
                TreeNode<K, V> pp = p.parent;
                if (s == pr) { // p was s's direct parent
                    p.parent = s;
                    s.right = p;
                } else {
                    TreeNode<K, V> sp = s.parent;
                    if ((p.parent = sp) != null) {
                        if (s == sp.left)
                            sp.left = p;
                        else
                            sp.right = p;
                    }
                    if ((s.right = pr) != null)
                        pr.parent = s;
                }
                p.left = null;
                if ((p.right = sr) != null)
                    sr.parent = p;
                if ((s.left = pl) != null)
                    pl.parent = s;
                if ((s.parent = pp) == null)
                    root = s;
                else if (p == pp.left)
                    pp.left = s;
                else
                    pp.right = s;
                if (sr != null)
                    replacement = sr;
                else
                    replacement = p;
            } else if (pl != null)
                replacement = pl;
            else if (pr != null)
                replacement = pr;
            else
                replacement = p;
            if (replacement != p) {
                TreeNode<K, V> pp = replacement.parent = p.parent;
                if (pp == null)
                    root = replacement;
                else if (p == pp.left)
                    pp.left = replacement;
                else
                    pp.right = replacement;
                p.left = p.right = p.parent = null;
            }
            TreeNode<K, V> r = p.red ? root : balanceDeletion(root, replacement);
            if (replacement == p) {  // detach
                TreeNode<K, V> pp = p.parent;
                p.parent = null;
                if (pp != null) {
                    if (p == pp.left)
                        pp.left = null;
                    else if (p == pp.right)
                        pp.right = null;
                }
            }
            if (movable)
                moveRootToFront(tab, r);
        }
        /**
         * Splits nodes in a tree bin into lower and upper tree bins,
         * or untreeifies if now too small. Called only from resize;
         * see above discussion about split bits and indices.
         *
         * @param map the map
         * @param tab the table for recording bin heads
         * @param index the index of the table being split
         * @param bit the bit of hash to split on
         */
        final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
           ...
        }
        // 左旋
        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
            TreeNode<K,V> r, pp, rl;
            if (p != null && (r = p.right) != null) {
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                r.left = p;
                p.parent = r;
            }
            return root;
        }
        // 右旋
        static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            TreeNode<K,V> l, pp, lr;
            if (p != null && (l = p.left) != null) {
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                l.right = p;
                p.parent = l;
            }
            return root;
        }
        // 修復(fù)紅黑樹(shù)平衡的方法
        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
            x.red = true;
            for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
                if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (!xp.red || (xpp = xp.parent) == null)
                    return root;
                if (xp == (xppl = xpp.left)) {
                    if ((xppr = xpp.right) != null && xppr.red) {
                        xppr.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.right) {
                            root = rotateLeft(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateRight(root, xpp);
                            }
                        }
                    }
                }
                else {
                    if (xppl != null && xppl.red) {
                        xppl.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.left) {
                            root = rotateRight(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }
        }
        static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                   TreeNode<K,V> x) {
            for (TreeNode<K,V> xp, xpl, xpr;;) {
                if (x == null || x == root)
                    return root;
                else if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (x.red) {
                    x.red = false;
                    return root;
                }
                else if ((xpl = xp.left) == x) {
                    if ((xpr = xp.right) != null && xpr.red) {
                        xpr.red = false;
                        xp.red = true;
                        root = rotateLeft(root, xp);
                        xpr = (xp = x.parent) == null ? null : xp.right;
                    }
                    if (xpr == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                        if ((sr == null || !sr.red) &&
                            (sl == null || !sl.red)) {
                            xpr.red = true;
                            x = xp;
                        }
                        else {
                            if (sr == null || !sr.red) {
                                if (sl != null)
                                    sl.red = false;
                                xpr.red = true;
                                root = rotateRight(root, xpr);
                                xpr = (xp = x.parent) == null ?
                                    null : xp.right;
                            }
                            if (xpr != null) {
                                xpr.red = (xp == null) ? false : xp.red;
                                if ((sr = xpr.right) != null)
                                    sr.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateLeft(root, xp);
                            }
                            x = root;
                        }
                    }
                }
                else { // symmetric
                    if (xpl != null && xpl.red) {
                        xpl.red = false;
                        xp.red = true;
                        root = rotateRight(root, xp);
                        xpl = (xp = x.parent) == null ? null : xp.left;
                    }
                    if (xpl == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpl.left, sr = xpl.right;
                        if ((sl == null || !sl.red) &&
                            (sr == null || !sr.red)) {
                            xpl.red = true;
                            x = xp;
                        }
                        else {
                            if (sl == null || !sl.red) {
                                if (sr != null)
                                    sr.red = false;
                                xpl.red = true;
                                root = rotateLeft(root, xpl);
                                xpl = (xp = x.parent) == null ?
                                    null : xp.left;
                            }
                            if (xpl != null) {
                                xpl.red = (xp == null) ? false : xp.red;
                                if ((sl = xpl.left) != null)
                                    sl.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateRight(root, xp);
                            }
                            x = root;
                        }
                    }
                }
            }
        }
        /**
         * Recursive invariant check
         */
        static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
            TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
                tb = t.prev, tn = (TreeNode<K,V>)t.next;
            if (tb != null && tb.next != t)
                return false;
            if (tn != null && tn.prev != t)
                return false;
            if (tp != null && t != tp.left && t != tp.right)
                return false;
            if (tl != null && (tl.parent != t || tl.hash > t.hash))
                return false;
            if (tr != null && (tr.parent != t || tr.hash < t.hash))
                return false;
            if (t.red && tl != null && tl.red && tr != null && tr.red)
                return false;
            if (tl != null && !checkInvariants(tl))
                return false;
            if (tr != null && !checkInvariants(tr))
                return false;
            return true;
        }
    }

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
   //轉(zhuǎn)換為紅黑樹(shù) tab表示數(shù)組名  hash表示哈希值
   treeifyBin(tab, hash);

/*
	替換指定哈希表的索引處桶中的所有鏈接結(jié)點(diǎn)，除非表太小，否則將修改大小。
	Node<K,V>[] tab = tab 數(shù)組名
	int hash = hash表示哈希值
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    /*
    	如果當(dāng)前數(shù)組為空或者數(shù)組的長(zhǎng)度小于進(jìn)行樹(shù)形化的閾值(MIN_TREEIFY_CAPACITY = 64)，
    	就去擴(kuò)容。而不是將結(jié)點(diǎn)變?yōu)榧t黑樹(shù)。
    	目的：如果數(shù)組很小，那么轉(zhuǎn)換紅黑樹(shù)，然后遍歷效率要低一些。這時(shí)進(jìn)行擴(kuò)容，
    	那么重新計(jì)算哈希值，鏈表長(zhǎng)度有可能就變短了，數(shù)據(jù)會(huì)放到數(shù)組中，這樣相對(duì)來(lái)說(shuō)效率高一些。
    */
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        //擴(kuò)容方法
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        /*
        	1）執(zhí)行到這里說(shuō)明哈希表中的數(shù)組長(zhǎng)度大于閾值64，開(kāi)始進(jìn)行樹(shù)形化
        	2）e = tab[index = (n - 1) & hash]表示將數(shù)組中的元素取出賦值給e，
        							e是哈希表中指定位置桶里的鏈表結(jié)點(diǎn)，從第一個(gè)開(kāi)始
        */
        // hd：紅黑樹(shù)的頭結(jié)點(diǎn)   tl：紅黑樹(shù)的尾結(jié)點(diǎn)
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 新創(chuàng)建一個(gè)樹(shù)的結(jié)點(diǎn)，內(nèi)容和當(dāng)前鏈表結(jié)點(diǎn)e一致
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p; // 將新創(chuàng)鍵的p結(jié)點(diǎn)賦值給紅黑樹(shù)的頭結(jié)點(diǎn)
            else {
                p.prev = tl; // 將上一個(gè)結(jié)點(diǎn)p賦值給現(xiàn)在的p的前一個(gè)結(jié)點(diǎn)
                tl.next = p; // 將現(xiàn)在結(jié)點(diǎn)p作為樹(shù)的尾結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
            }
            tl = p;
            /*
            	e = e.next 將當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)賦值給e，如果下一個(gè)結(jié)點(diǎn)不等于null
            	則回到上面繼續(xù)取出鏈表中結(jié)點(diǎn)轉(zhuǎn)換為紅黑樹(shù)
            */
        } while ((e = e.next) != null);
        /*
        	讓桶中的第一個(gè)元素即數(shù)組中的元素指向新建的紅黑樹(shù)的結(jié)點(diǎn)，以后這個(gè)桶里的元素就是紅黑樹(shù)
        	而不是鏈表數(shù)據(jù)結(jié)構(gòu)了
        */
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}