概述

二叉搜索樹是優(yōu)化搜索效率最常用的數(shù)據(jù)結(jié)構(gòu)充边，時(shí)間復(fù)雜度為O(h)，其中h是樹的高度蘑辑⊙蠡可以看出，樹的高度是影響搜索效率的關(guān)鍵因素洋魂。在樹退化為一個(gè)鏈表(節(jié)點(diǎn)都在左或都在右)绷旗，搜索效率也就退化為O(n)。為了防止這種情況的出現(xiàn)平衡二叉搜索樹出現(xiàn)副砍，本文所介紹的紅黑樹就是一種特殊的"平衡"二叉樹刁标，因?yàn)榧t黑樹只能保證沒有一條路徑會(huì)比其他路徑長出2倍，所以并不是嚴(yán)格意義上的平衡樹址晕。但是這個(gè)性質(zhì)卻能保證最壞情況下搜索操作的復(fù)雜度是O(h)。

定義及性質(zhì)

紅黑樹每個(gè)節(jié)點(diǎn)包含color顿锰，key谨垃，left，right和p硼控，如果一個(gè)節(jié)點(diǎn)沒有子節(jié)點(diǎn)或者父節(jié)點(diǎn)刘陶，那么該節(jié)點(diǎn)響應(yīng)指針的屬性值為NIL，我們將NIL視為指向也節(jié)點(diǎn)的指針牢撼。一個(gè)紅黑樹必須滿足一下性質(zhì)：
(1) 每個(gè)節(jié)點(diǎn)只能是紅色或者黑色匙隔；
(2) 根節(jié)點(diǎn)是黑色；
(3) 每個(gè)葉節(jié)點(diǎn)（NIL）是黑色熏版；
(4) 紅節(jié)點(diǎn)的子節(jié)點(diǎn)一定是黑色纷责；
(5) 對(duì)于每個(gè)節(jié)點(diǎn)捍掺，從該節(jié)點(diǎn)到到期所有后代也節(jié)點(diǎn)的路徑上，均包含相同數(shù)目的黑節(jié)點(diǎn)再膳。

插入操作

紅黑樹的插入操作和一般的二叉搜索樹一樣挺勿，但是插入節(jié)點(diǎn)后需要進(jìn)行調(diào)整，以滿足紅黑樹的以上五個(gè)性質(zhì)喂柒。我們知道JDK8中的HashMap和ConcurrentHashMap在桶中鏈表長度大于等于8時(shí)會(huì)將鏈表轉(zhuǎn)換為紅黑樹以提高搜索效率不瓶，下面我們通過這塊代碼來了解下具體調(diào)整算法。下面代碼涉及兩個(gè)操作：左旋和右旋灾杰，大家可以認(rèn)為對(duì)x節(jié)點(diǎn)左旋就是用x節(jié)點(diǎn)的右子節(jié)點(diǎn)y代替x蚊丐，并且x成為y的左子節(jié)點(diǎn)；對(duì)x節(jié)點(diǎn)進(jìn)行右旋就是用x的左子節(jié)點(diǎn)y代替x并且x成y的右子節(jié)點(diǎn)艳吠。

左旋右旋.png

static <K,V> ConcurrentHashMap.TreeNode<K,V> balanceInsertion(ConcurrentHashMap.TreeNode<K,V> root,
                                                                  ConcurrentHashMap.TreeNode<K,V> x) {
        //1.所有新插入的節(jié)點(diǎn)顏色都是紅色
        x.red = true;
        for (ConcurrentHashMap.TreeNode<K,V> xp, xpp, xppl, xppr;;) {
            //如果節(jié)點(diǎn)是根節(jié)點(diǎn)麦备，那么直接將該節(jié)點(diǎn)置為黑色，結(jié)束
            if ((xp = x.parent) == null) {
                x.red = false;
                return x;
            }
            //如果x的父節(jié)點(diǎn)是黑色讲竿，符合紅黑樹定義直接返回泥兰。
            else if (!xp.red || (xpp = xp.parent) == null)
                return root;
            //2.插入的節(jié)點(diǎn)x的父節(jié)點(diǎn)是紅色并且是左子樹
            if (xp == (xppl = xpp.left)) {
                //2.1查看x的叔叔節(jié)點(diǎn)的顏色，如果是紅色题禀，那么將x的父節(jié)點(diǎn)鞋诗，叔節(jié)點(diǎn)置為黑色，爺爺節(jié)點(diǎn)置為紅色迈嘹，并將要調(diào)整的節(jié)點(diǎn)置為爺爺節(jié)點(diǎn)
                if ((xppr = xpp.right) != null && xppr.red) {
                    xppr.red = false;
                    xp.red = false;
                    xpp.red = true;
                    x = xpp;
                }
                else {
                  //2.2 x節(jié)點(diǎn)的叔叔節(jié)點(diǎn)是黑色削彬，且x是右子樹，那么將x的父節(jié)點(diǎn)進(jìn)行右旋
                    if (x == xp.right) {
                        root = rotateLeft(root, x = xp);
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                  //2.3 x節(jié)點(diǎn)的叔叔節(jié)點(diǎn)是黑色秀仲，且x是左子樹融痛，將父節(jié)點(diǎn)置為黑色，爺爺節(jié)點(diǎn)置為紅色并將爺爺節(jié)點(diǎn)進(jìn)行右旋
                    if (xp != null) {
                        xp.red = false;
                        if (xpp != null) {
                            xpp.red = true;
                            root = rotateRight(root, xpp);
                        }
                    }
                }
            }
           //3.插入節(jié)點(diǎn)x父節(jié)點(diǎn)是紅色并且是右子樹神僵，處理過程與情況2相同
            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);
                        }
                    }
                }
            }
        }
    }

刪除操作

相對(duì)于紅黑樹的插入操作雁刷，刪除操作比較麻煩，我們按照被刪除節(jié)點(diǎn)x的顏色和x的子節(jié)點(diǎn)情況分類如下保礼。為了更容易理解在有的情況下我們給出了操作圖沛励，紅色代表紅節(jié)點(diǎn)，黑色代表黑節(jié)點(diǎn)炮障，白色代表不知道該節(jié)點(diǎn)是紅還是黑目派，并且為了簡(jiǎn)化圖示我們沒有將NIL節(jié)點(diǎn)畫出，大家可以認(rèn)為所有頁節(jié)點(diǎn)都隱含一個(gè)黑色節(jié)點(diǎn)NIL胁赢。
(1) x為紅色并且x沒有子節(jié)點(diǎn)
這種情況下較為簡(jiǎn)單企蹭，直接刪除x不會(huì)破壞紅黑樹上述五個(gè)限制。
(2) x為紅色并且x有一個(gè)子節(jié)點(diǎn)
這種情況實(shí)際是不存在的，因?yàn)槿绻鹸是紅色谅摄，其子節(jié)點(diǎn)必定是黑色徒河，而左右子樹的黑高就不相等。
(3) x為黑色并且x有一個(gè)子節(jié)點(diǎn)
這種情況下螟凭，x的這個(gè)子節(jié)點(diǎn)y必定是紅色虚青，因此只需要將y替換為x并且將y置為黑色即可。具體如下圖：

image

(4) x為紅色并且x有兩個(gè)子節(jié)點(diǎn)

這種情況下螺男，可以找到x節(jié)點(diǎn)的后繼節(jié)點(diǎn)s棒厘，s的情況可能有以下兩種：

image

image

(5) x為黑色并且x有兩個(gè)子節(jié)點(diǎn)

這種情況同(4)的處理機(jī)制一樣。

(6) x為黑色并且x沒有子節(jié)點(diǎn)

這種情況比較復(fù)雜土辩，因?yàn)閯h除黑節(jié)點(diǎn)會(huì)破壞黑高支救。可以分為如下幾種情況討論：

(a). x節(jié)點(diǎn)的兄弟節(jié)點(diǎn)b有一個(gè)與其方向一致的紅色子節(jié)點(diǎn)s

此時(shí)將父節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)拷淘，并將刪除節(jié)點(diǎn)的黑色轉(zhuǎn)移到父節(jié)點(diǎn)各墨，而父節(jié)點(diǎn)原來位置的顏色保持不變。

image

(b). x節(jié)點(diǎn)的兄弟節(jié)點(diǎn)b有一個(gè)與其方向不一致的紅色節(jié)點(diǎn)s

此時(shí)首先通過旋轉(zhuǎn)操作轉(zhuǎn)為情況(a)启涯，再按照(a)進(jìn)行處理贬堵。

image

(c) 兄弟節(jié)點(diǎn)為黑色，且兄弟節(jié)點(diǎn)無紅色子節(jié)點(diǎn)

如果父節(jié)點(diǎn)是紅色结洼，那么將父節(jié)點(diǎn)置為黑色黎做，兄弟節(jié)點(diǎn)置為紅色即可解決問題。

image

如果父節(jié)點(diǎn)是黑色松忍，那么確實(shí)沒有紅節(jié)點(diǎn)可以作為黑節(jié)點(diǎn)轉(zhuǎn)移的節(jié)點(diǎn)蒸殿，只能對(duì)兄弟節(jié)點(diǎn)重新設(shè)置顏色，已平衡被刪除節(jié)點(diǎn)側(cè)減小的黑高鸣峭，并即將節(jié)點(diǎn)一直上移知道根節(jié)點(diǎn)使得所有的路徑的黑高都減1伟桅。

(d) 兄弟節(jié)點(diǎn)為紅色

這種情況可以通過旋轉(zhuǎn)父節(jié)點(diǎn)，轉(zhuǎn)換為父節(jié)點(diǎn)為紅色叽掘，兄弟節(jié)點(diǎn)為黑色的情況處理。

從以上的刪除過程可以看出玖雁，如果刪除節(jié)點(diǎn)是紅色節(jié)點(diǎn)更扁，不會(huì)破會(huì)黑高，可以直接刪除。如果刪除的節(jié)點(diǎn)是黑色節(jié)點(diǎn)浓镜，并且刪除的節(jié)點(diǎn)的父節(jié)點(diǎn)或者兄弟節(jié)點(diǎn)溃列，兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)存在紅色節(jié)點(diǎn)，那么可以通過旋轉(zhuǎn)操作即將紅色節(jié)點(diǎn)旋轉(zhuǎn)到被刪除節(jié)點(diǎn)側(cè)并置為黑色保持黑高不改變膛薛。如果以上節(jié)點(diǎn)都不存在紅色節(jié)點(diǎn)听隐，那么只能向上回溯整個(gè)樹的黑高整體減一。

原文

袁瓊瓊的技術(shù)博客哄啄，歡迎指針
https://yuanqiongqiong.cn/2019/06/09/%E7%BA%A2%E9%BB%91%E6%A0%91/