@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>
 * ⑥公開插入接口方法定義：insert(K key, V value);
 * <p>
 * ⑦內(nèi)部插入接口方法定義：insert(RBNode node);
 * <p>
 * ⑧修正插入導(dǎo)致紅黑樹失衡的方法定義：insertFIxUp(RBNode node);
 * <p>
 * ⑨測試紅黑樹正確性
 */
public class RBTree<K extends Comparable<K>, V> {
    private static final boolean RED = true;// 紅
    private static final boolean BLACK = false;// 黑
    /**
     * 樹根的引用
     **/
    private RBNode root;
    public RBNode getRoot() {
        return root;
    }
    /**
     * 獲取當(dāng)前節(jié)點的父節(jié)點
     *
     * @param node
     * @return
     */
    private RBNode parentOf(RBNode node) {
        if (node != null) {
            return node.parent;
        }
        return null;
    }
    /**
     * 節(jié)點是否為紅色
     *
     * @param node
     * @return
     */
    private boolean isRed(RBNode node) {
        if (node != null) {
            return node.color == RED;
        }
        return false;
    }
    /**
     * 節(jié)點是否為黑色
     *
     * @param node
     * @return
     */
    private boolean isBlack(RBNode node) {
        if (node != null) {
            return node.color == BLACK;
        }
        return false;
    }
    /**
     * 設(shè)置節(jié)點為紅色
     *
     * @param node
     */
    private void setRed(RBNode node) {
        if (node != null) {
            node.color = RED;
        }
    }
    /**
     * 設(shè)置節(jié)點為黑色
     *
     * @param node
     */
    private void setBlack(RBNode node) {
        if (node != null) {
            node.color = BLACK;
        }
    }
    /**
     * 中序打印二叉樹
     */
    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é)點
     *   p                   p
     *   |                   |
     *   x                   y
     *  / \      ---->      / \
     * lx  y               x   ry
     *    / \             / \
     *   ly  ry          lx  ly
     *
     * 左旋做了幾件事？
     * 1.將x的右子節(jié)點指向y的左子節(jié)點(ly)，并且把y的左子節(jié)點更新為x
     * 2.當(dāng)x的父節(jié)點(不為空時)，更新y的父節(jié)點為x的父節(jié)點，并將x的父節(jié)點 指定 子樹(當(dāng)前x的子樹位置) 指定為y
     * 3.將x的父節(jié)點更新為y，將y的左子節(jié)點更新為x
     */
    private void leftRotate(RBNode x) {
        RBNode y = x.right;// 獲得y
        // 1.將x的右子節(jié)點指向y的左子節(jié)點(ly)，并且把y的左子節(jié)點更新為x
        x.right = y.left;
        if (y.left != null) {
            y.left.parent = x;
        }
        // 2.當(dāng)x的父節(jié)點(不為空時)，更新y的父節(jié)點為x的父節(jié)點，并將x的父節(jié)點 指定 子樹(當(dāng)前x的子樹位置) 指定為y
        if (x.parent != null) {
            y.parent = x.parent;
            if (x == x.parent.left) {// 如果x是其父節(jié)點的左子節(jié)點，則將y放在x父節(jié)點的左邊
                x.parent.left = y;
            } else {
                x.parent.right = y;// 如果x是其父節(jié)點的右子節(jié)點，則將y放在x父節(jié)點的右邊
            }
        } else {// 說明x為根節(jié)點，此時需要更新y為根節(jié)點 的引用
            this.root = y;
            this.root.parent = null;// 根節(jié)點無父節(jié)點
        }
        // 3.將x的父節(jié)點更新為y，將y的左子節(jié)點更新為x
        x.parent = y;
        y.left = x;
    }
    /**
     * 右旋方法
     * 右旋示意圖：右旋y節(jié)點
     *
     *     p                       p
     *     |                       |
     *     y                       x
     *    / \          ---->      / \
     *   x   ry                  lx  y
     *  / \                         / \
     * lx  ly                      ly  ry
     *
     * 右旋都做了幾件事？
     * 1.將y的左子節(jié)點指向x的右子節(jié)點，并且更新x的右子節(jié)點的父節(jié)點為y
     * 2.當(dāng)y的父節(jié)點不為空時，更新x的父節(jié)點為y的父節(jié)點，更新y的父節(jié)點的指定子節(jié)點（y當(dāng)前位置） 為x
     * 3.更新y 的父節(jié)點為x ,更新x 的右子節(jié)點為y
     */
    private void rightRotate(RBNode y) {
        RBNode x = y.left;// 獲得 x
        // 1.將x的右子節(jié)點 賦值 給了 y 的左子節(jié)點，并且更新x的右子節(jié)點的父節(jié)點為 y
        y.left = x.right;
        if(x.right != null) {
            x.right.parent = y;
        }
        // 2.將y的父節(jié)點p（非空時）賦值給x的父節(jié)點，同時更新p的子節(jié)點為x（左或右）
        if(y.parent != null) {
            x.parent = y.parent;
            if(y.parent.left == y) {// 如果y是其父節(jié)點的左子節(jié)點，則將x放在y父節(jié)點的左邊
                y.parent.left = x;
            } else {// 如果y是其父節(jié)點的右子節(jié)點，則將x放在y父節(jié)點的右邊
                y.parent.right = x;
            }
        } else {// 說明y為根節(jié)點，此時需要更新x為根節(jié)點 的引用
            this.root = x;
            this.root.parent = null;// 根節(jié)點無父節(jié)點
        }
        // 3.將x的右子節(jié)點賦值為y，將y的父節(jié)點設(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é)點 一定要是紅色！
        node.setColor(RED);
        insert(node);
    }
    private void insert(RBNode node) {
        // 第一步：查找當(dāng)前要插入節(jié)點node的父節(jié)點
        RBNode parent = null;// 聲明要插入節(jié)點node的父節(jié)點
        RBNode x = this.root;
        while (x != null) {
            parent = x;
            /**
             * cmp > 0 說明node.key 大于 x.key 需要到x 的右子樹查找
             * cmp == 0 說明node.key 等于 x.key 需要進行替換操作
             * cmp < 0 說明node.key 小于 x.key 需要到x 的左子樹查找
             */
            int cmp = node.key.compareTo(x.key);
            if (cmp > 0) {
                x = x.right;
            } else if (cmp == 0) {
                x.setValue(node.getValue());
                return;// 修改完后 就不再繼續(xù)往下面的代碼執(zhí)行了
            } else {
                x = x.left;
            }
        }
        /**
         * 退出上面的while循環(huán)后，到這里，說明樹中沒有相同key 的元素
         *
         * 需要添加新元素node到 x(parent) 目前位置的左子樹/右子樹
         */
        node.parent = parent;
        if (parent != null) {
            // 判斷node與parent 的key 誰大
            int cmp = node.key.compareTo(parent.key);
            if (cmp > 0) {// 當(dāng)前node的key比parent 的key大，需要把node放入parent 的右子節(jié)點
                parent.right = node;
            } else {// 當(dāng)前node的key比parent 的key小，需要把node放入parent 的左子節(jié)點
                parent.left = node;
            }
        } else {// parent == null; 說明為空樹
            this.root = node;// 直接給樹根賦值為node
        }
        // 新元素node 加入樹中之后，要調(diào)用修復(fù)紅黑樹平衡的方法
        insertFixUp(node);
    }
    /**
     * 插入后修復(fù)紅黑樹平衡的方法
     * |---情景1：如果紅黑樹為空樹,需要將根節(jié)點染為黑色
     * |---情景2：如果插入節(jié)點的key已經(jīng)存在,(這種情況不需要處理,因為修改樹中的值不會觸發(fā)紅黑樹修復(fù)平衡方法)
     * |---情景3：如果插入節(jié)點的父節(jié)點為黑色,這種情況不需要處理,(參考紅黑樹的性質(zhì)4和性指5去理解)
     * (因為所插入的路徑中,黑色節(jié)點數(shù)沒發(fā)生變化,所以紅黑樹依然平衡)
     * <p>
     * 情景4 需要去處理的情景
     * |---情景4：插入節(jié)點的父節(jié)點為紅色,(違反紅黑樹性質(zhì)4,不能有兩個紅色節(jié)點相連)
     * |---情景4.1：叔叔節(jié)點存在，并且為紅色（父-叔 雙紅）
     * 處理：將爸爸和叔叔染成黑色，將爺爺染成紅色，并且再以爺爺節(jié)點為當(dāng)前節(jié)點，進行下一輪處理
     * |---情景4.2：叔叔節(jié)點不存在，或者為黑色，父節(jié)點為爺爺節(jié)點的左子樹
     * 處理：
     * |---情景4.2.1：插入節(jié)點為其父節(jié)點的左子節(jié)點（LL情況）
     * 處理：將父節(jié)點染為黑色，將爺爺染為紅色，然后以爺爺節(jié)點右旋即可
     * |---情景4.2.2：插入節(jié)點為其父節(jié)點的右子節(jié)點（LR情況）
     * 處理：將父節(jié)點進行一次左旋，得到LL雙紅情景(4.2.1),然后指定父節(jié)點為當(dāng)前節(jié)點進行下一輪處理
     * |---情景4.3：叔叔節(jié)點不存在，或者為黑色，父節(jié)點為爺爺節(jié)點的右子樹
     * |---情景4.3.1：插入節(jié)點為其父節(jié)點的右子節(jié)點（RR情況）
     * 處理：將父節(jié)點染為黑色，將爺爺節(jié)點染為紅色，然后以爺爺節(jié)點左旋即可
     * |---情景4.3.2：插入節(jié)點為其父節(jié)點的左子節(jié)點（RL情況）
     * 處理：以父節(jié)點進行一次右旋，得到RR雙紅情景(4.3.1),然后指定父節(jié)點為當(dāng)前節(jié)點進行下一輪處理
     */
    private void insertFixUp(RBNode node) {
        RBNode parent = parentOf(node);// 當(dāng)前節(jié)點的父節(jié)點
        RBNode gparent = parentOf(parent);// 當(dāng)前節(jié)點的爺爺節(jié)點
        // 存在父節(jié)點且父節(jié)點為紅色
        if (parent != null && isRed(parent)) {
            // 父節(jié)點是紅色的，那么一定存在爺爺節(jié)點(性質(zhì)2：根節(jié)點只能是黑色)
            // 父節(jié)點為爺爺節(jié)點的左子樹
            if (parent == gparent.left) {
                RBNode uncle = gparent.right;
                // 情景4.1：叔叔節(jié)點存在，并且為紅色（父-叔 雙紅）
                // 將父和叔染色為黑色，再將爺爺染紅，并將爺爺設(shè)置為當(dāng)前節(jié)點，進入下一次循環(huán)判斷
                if (uncle != null && isRed(uncle)) {
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gparent);
                    insertFixUp(gparent);
                    return;
                }
                // 情景4.2：叔叔節(jié)點不存在，或者為黑色，父節(jié)點為爺爺節(jié)點的左子樹
                if (uncle == null || isBlack(uncle)) {
                    /**
                     * 情景4.2.1：插入節(jié)點為其父節(jié)點的左子節(jié)點（LL情況）
                     * 處理：將父節(jié)點染為黑色，將爺爺染為紅色，然后以爺爺節(jié)點右旋即可
                     */
                    // 插入節(jié)點為其父節(jié)點的左子節(jié)點（LL情況）=>
                    // 變色（父節(jié)點變黑，爺爺節(jié)點變紅），右旋爺爺節(jié)點
                    if (node == parent.left) {
                        setBlack(parent);
                        setRed(gparent);
                        rightRotate(gparent);// 以gparent 右旋
                    }
                    /**
                     * 情景4.2.2：插入節(jié)點為其父節(jié)點的右子節(jié)點（LR情況）
                     * 處理：將父節(jié)點進行一次左旋，得到LL雙紅情景(4.2.1),然后指定父節(jié)點為當(dāng)前節(jié)點進行下一輪處理
                     */
                    // 插入節(jié)點為其父節(jié)點的右子節(jié)點（LR情況）=>
                    // 左旋（父節(jié)點），當(dāng)前節(jié)點設(shè)置為父節(jié)點，進入下一次循環(huán)
                    if (node == parent.right) {
                        leftRotate(parent);// parent 左旋
                        insertFixUp(parent);// 進行下一輪處理
                        return;
                    }
                }
            } else {// 父節(jié)點為爺爺節(jié)點的右子樹
                RBNode uncle = gparent.left;
                // 情景4.1：叔叔節(jié)點存在，并且為紅色（父-叔 雙紅）
                // 將父和叔染色為黑色，再將爺爺染紅，并將爺爺設(shè)置為當(dāng)前節(jié)點，進入下一次循環(huán)判斷
                if (uncle != null && isRed(uncle)) {
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gparent);
                    insertFixUp(gparent);// 進行下一輪處理
                    return;
                }
                // 情景4.3：叔叔節(jié)點不存在，或者為黑色，父節(jié)點為爺爺節(jié)點的右子樹
                if (uncle == null || isBlack(uncle)) {
                    /**
                     * 情景4.3.1：插入節(jié)點為其父節(jié)點的右子節(jié)點（RR情況）
                     * 處理：將父節(jié)點染為黑色，將爺爺節(jié)點染為紅色，然后以爺爺節(jié)點左旋即可
                     */
                    // 插入節(jié)點為其父節(jié)點的右子節(jié)點（RR情況）=>
                    // 變色（父節(jié)點變黑，爺爺節(jié)點變紅），右旋爺爺節(jié)點
                    if (node == parent.right) {
                        setBlack(parent);
                        setRed(gparent);
                        leftRotate(gparent);
                    }
                    /**
                     * 情景4.3.2：插入節(jié)點為其父節(jié)點的左子節(jié)點（RL情況）
                     * 處理：以父節(jié)點進行一次右旋，得到RR雙紅情景(4.3.1),然后指定父節(jié)點為當(dāng)前節(jié)點進行下一輪處理
                     */
                    // 插入節(jié)點為其父節(jié)點的左子節(jié)點（RL情況）
                    // 右旋（父節(jié)點）得到RR情況，當(dāng)前節(jié)點設(shè)置為父節(jié)點，進入下一次循環(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é)點
        private RBNode left;// 左子樹
        private RBNode right;// 右子樹
        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: 打印紅黑樹的工具類
 */
public class TreeOperation {
    /*
           樹的結(jié)構(gòu)示例：
              1
            /   \
          2       3
         / \     / \
        4   5   6   7
    */
    // 用于獲得樹的層數(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) {
        // 保證輸入的樹不為空
        if (currNode == null) return;
        // 先將當(dāng)前節(jié)點保存到二維數(shù)組中
        res[rowIndex][columnIndex] = String.valueOf(currNode.getKey() /*+ "-" + (currNode.isColor() ? "R" : "B") + ""*/);
        // 計算當(dāng)前位于樹的第幾層
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一層，則返回
        if (currLevel == treeDepth) return;
        // 計算當(dāng)前行到下一行，每個元素之間的間隔（下一行的列索引與當(dāng)前元素的列索引之間的間隔）
        int gap = treeDepth - currLevel - 1;
        // 對左兒子進行判斷，若有左兒子，則記錄相應(yīng)的"/"與左兒子的值
        if (currNode.getLeft() != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }
        // 對右兒子進行判斷，若有右兒子，則記錄相應(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!");
        // 得到樹的深度
        int treeDepth = getTreeDepth(root);
        // 最后一行的寬度為2的（n - 1）次方乘3，再加1
        // 作為整個二維數(shù)組的寬度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一個字符串?dāng)?shù)組來存儲每個位置應(yīng)顯示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 對數(shù)組進行初始化，默認(rèn)為一個空格
        for (int i = 0; i < arrayHeight; i++) {
            for (int j = 0; j < arrayWidth; j++) {
                res[i][j] = " ";
            }
        }
        // 從根節(jié)點開始，遞歸處理整個樹
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth / 2, res, treeDepth);
        // 此時，已經(jīng)將所有需要顯示的元素儲存到了二維數(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紅黑樹 測試
 */
public class RBTreeTest {
    public static void main(String[] args) {
        RBTree<String, Object> rbtree = new RBTree();
        //測試輸入：ijkgefhdabc
        while(true) {
            Scanner sc = new Scanner(System.in);
            System.out.println("請輸入key:");
            String key = sc.next();
            rbtree.insert(key, null);
            TreeOperation.show(rbtree.getRoot());
        }
    }
}

請輸入key:
i
i-B
請輸入key:
j
   i-B 
    \  
     j-R
請輸入key:
k
   j-B 
  / \  
 i-R k-R
請輸入key:
g
      j-B    
    /   \    
  i-B     k-B
 /           
g-R          
請輸入key:
e
      j-B    
    /   \    
  g-B     k-B
 / \         
e-R i-R      
請輸入key:
f
            j-B          
         /     \         
      g-R         k-B    
    /   \                
  e-B     i-B            
   \                     
    f-R                  
請輸入key:
h
            j-B          
         /     \         
      g-R         k-B    
    /   \                
  e-B     i-B            
   \     /               
    f-R h-R              
請輸入key:
d
            j-B          
         /     \         
      g-R         k-B    
    /   \                
  e-B     i-B            
 / \     /               
d-R f-R h-R              
請輸入key:
a
            g-B          
         /     \         
      e-R         j-R    
    /   \       /   \    
  d-B     f-B i-B     k-B
 /           /           
a-R         h-R          
請輸入key:
b
            g-B          
         /     \         
      e-R         j-R    
    /   \       /   \    
  b-B     f-B i-B     k-B
 / \         /           
a-R d-R     h-R          
請輸入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é)點
        TreeNode<K,V> left;// 左子樹
        TreeNode<K,V> right;// 右子樹
        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);
        }
        /**
         * 獲取紅黑樹的根節(jié)點
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }
        /**
         * 確保給定的根root是樹的第一個節(jié)點
         */
        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) {
            // 從樹的根節(jié)點開始查找
            return ((parent != null) ? root() : this).find(h, k, null);
        }
        /**
         * 從根節(jié)點出發(fā)查找具有給定哈希值和鍵的節(jié)點.從根節(jié)點出發(fā)
         * 查找當(dāng)前要插入節(jié)點node的父節(jié)點
         *
         * 經(jīng)典二叉查找樹的查找過程，先根據(jù)hash值比較，再根據(jù)key值比較決定是查左子樹還是右子樹。
         */
        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)
                    // 左子樹
                    p = pl;
                else if (ph < h)
                    // 右子樹
                    p = pr;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    // 找到了直接返回
                    return p;
                else if (pl == null)
                    // hash相同但key不同，左子樹為空查右子樹
                    p = pr;
                else if (pr == null)
                    // 右子樹為空查左子樹
                    p = pl;
                else if ((kc != null ||
                        (kc = comparableClassFor(k)) != null) &&
                        (dir = compareComparables(kc, k, pk)) != 0)
                    // 通過compare方法比較key值的大小決定使用左子樹還是右子樹
                    p = (dir < 0) ? pl : pr;
                else if ((q = pr.find(h, k, kc)) != null)
                    // 如果以上條件都不通過，則嘗試在右子樹查找
                    return q;
                else
                    // 都沒找到就在左子樹查找
                    p = pl;
            } while (p != null);
            return null;
        }
        /**
         * 用于在a 和 b 的hash值相等且不可比較時對插入進行排序
         */
        static int tieBreakOrder(Object a, Object b) {
           ...
        }
        /**
         * 對鏈表進行樹化的方法
         *（1）從鏈表的第一個元素開始遍歷；
		*（2）將第一個元素作為根節(jié)點；
		*（3）其它元素依次插入到紅黑樹中，再做平衡；
		*（4）將根節(jié)點移到鏈表第一元素的位置（因為平衡的時候根節(jié)點會改變）；
         */
        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;
                // 第一個元素作為根節(jié)點且為黑節(jié)點，其它元素依次插入到樹中再做平衡
                if (root == null) {
                    x.parent = null;
                    x.red = false;
                    root = x;
                } else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    // 從根節(jié)點查找元素插入的位置
                    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);
                        // 如果最后沒找到元素，則插入
                        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é)點，在balanceInsertion()方法里
                            root = balanceInsertion(root, x);
                            break;
                        }
                    }
                }
            }
            // 把根節(jié)點移動到鏈表的頭節(jié)點，因為經(jīng)過平衡之后原來的第一個元素不一定是根節(jié)點了
            moveRootToFront(tab, root);
        }
        /**
         * 對紅黑樹進行反樹化的方法
         */
        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ù)據(jù)的方法
         *（1）尋找根節(jié)點；
         *（2）從根節(jié)點開始查找；
         *（3）比較hash值及key值，如果都相同，直接返回，在putVal()方法中決定是否要替換value值；
         *（4）根據(jù)hash值及key值確定在樹的左子樹還是右子樹查找，找到了直接返回；
         *（5）如果最后沒有找到則在樹的相應(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)記是否找到這個key的節(jié)點
            boolean searched = false;
            // 找到樹的根節(jié)點
            TreeNode<K, V> root = (parent != null) ? root() : this;
            // 從樹的根節(jié)點開始遍歷
            for (TreeNode<K, V> p = root; ; ) {
                // dir=direction，標(biāo)記是在左邊還是右邊
                // ph=p.hash，當(dāng)前節(jié)點的hash值
                int dir, ph;
                // pk=p.key，當(dāng)前節(jié)點的key值
                K pk;
                if ((ph = p.hash) > h) {
                    // 當(dāng)前hash比目標(biāo)hash大，說明在左邊
                    dir = -1;
                }
                else if (ph < h)
                    // 當(dāng)前hash比目標(biāo)hash小，說明在右邊
                    dir = 1;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    // 兩者h(yuǎn)ash相同且key相等，說明找到了節(jié)點，直接返回該節(jié)點
                    // 回到putVal()中判斷是否需要修改其value值
                    return p;
                else if ((kc == null &&
                        // 如果k是Comparable的子類則返回其真實的類，否則返回null
                        (kc = comparableClassFor(k)) == null) ||
                        // 如果k和pk不是同樣的類型則返回0，否則返回兩者比較的結(jié)果
                        (dir = compareComparables(kc, k, pk)) == 0) {
                    // 這個條件表示兩者h(yuǎn)ash相同但是其中一個不是Comparable類型或者兩者類型不同
                    // 比如key是Object類型，這時可以傳String也可以傳Integer，兩者h(yuǎn)ash值可能相同
                    // 在紅黑樹中把同樣hash值的元素存儲在同一顆子樹，這里相當(dāng)于找到了這顆子樹的頂點
                    // 從這個頂點分別遍歷其左右子樹去尋找有沒有跟待插入的key相同的元素
                    if (!searched) {
                        TreeNode<K, V> q, ch;
                        searched = true;
                        // 遍歷左右子樹找到了直接返回
                        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)存地址計算hash值進行比較
                    dir = tieBreakOrder(k, pk);
                }
                TreeNode<K, V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    // 如果最后確實沒找到對應(yīng)key的元素，則新建一個節(jié)點
                    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;
                    // 插入樹節(jié)點后平衡
                    // 把root節(jié)點移動到鏈表的第一個節(jié)點
                    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且待刪除的元素所在的桶的第一個元素不為空
            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))))
                    // 如果第一個元素正好就是要找的元素，賦值給node變量后續(xù)刪除使用
                    node = p;
                else if ((e = p.next) != null) {
                    if (p instanceof TreeNode)
                        // 如果第一個元素是樹節(jié)點，則以樹的方式查找節(jié)點
                        node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
                    else {
                        // 否則遍歷整個鏈表查找元素
                        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)
                        // 如果是樹節(jié)點，調(diào)用樹的刪除方法（以node調(diào)用的，是刪除自己）
                        ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
                    else if (node == p)
                        // 如果待刪除的元素是第一個元素，則把第二個元素移到第一的位置
                        tab[index] = node.next;
                    else
                        // 否則刪除node節(jié)點
                        p.next = node.next;
                    ++modCount;
                    --size;
                    // 刪除節(jié)點后置處理
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }
   /**
	*（1）先查找元素所在的節(jié)點；
	*（2）如果找到的節(jié)點是樹節(jié)點，則按樹的移除節(jié)點處理；
     *（3）如果找到的節(jié)點是桶中的第一個節(jié)點，則把第二個節(jié)點移到第一的位置；
     *（4）否則按鏈表刪除節(jié)點處理；
     *（5）修改size，調(diào)用移除節(jié)點后置處理等；
     */    
    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é)點在桶中的索引
            int index = (n - 1) & hash;
            // 第一個節(jié)點，根節(jié)點，根左子節(jié)點
            TreeNode<K, V> first = (TreeNode<K, V>) tab[index], root = first, rl;
            // 后繼節(jié)點，前置節(jié)點
            TreeNode<K, V> succ = (TreeNode<K, V>) next, pred = prev;
            if (pred == null)
                // 如果前置節(jié)點為空，說明當(dāng)前節(jié)點是根節(jié)點，則把后繼節(jié)點賦值到第一個節(jié)點的位置，相當(dāng)于刪除了當(dāng)前節(jié)點
                tab[index] = first = succ;
            else
                // 否則把前置節(jié)點的下個節(jié)點設(shè)置為當(dāng)前節(jié)點的后繼節(jié)點，相當(dāng)于刪除了當(dāng)前節(jié)點
                pred.next = succ;
            // 如果后繼節(jié)點不為空，則讓后繼節(jié)點的前置節(jié)點指向當(dāng)前節(jié)點的前置節(jié)點，相當(dāng)于刪除了當(dāng)前節(jié)點
            if (succ != null)
                succ.prev = pred;
            // 如果第一個節(jié)點為空，說明沒有后繼節(jié)點了，直接返回
            if (first == null)
                return;
            // 如果根節(jié)點的父節(jié)點不為空，則重新查找父節(jié)點
            if (root.parent != null)
                root = root.root();
            // 如果根節(jié)點為空，則需要反樹化（將樹轉(zhuǎn)化為鏈表）
            // 如果需要移動節(jié)點且樹的高度比較小，則需要反樹化
            if (root == null
                    || (movable
                    && (root.right == null
                    || (rl = root.left) == null
                    || rl.left == null))) {
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            // 分割線，以上都是刪除鏈表中的節(jié)點，下面才是直接刪除紅黑樹的節(jié)點（因為TreeNode本身即是鏈表節(jié)點又是樹節(jié)點）
            // 刪除紅黑樹節(jié)點的大致過程是尋找右子樹中最小的節(jié)點放到刪除節(jié)點的位置，然后做平衡，此處不過多注釋
            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ù)紅黑樹平衡的方法
        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)換為紅黑樹 tab表示數(shù)組名  hash表示哈希值
   treeifyBin(tab, hash);

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