紅黑樹--在hashMap中的以用

1.紅黑樹的定義

（1）每個節點隻有兩種顔色：紅色和黑色。

（2）根節點是黑色的。

（3）每個葉子節點（NIL）都是黑色的空節點。

（4）從根節點到葉子節點，不會出現兩個連續的紅色節點。

（5）從任何一個節點出發，到葉子節點，這條路徑上都有相同數目的黑色節點。

1、查詢節點

查詢節點是最簡單的一個，他的查找過程和二叉查找樹一樣，查找元素比目前節點大，就從右子樹繼續查找比較，查找元素比目前節點小，就從左子樹繼續查找比較。查找過程就不再贅述了。

2、插入節點

（1） 沒有父節點： 即為根節點，黑色

（2）父節點是黑色：不變

（3）父節點為紅色，叔叔節點為空：變色和旋轉

（4）父節點紅色，叔叔節點為紅色：變色

（5）父節點為紅色，叔叔節點為黑：變色和旋轉

/**
 * 插入平衡
 */
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    //将x節點設為紅色（新插入節點一開始為紅色）
    x.red = true;
    //一個沒有邊界的循環(需要内部跳出)
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        //取出x的父節點并判斷是否為null
        if ((xp = x.parent) == null) {
            //x沒有父節點
            x.red = false;//變色(黑色)
            return x;//x為根節點發那會
        }
        //如果x存在父節點且x的父節點為黑色或x的父父節點不存在
        else if (!xp.red || (xpp = xp.parent) == null)
            //傳回root
            return root;
        //如果x的父節點是父父節點的左孩子
        if (xp == (xppl = xpp.left)) {
            //父父節點的右孩子不為null且為紅色
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false;//變色(黑)
                xp.red = false;//變色(黑)
                xpp.red = true;//變色(紅)
                x = xpp;
            }
            else {
                //x是父節點的右孩子
                if (x == xp.right) {
                    //左旋
                    root = rotateLeft(root, x = xp);
                    //處理x的父父節點
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                //x的父節點存在
                if (xp != null) {
                    xp.red = false;//變色
                    //x的父父節點存在
                    if (xpp != null) {
                        xpp.red = true;//變色
                        //右旋
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        //如果x的父節點是父父節點的右孩子
        else {
            //x的父父節點的左孩子存在且為紅色
            if (xppl != null && xppl.red) {
                xppl.red = false;//變色(黑)
                xp.red = false;//變色(黑)
                xpp.red = true;//變色(紅)
                x = xpp;
            }
            else {
                //如果x是父節點的左孩子
                if (x == xp.left) {
                    //右旋
                    root = rotateRight(root, x = xp);
                    //處理x的父父節點
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                //如果x的父節點存在
                if (xp != null) {
                    xp.red = false;//變色(黑)
                    //如果x的父父節點存在
                    if (xpp != null) {
                        xpp.red = true;//變色(紅)
                        //左旋
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}
           

1、将連結清單的首節點當做臨時的紅黑樹根節點，左右孩子置為null

2、循環按順序取對外連結表的節點，進行紅黑樹插入，和插入後平衡

2.1、取對外連結表節點，經過hash比較，插入到紅黑樹合适的位置(保證平衡性)

2.2、由于插入的節點會破壞紅黑樹的性質，是以需要進行插入後平衡

2.2.1、新插入的節點置為紅色

2.2.2、父節點和父父節點的null判斷和顔色判斷

2.2.2.1、判斷新插入節點的父節點是否存在，不存在則傳回

2.2.2.1、如果父節點是黑色的，或者父父節點不存在着，則傳回

2.2.3、父節點是父父節點的左孩子還是右孩子判斷

2.2.3.1、是左孩子且兄弟節點存在并且是紅色，則執行相應的變色，然後進行下一輪判斷。

2.2.3.2、是左孩子當兄弟節點不存在（或者是黑色），則執行相應的左旋/右旋。

2.2.3.3、是右孩子且兄弟節點存在并且是紅色，則執行相應的變色，然後進行下一輪判斷。

2.2.3.4、是右孩子當兄弟節點不存在（或者是黑色），則執行相應的左旋/右旋。

3、連結清單循環完畢後，確定哈希桶指定位置存儲的是紅黑樹的根節點

參考：

https://blog.lzoro.com/2018/08/31/r_b_tree/

https://baijiahao.baidu.com/s?id=1645429373049393021&wfr=spider&for=pc