數(shù)據(jù)結(jié)構(gòu)與算法--從平衡二叉樹(AVL)到紅黑樹

上節(jié)學(xué)習(xí)了二叉查找樹调违。算法的性能取決于樹的形狀且轨，而樹的形狀取決于插入鍵的順序旋奢。在最好的情況下至朗，n個(gè)結(jié)點(diǎn)的樹是完全平衡的，如下圖“最好情況”所示唆香，此時(shí)樹的高度為?log2 n? + 1腾啥，所以時(shí)間復(fù)雜度為O(lg n)當(dāng)我們將鍵以升序或者降序插入的時(shí)候倘待，得到的是一棵斜樹，如下圖中的“最壞情況”贞间，樹的高度為n增热，時(shí)間復(fù)雜度也變成了O(n)

在最壞情況下公黑，二叉查找樹的查找和插入效率很低凡蚜。為了解決這個(gè)問題，引出了平衡二叉樹(AVL)谱醇。

平衡二叉樹介紹

平衡二叉樹，首先是一棵二叉查找樹煮剧，但是它滿足一點(diǎn)重要的特性：每一個(gè)結(jié)點(diǎn)的左子樹和右子樹的高度差最多為1轿秧。這個(gè)高度差限制就完全規(guī)避了上述的最壞情況漩符，因此查找嗜暴、插入和刪除的時(shí)間復(fù)雜度都變成了O(lg n)萎战。

為了反映每個(gè)結(jié)點(diǎn)的高度差蚂维，在二叉查找樹的結(jié)點(diǎn)中應(yīng)該增加一個(gè)新的域——被稱為平衡因子(BF)蔚约，它的值是某個(gè)根結(jié)點(diǎn)的左子樹深度減右子樹深度的值苹祟。易知，對于一棵平衡二叉樹砂轻，每個(gè)結(jié)點(diǎn)的平衡因子只可能是-1、0体谒、1三種可能。

上圖中圖1和圖4是平衡樹故响。圖2根本不是二叉查找樹，因?yàn)?9大于58卻是58的左子結(jié)點(diǎn)樟蠕；圖3中結(jié)點(diǎn)58的左子樹高度為3而右子樹的高度為0，不滿足平衡二叉樹的定義靡狞。不過將圖3稍作改變甘穿，得到圖4扒磁，它就是一棵平衡二叉樹了。

將每個(gè)結(jié)點(diǎn)的平衡因子控制在-1兰伤、0、1三個(gè)值是靠一種稱為旋轉(zhuǎn)(Rolate)的操作保證的符衔，視情況分為左旋轉(zhuǎn)和右旋轉(zhuǎn)。

如圖插入1的時(shí)候形帮，發(fā)現(xiàn)根結(jié)點(diǎn)3的平衡因子變成了2（正數(shù)），對結(jié)點(diǎn)3進(jìn)行右旋轉(zhuǎn)修正成上圖2的樣子合冀。

而當(dāng)插入5時(shí)，發(fā)現(xiàn)結(jié)點(diǎn)3的平衡因子為-2（負(fù)數(shù)）朝抖，所以需要對結(jié)點(diǎn)3進(jìn)行左旋轉(zhuǎn)修正成上圖5的樣子治宣。

再看插入結(jié)點(diǎn)9的情況坏怪，結(jié)點(diǎn)7的平衡因子變成了-2打掘，按理說應(yīng)該對7進(jìn)行左旋轉(zhuǎn)（上圖11），然而得到的確實(shí)圖11虛線框中的子樹横朋，9位于10的右子結(jié)點(diǎn)這明顯就是錯(cuò)的。究其原因决帖，主要是因?yàn)?strong>不平衡結(jié)點(diǎn)7和它的子樹10的平衡因子符號相反（一正一負(fù)），這種情況出現(xiàn)在新結(jié)點(diǎn)插入在根結(jié)點(diǎn)的左孩子的右子樹落君、或者根結(jié)點(diǎn)的右孩子的左子樹。后者情況下（即上圖情況）纹冤，需要先對根結(jié)點(diǎn)7的子結(jié)點(diǎn)10先作右旋轉(zhuǎn)處理再對根結(jié)點(diǎn)7進(jìn)行左旋處理。再回頭看前兩種插入情況，都是在根結(jié)點(diǎn)的左孩子的的左子樹或者根結(jié)點(diǎn)的右孩子的右子樹上插入的求妹，根結(jié)點(diǎn)的平衡因子符號和它子結(jié)點(diǎn)的平衡因子符號相同父能。

接下來看看這個(gè)旋轉(zhuǎn)處理是怎么用代碼表示的，以下所說的“根結(jié)點(diǎn)”指的是任意子樹的根岔霸。

public void rotateLeft(Node h) {
    Node x = h.right; // 根結(jié)點(diǎn)的右孩子保存為x
    h.right = x.left; // 根結(jié)點(diǎn)右孩子的左孩子掛到根結(jié)點(diǎn)的右孩子上
    x.left = h; // 根結(jié)點(diǎn)掛到根結(jié)點(diǎn)右孩子的左孩子上
    h = x; // 根結(jié)點(diǎn)的右孩子代替h稱為新的根結(jié)點(diǎn)
}

public void rotateRight(Node h) {
    Node x = h.left; // 根結(jié)點(diǎn)的左孩子保存為x
    h.left = x.right; // 根結(jié)點(diǎn)左孩子的右孩子掛到根結(jié)點(diǎn)的左孩子上
    x.right = h; // 根結(jié)點(diǎn)掛到根結(jié)點(diǎn)左孩子的右孩子上
    h = x; // 根結(jié)點(diǎn)的左孩子代替h稱為新的根結(jié)點(diǎn)
}

建議在紙上畫畫加深理解，其實(shí)旋轉(zhuǎn)操作沒那么難。

插入的話就是以下四種情況

• 在根結(jié)點(diǎn)的左孩子的左子樹上插入坑夯，對根結(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)。調(diào)用rotateRight
• 在根結(jié)點(diǎn)的右孩子的右子樹上插入淑履，對根結(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)。調(diào)用rotateLeft
• 在根結(jié)點(diǎn)的左孩子的右子樹上插入指煎，先對根結(jié)點(diǎn)的左孩子進(jìn)行左旋轉(zhuǎn)，再對根結(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)。調(diào)用rotateLeft(h.left);rotateRight(h);
• 在根結(jié)點(diǎn)的右孩子的左子樹上插入宅广，先對根結(jié)點(diǎn)的右孩子進(jìn)行右旋轉(zhuǎn)，再對根結(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)。調(diào)用rotateRight(h.right);rotateLeft(h);

插入之后還要調(diào)整每個(gè)結(jié)點(diǎn)的平衡因子关翎，看起來比較麻煩，代碼量不小爽茴。刪除操作也是比較麻煩。由于我們的重點(diǎn)在于講解紅黑樹，平衡查找樹只是拋磚引玉绒怨。所以對于平衡二叉樹的介紹就到此為止。

2-3樹介紹

為了保證查找樹的平衡性碎紊，我們允許樹中一個(gè)結(jié)點(diǎn)保存多個(gè)鍵 。標(biāo)準(zhǔn)二叉查找樹中的結(jié)點(diǎn)只能保存一個(gè)鍵，擁有兩條鏈接锅锨，這種結(jié)點(diǎn)被稱為2-結(jié)點(diǎn)必指；如果某個(gè)結(jié)點(diǎn)可以存儲兩個(gè)鍵，擁有3條鏈接，這種結(jié)點(diǎn)被稱為3-結(jié)點(diǎn)癞谒。

• 2-結(jié)點(diǎn)扯俱，左鏈接指向的2-3樹中的鍵都小于該結(jié)點(diǎn)，右鏈接指向的2-3樹中的鍵都大于該結(jié)點(diǎn)。
• 3-結(jié)點(diǎn)，左鏈接指向的2-3樹中的鍵都小于該結(jié)點(diǎn)尔当，中鏈接指向的2-3樹中的鍵都位于該結(jié)點(diǎn)的兩個(gè)鍵之間，右鏈接指向的2-3樹中的鍵都大于該結(jié)點(diǎn)。

我們規(guī)定简软，一個(gè)2-結(jié)點(diǎn)要么擁有兩個(gè)子結(jié)點(diǎn)建炫，要么沒有子結(jié)點(diǎn)据过；一個(gè)3-結(jié)點(diǎn)要么擁有三個(gè)子結(jié)點(diǎn)，要么沒有子結(jié)點(diǎn)鳞芙。這樣的保證使得2-3樹的所有葉子結(jié)點(diǎn)位于同一層，也就是說所有葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度是一樣的，達(dá)到了所謂的完美平衡壕鹉。如下是一棵2-3樹

2-3樹的查找

2-3樹的查找和標(biāo)準(zhǔn)的二叉查找樹如出一轍牍白，只是多了在中鏈接的遞歸查找狸涌。具體來說：先將要查找的key與2-3樹的根結(jié)點(diǎn)比較，若和根結(jié)點(diǎn)中任意一個(gè)鍵相等則查找命中惶楼；否則，若key小于根結(jié)點(diǎn)中的較小鍵，在根結(jié)點(diǎn)的左子樹中遞歸查找歼捐；若key大于根結(jié)點(diǎn)中的較大者何陆，在根結(jié)點(diǎn)的右子樹中遞歸查找；若key在根結(jié)點(diǎn)兩個(gè)鍵的之間贷盲，則在根結(jié)點(diǎn)的中子樹中遞歸查找...下面分別展示了查找成功和失敗的軌跡。

2-3樹的插入

插入操作剥扣，肯定是查找未命中時(shí)巩剖。如果未命中的查找結(jié)束于一個(gè)2-結(jié)點(diǎn)，直接插入到該結(jié)點(diǎn)中钠怯，使其變成3-結(jié)點(diǎn)就好了佳魔。可如果查找結(jié)束于一個(gè)3-結(jié)點(diǎn)該怎么辦呢晦炊？2-3樹中并不允許4-結(jié)點(diǎn)啊鞠鲜。

有幾種情況，我們一一來看断国。

向一棵只含有一個(gè)3-結(jié)點(diǎn)的樹中插入新鍵

考慮一種最簡單的情況贤姆，一棵2-3樹中只有一個(gè)3-結(jié)點(diǎn)，此時(shí)插入一個(gè)新鍵稳衬。我們可以這樣做：先讓該鍵暫時(shí)存放于3-結(jié)點(diǎn)中霞捡，隨即將3個(gè)鍵中排名中間的鍵向上移（因此樹的高度增加了1），左邊的鍵成為上移鍵的左子結(jié)點(diǎn)薄疚，右邊的鍵成為上移鍵的右子樹弄砍，最后這個(gè)臨時(shí)的4-結(jié)點(diǎn)被分解成了3個(gè)2-結(jié)點(diǎn)。如下圖

向一個(gè)父結(jié)點(diǎn)是2-結(jié)點(diǎn)的3-結(jié)點(diǎn)中插入新鍵

如果樹比較復(fù)雜输涕，其實(shí)也沒關(guān)系音婶，和上面的簡單情況是同樣的處理方法。

如圖莱坎，排名中間的鍵X上移和R合并稱為了3-結(jié)點(diǎn)衣式。

向一個(gè)父結(jié)點(diǎn)是3-結(jié)點(diǎn)的3-結(jié)點(diǎn)插入新鍵

一樣的處理方法，無非就是再向上移檐什，如下左圖所示碴卧，在樹的底部插入D，將排名中間的C上移和EJ合并成4-結(jié)點(diǎn)乃正，繼續(xù)將排名中間的E上移住册，和根結(jié)點(diǎn)M合并成為3-結(jié)點(diǎn)。

如果到根結(jié)點(diǎn)還是4-結(jié)點(diǎn)呢瓮具，那就按照第一種情況處理——向一棵只含有3-結(jié)點(diǎn)的樹中插入新鍵荧飞，只需將4-結(jié)點(diǎn)分解成3個(gè)2-結(jié)點(diǎn)即可凡人，同時(shí)樹的高度增加了1。

局部變換與全局性質(zhì)

4-結(jié)點(diǎn)的分解是局部的：除了相關(guān)的結(jié)點(diǎn)和鏈接之外叹阔，樹的其他所有結(jié)點(diǎn)的狀態(tài)都不會(huì)被修改挠轴。即每次變換，不是整棵樹都變化了耳幢。下圖能比較直觀理解這種變換的局部性岸晦。

這些局部變換不會(huì)影響樹的全局有序性和平衡性：任意葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度都是相等的。

2-3樹的刪除

2-3樹的插入分好幾種情況睛藻，但還算不難理解启上。刪除操作的話就更難了。這里只介紹簡單的情況店印，刪除最小最大鍵碧绞。刪除任意鍵在紅黑樹中會(huì)有介紹。

如果要?jiǎng)h除的結(jié)點(diǎn)是一個(gè)3-結(jié)點(diǎn)吱窝，最簡單，直接刪除掉迫靖，因此3-結(jié)點(diǎn)變成了2結(jié)點(diǎn)院峡。

如果刪除的是一個(gè)2-結(jié)點(diǎn)呢？

刪除最小鍵

先看最小鍵的刪除系宜。如果當(dāng)前要被刪除的結(jié)點(diǎn)是一個(gè)2-結(jié)點(diǎn)照激，那就想辦法把它變成一個(gè)3-結(jié)點(diǎn)或者4-結(jié)點(diǎn)，然后直接刪除即可盹牧。

如上圖中的5種變換：

• 當(dāng)前的結(jié)點(diǎn)左子結(jié)點(diǎn)和右子結(jié)點(diǎn)都是2-結(jié)點(diǎn)俩垃，見圖中第1、4種變換汰寓，它們是將這三個(gè)結(jié)點(diǎn)合并成了一個(gè)4-結(jié)點(diǎn)口柳。
• 當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)是2-結(jié)點(diǎn)，但是右子結(jié)點(diǎn)不是2-結(jié)點(diǎn)有滑。見圖中第2跃闹、3種情況，它們的做法是從左子結(jié)點(diǎn)的兄弟結(jié)點(diǎn)中借一個(gè)最小的鍵到當(dāng)前結(jié)點(diǎn)（它們的父結(jié)點(diǎn)）毛好，再將當(dāng)前結(jié)點(diǎn)中最小的鍵移動(dòng)到左子結(jié)點(diǎn)中望艺。
• 一旦要被刪除結(jié)點(diǎn)不是2-結(jié)點(diǎn)就可以執(zhí)行刪除了，這保證了2-3樹的有序性和平衡性肌访。見圖中第5種變換找默。

刪除最大鍵

和刪除最小鍵的處理方法類似。如下圖

也是當(dāng)前結(jié)點(diǎn)的左右子結(jié)點(diǎn)都是2-結(jié)點(diǎn)就將這三個(gè)結(jié)點(diǎn)合并成4-結(jié)點(diǎn)吼驶，如圖左邊的combine siblings惩激；當(dāng)右子結(jié)點(diǎn)是2-結(jié)點(diǎn)店煞，左子結(jié)點(diǎn)不是2-結(jié)點(diǎn)，那么從右子結(jié)點(diǎn)的兄弟結(jié)點(diǎn)中借一個(gè)最大結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)（它們的父結(jié)點(diǎn)）咧欣，然后將當(dāng)前結(jié)點(diǎn)中最大的鍵移動(dòng)到右子結(jié)點(diǎn)浅缸，如圖中borrow from siblings。

紅黑樹

2-3樹理解不難魄咕，而且和平衡二叉樹比討論情況有所減少衩椒。而接下來介紹的左傾紅黑樹（Left leaning Red-Black Tree）就是為了用簡單的方法實(shí)現(xiàn)2-3樹，進(jìn)一步減少討論的情況和代碼量哮兰。2-3樹中2-結(jié)點(diǎn)就是標(biāo)準(zhǔn)二叉查找樹中的結(jié)點(diǎn)宪郊，為了表達(dá)3-結(jié)點(diǎn)需要附加額外的信息网杆。這里講的紅黑樹可能有別于常規(guī)的定義方法。接下來你會(huì)看到，我們在結(jié)點(diǎn)與結(jié)點(diǎn)的鏈接上著色（而不是著色結(jié)點(diǎn)）匀油。左傾紅黑樹必須滿足以下幾點(diǎn)：

• 紅鏈接均是紅鏈接，即不存在有某個(gè)右鏈接是紅色的茵宪，這可以保證更少的討論情況從而減少代碼量乖杠。
• 沒有任何一個(gè)結(jié)點(diǎn)同時(shí)和兩條紅鏈接相連，也就是不允許連續(xù)的兩條紅鏈接窘哈、或者一個(gè)結(jié)點(diǎn)的左右鏈接都是紅色吹榴。
• 該樹是完美黑色平衡的，也就是說任意葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑上黑色鏈接數(shù)量相同滚婉。
• 根結(jié)點(diǎn)始終是黑色的图筹。

我們將兩個(gè)用紅色鏈接相連的結(jié)點(diǎn)表示為一個(gè)3-結(jié)點(diǎn)。

如圖让腹，加粗的黑線（沒找到彩圖...）是被著色為紅色的鏈接远剩，a和b被紅鏈接相連，因此a骇窍、b其實(shí)是一個(gè)3-結(jié)點(diǎn)瓜晤。

上圖是個(gè)彩圖了...同樣的我們可以定義4-結(jié)點(diǎn)：某結(jié)點(diǎn)的左右鏈接都是紅的，和這兩條紅鏈接相連的三個(gè)結(jié)點(diǎn)就是一個(gè)4-結(jié)點(diǎn)腹纳，這里只是提一下活鹰，左傾紅黑樹不會(huì)用到4-結(jié)點(diǎn)。下面我們?nèi)绻岬健凹t黑樹”那它指代就是“左傾紅黑樹”只估。

因此我們完全可以用附帶了顏色信息的二叉查找樹來表示2-3樹志群。而且標(biāo)準(zhǔn)二叉查找樹中的get(Key key)方法無需修改直接就能用于左傾紅黑樹！容易知道蛔钙，紅黑樹既是二叉查找樹锌云，又是2-3樹。因此它結(jié)合了兩者的優(yōu)勢：二叉查找樹中高效的查找方法和2-3樹中高效的平衡插入算法吁脱。

看到一棵紅黑樹桑涎，如果將其直觀地表示成2-3樹呢彬向？我們只需將所有左鏈接畫平，并將與紅鏈接相連的結(jié)點(diǎn)合并成一個(gè)3-結(jié)點(diǎn)即可攻冷。如下所示娃胆，加粗的黑色鏈接是紅鏈接

之前一直說鏈接的紅黑，表達(dá)的是指向某個(gè)結(jié)點(diǎn)的鏈接的顏色等曼。

比如上圖中C里烦、E之間的鏈接是紅色的，這條鏈接指向C禁谦，因此這條鏈接的顏色是屬于結(jié)點(diǎn)C的胁黑，我們也可以簡單地說“（指向）C結(jié)點(diǎn)（的鏈接）是紅色的”；那么對于結(jié)點(diǎn)J州泊，指向它的鏈接顏色是黑的丧蘸。葉子結(jié)點(diǎn)也有左右鏈接，雖然它們都是空遥皂，約定（指向null的）空鏈接的顏色是黑色的力喷。如A的左子結(jié)點(diǎn)的鏈接顏色A.left.color = BLACK。哦對了演训，還有指向根結(jié)點(diǎn)的鏈接（雖然這么說很奇怪弟孟，因?yàn)槭聦?shí)上并沒有鏈接指向根結(jié)點(diǎn)，為了保持結(jié)點(diǎn)性質(zhì)的一致性仇祭，我們還是這么叫了），上面左傾紅黑樹的定義中有說到其顏色必須是黑色的颈畸，因?yàn)楦Y(jié)點(diǎn)的左孩子有可能是紅鏈接乌奇，如果根結(jié)點(diǎn)也是紅鏈接，就違反了定義的第二條——沒有任何一個(gè)結(jié)點(diǎn)同時(shí)和兩條紅鏈接相連眯娱〗该纾總之上面提到了一些約定，這些都是為了我們實(shí)現(xiàn)時(shí)更加方便徙缴，所以在代碼中要時(shí)刻保證這些約定试伙。

說了這么多，來試著用代碼實(shí)現(xiàn)吧于样。

package Chap8;

public class LLRB<Key, Value> {

    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private Node root;

    private class Node {
        private Key key;
        private Value value;
        private Node left, right;
        private int N; // 結(jié)點(diǎn)計(jì)數(shù)器疏叨，以該結(jié)點(diǎn)為根的子樹結(jié)點(diǎn)總數(shù)
        private boolean color; // 指向該結(jié)點(diǎn)的鏈接顏色

        public Node(Key key, Value value, int N, boolean color) {
            this.key = key;
            this.value = value;
            this.N = N;
            this.color = color;
        }
    }

    public boolean isRed(Node x) {
        // 約定空鏈接為黑色
        if (x == null) {
            return BLACK;
        } else {
            return x.color == RED;
        }
    }
}

先給出了左傾紅黑樹的基本實(shí)現(xiàn)，在標(biāo)準(zhǔn)二叉查找樹中新增了color域穿剖，表示指向該結(jié)點(diǎn)的鏈接顏色蚤蔓。對應(yīng)的isRed(Node x)判斷指向該結(jié)點(diǎn)的鏈接是不是紅色的，如果x == null表示這是條空鏈接糊余，出于之前的約定秀又，應(yīng)該返回黑色单寂。

旋轉(zhuǎn)

為了保證紅黑樹的特性——不存在右鏈接是紅色的、以及沒有任何一個(gè)結(jié)點(diǎn)同時(shí)和兩條紅鏈接相連吐辙，在對紅黑樹進(jìn)行操作時(shí)宣决，比如插入或者刪除，難免會(huì)出現(xiàn)紅色右鏈接或者連續(xù)的兩條紅鏈接昏苏，應(yīng)該確保每次操作完成之前這些情況已經(jīng)被修正尊沸。這種對鏈接顏色的修正靠的是一種稱為旋轉(zhuǎn)的操作完成的，和上述平衡樹中的旋轉(zhuǎn)操作基本類似捷雕，不過這里加入了對鏈接顏色信息的修正椒丧。

旋轉(zhuǎn)操作會(huì)改變紅鏈接的指向，比如一條紅色的右鏈接需要轉(zhuǎn)換為紅色的左鏈接救巷，這個(gè)操作被稱為左旋轉(zhuǎn)壶熏，右旋轉(zhuǎn)和左旋轉(zhuǎn)是對稱的。如下圖所示浦译。

上面兩張圖棒假，從紅色右鏈接變到紅色左鏈接，是左旋轉(zhuǎn)精盅。

上面兩張圖帽哑，從紅色左鏈接變到紅色右鏈接，是右旋轉(zhuǎn)叹俏。

旋轉(zhuǎn)操作也是局部的妻枕，只會(huì)影響旋轉(zhuǎn)相關(guān)的結(jié)點(diǎn)，樹中其他結(jié)點(diǎn)不受影響粘驰，而且旋轉(zhuǎn)操作不會(huì)破壞整棵樹的有序性和平衡性屡谐，如圖中小于a、位于a和b之間蝌数、大于b這些大小關(guān)系在旋轉(zhuǎn)前后沒有改變愕掏！

由圖可寫出旋轉(zhuǎn)操作的實(shí)現(xiàn)

private Node rotateLeft(Node h) {
    Node x = h.right; // 根結(jié)點(diǎn)的右子結(jié)點(diǎn)保存為x
    // 其實(shí)就是h和x互換位置
    h.right = x.left; // 根結(jié)點(diǎn)的右子結(jié)點(diǎn)的左孩子掛到根結(jié)點(diǎn)的右子結(jié)點(diǎn)上
    x.left = h; // 根結(jié)點(diǎn)掛到根結(jié)點(diǎn)右子結(jié)點(diǎn)的左子結(jié)點(diǎn)上
    x.color = h.color; // 原來h是什么顏色，換過去的x也應(yīng)該是什么顏色
    h.color = RED;     // 將紅色右鏈接變成紅色左鏈接顶伞，因此x是紅色的饵撑，h和x互換位置所以換過去的h也應(yīng)該是RED
    x.N = h.N;  // x的結(jié)點(diǎn)數(shù)和h保持一致
    h.N = size(h.left) + size(h.right) + 1; // 這里不能用原x.N賦值給h.N，因?yàn)樾D(zhuǎn)操作后原來x的子樹和現(xiàn)在h的子樹不一樣
    // 返回取代h位置的結(jié)點(diǎn)x唆貌，h = rotateLeft(Node h)就表示x取代了h
    return x;
}

private Node retateRight(Node h) {
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = RED; // x原來是紅色的
    x.N = h.N;
    h.N = size(h.left) + size(h.right) + 1;

    return x;
}

查找和插入

查找操作直接使用標(biāo)準(zhǔn)二叉查找樹的get方法滑潘，改都不用改的。

// 非遞歸get
public Value get(Key key) {
    Node cur = root;
    while (cur != null) {
        int cmp = key.compareTo(cur.key);
        if (cmp < 0) {
        cur = cur.left;
        } else if (cmp > 0) {
        cur = cur.right;
        } else {
        return cur.value;
        }
    }
  return null;
}

插入就稍微麻煩一點(diǎn)了锨咙。由于紅黑樹也是2-3樹众羡，所以插入情況請參考上述對2-3樹插入的探討。

向2-結(jié)點(diǎn)中插入新鍵

這是最簡單的情況了，按照2-3樹插入的思路粱侣，直接使這個(gè)2-3結(jié)點(diǎn)變成3-結(jié)點(diǎn)羊壹。對應(yīng)到紅黑樹中，如果新鍵小于父結(jié)點(diǎn)齐婴，只需將該鍵掛到父結(jié)點(diǎn)的左邊且鏈接是紅色油猫；如果新鍵大于父結(jié)點(diǎn)，只需將該鍵掛到老鍵的右邊且鏈接是紅色柠偶，但這就違反了紅黑樹的特性（右鏈接不能是紅色）情妖，因此上面的旋轉(zhuǎn)操作就派上用場了，只需對其進(jìn)行左旋轉(zhuǎn)即可诱担。

向3-結(jié)點(diǎn)中插入一個(gè)新鍵

如果樹只由一個(gè)3-結(jié)點(diǎn)構(gòu)成毡证。插入有三種情況，分別是新鍵最大插入到結(jié)點(diǎn)右邊蔫仙、新鍵最小插入到結(jié)點(diǎn)的左邊料睛、新鍵位于兩者之間插入到中間。

回憶2-3樹中往3-結(jié)點(diǎn)中插入的情況摇邦，我們的做法是先將新鍵存在一個(gè)臨時(shí)的4-結(jié)點(diǎn)中恤煞，然后將排名中間的鍵往上移，4-結(jié)點(diǎn)分解成了3個(gè)2-結(jié)點(diǎn)施籍，同時(shí)樹高增加1居扒。這在紅黑樹中很好實(shí)現(xiàn)，4-結(jié)點(diǎn)也就是一個(gè)結(jié)點(diǎn)擁有兩條紅色鏈接丑慎，至于排名中間的鍵上移喜喂，只需將鏈接的顏色反轉(zhuǎn)即可。如下是結(jié)點(diǎn)鏈接反色的示意圖

左圖是一個(gè)4-結(jié)點(diǎn)竿裂，通過將h的兩個(gè)子結(jié)點(diǎn)的顏色變成BLACK玉吁、將h變成RED就達(dá)到了上移的目的，而且4-結(jié)點(diǎn)正確地被分解成了三個(gè)2-結(jié)點(diǎn)铛绰，h變紅正好可以和上一層的2-結(jié)點(diǎn)合并成3-結(jié)點(diǎn)诈茧；或者和3-結(jié)點(diǎn)合并成4-結(jié)點(diǎn)后繼續(xù)執(zhí)行分解操作产喉，如此這般一直到遇到一個(gè)2-結(jié)點(diǎn)為止捂掰。這完全符合2-3樹中的插入操作！反轉(zhuǎn)結(jié)點(diǎn)鏈接顏色的代碼非常簡單曾沈，但是又相當(dāng)重要这嚣，我們將看到，向3-結(jié)點(diǎn)中插入的種種情況最終都會(huì)轉(zhuǎn)換成上面的情況塞俱。

private void flipColors(Node h) {
    h.color = !h.color;
    h.left.color = !h.left.color;
    h.right.color = !h.right.color;
}

向一棵只有3-結(jié)點(diǎn)的樹中插入新鍵分以下三種情況：

• 新鍵大于3-結(jié)點(diǎn)中的兩個(gè)鍵姐帚，那么直接連接到3-結(jié)點(diǎn)較大鍵的右鏈接且顏色為紅色。此時(shí)直接調(diào)用flipColors方法即可障涯；
• 新鍵小于3-結(jié)點(diǎn)中的兩個(gè)鍵罐旗，那么該鍵會(huì)連接到3-結(jié)點(diǎn)較小鍵的的左鏈接且顏色為紅色膳汪，此時(shí)出現(xiàn)了連續(xù)兩條的紅鏈接，是不允許的九秀，通過右旋轉(zhuǎn)變成了情況1遗嗽，再調(diào)用flipColors
• 新鍵位于3-結(jié)點(diǎn)的兩個(gè)鍵之間，那么該鍵會(huì)鏈接到3-結(jié)點(diǎn)較小鍵的右鏈接上且顏色為紅色鼓蜒，此時(shí)出現(xiàn)紅色右鏈接痹换，是不允許的，通過左旋轉(zhuǎn)修正后變成了情況2都弹，于是右旋轉(zhuǎn)娇豫，變成情況1，最后調(diào)用flipColors.

如果是在樹底部的某個(gè)3-結(jié)點(diǎn)插入新鍵畅厢，有可能包含以上全部三種情況冯痢！

如果你回頭看各種情況的插入操作，我們總是用紅鏈接將新結(jié)點(diǎn)和它的父結(jié)點(diǎn)相連或详。這么做是為了符合2-3樹中各種插入情況系羞。而且因?yàn)槿N情況里有些情況會(huì)進(jìn)行其他情況的處理，在實(shí)現(xiàn)時(shí)一定要注意處理的順序霸琴。比如情況3里包含了情況2和情況1的處理椒振，情況2中包含了情況1的處理，那么在處理時(shí)應(yīng)該先判斷情況3梧乘，再判斷情況2澎迎，最后判斷情況1。

總結(jié)一下：

• 如果右子結(jié)點(diǎn)是紅色的而左子結(jié)點(diǎn)是黑色的选调，進(jìn)行左旋轉(zhuǎn)夹供，目的是將紅色右鏈接變成紅色左鏈接。
• 如果右子結(jié)點(diǎn)是紅色的而左子結(jié)點(diǎn)是黑色的仁堪，進(jìn)行左旋轉(zhuǎn)哮洽。
• 如果左右子結(jié)點(diǎn)均為紅色，進(jìn)行顏色反轉(zhuǎn)弦聂。

上面的表述按順序翻譯成代碼就可以實(shí)現(xiàn)put方法了鸟辅。

它們互相轉(zhuǎn)換的關(guān)系如下圖所示

對了還有一點(diǎn)，顏色反轉(zhuǎn)有可能導(dǎo)致根結(jié)點(diǎn)的顏色也變成紅色莺葫，但是我們約定根結(jié)點(diǎn)總是黑色的匪凉。所以每次put操作后，記得手動(dòng)將root.color置為黑色捺檬。

public void put(Key key, Value value) {
    root = put(root, key,value);
    // 保證根結(jié)點(diǎn)始終為黑色
    root.color = BLACK;
}

private Node put(Node h, Key key, Value value) {
    if (h == null) {
        return new Node(key, value, 1, RED);
    }
    int cmp = key.compareTo(h.key);
    if (cmp < 0) {
        h.left = put(h.left, key, value);
    } else if (cmp > 0){
        h.right = put(h.right, key, value);
    } else {
        h.value = value;
    }

    /*
     下面連續(xù)三個(gè)判斷是和標(biāo)準(zhǔn)二叉查找樹put方法不同的地方再层，目的是修正紅鏈接
     */
  // 如果右子結(jié)點(diǎn)是紅色的而左子結(jié)點(diǎn)是黑色的，進(jìn)行左旋轉(zhuǎn)
  // 之后返回值賦給h是讓x取代原h(huán)的位置，不可少
    if (isRed(h.right) && !isRed(h.left)) {
        h = rotateLeft(h);
    }
    // 如果左子結(jié)點(diǎn)是紅色的且左子結(jié)點(diǎn)的左子節(jié)點(diǎn)是紅色的聂受，進(jìn)行右旋轉(zhuǎn)
    if (isRed(h.left) && isRed(h.left.left)) {
        h = rotateRight(h);
    }
    // 如果左右子結(jié)點(diǎn)均為紅色蒿秦，進(jìn)行顏色反轉(zhuǎn)
    if (isRed(h.left) && isRed(h.right)) {
        flipColors(h);
    }

    h.N = size(h.left) + size(h.right) + 1;
    return h;
}

刪除

紅黑樹的刪除和上面提到的2-3樹的刪除是一致的。對照著上述2-3樹刪除的各種情況來實(shí)現(xiàn)紅黑樹的刪除蛋济，理解起來就不那么復(fù)雜了渤早。

還是先從簡單的入手。

刪除最小鍵

如果要?jiǎng)h除的是一個(gè)3-結(jié)點(diǎn)瘫俊，那么直接刪除鹊杖。如果要?jiǎng)h除的是一個(gè)2-結(jié)點(diǎn)，說明h.left == BLACK && h.left.left ==BLACK扛芽，逆向思考我們保證h.left或h.left.left任意一個(gè)是RED就說明要?jiǎng)h除的結(jié)點(diǎn)是一個(gè)3-結(jié)點(diǎn)骂蓖，之后再刪除就簡單了。

如圖當(dāng)前結(jié)點(diǎn)B川尖，B.left = BLACK && B.left.left = BLACK登下，此時(shí)只需flipColor將ABC合并成4-結(jié)點(diǎn)即可執(zhí)行刪除。

反轉(zhuǎn)顏色后使得h.left = RED

還有種更難的情況叮喳，在滿足上述兩個(gè)結(jié)點(diǎn)鏈接都是黑色的情況下被芳，如果h.right.left = RED呢？如下馍悟，當(dāng)前結(jié)點(diǎn)h = E

按照2-3樹刪除方法畔濒，應(yīng)該從A的兄弟結(jié)點(diǎn)借一個(gè)最小鍵到當(dāng)前結(jié)點(diǎn)，再將當(dāng)前結(jié)點(diǎn)中最小鍵移到A中合并成一個(gè)3-結(jié)點(diǎn)锣咒，再執(zhí)行刪除侵状。

經(jīng)過一系列的變換，從圖中可看出先是rotateRight(h.right)毅整，再rotateLeft(h)趣兄，然后filpColors(h)最終使得h.left.left = RED。

其他情況如當(dāng)前結(jié)點(diǎn)為D悼嫉，D.left.left = RED艇潭，BC中可以直接刪除B∠访铮或者如果遞歸到了C是當(dāng)前結(jié)點(diǎn)蹋凝，C.left = RED也能直接刪除而無需其他操作。

在遞歸自頂而下的過程中辛臊，我們對若干結(jié)點(diǎn)都進(jìn)行了顏色反轉(zhuǎn)及旋轉(zhuǎn)操作仙粱，這些操作都可能影響數(shù)的有序性和平衡性房交，所以在返回的自下而上的過程中彻舰，要對樹進(jìn)行修正，修正的方法和put方法中的修正方法完全一樣，抽取出來作為一個(gè)方法刃唤，如下

private Node fixUp(Node h) {
    if (isRed(h.right) && !isRed(h.left)) {
        h = rotateLeft(h);
    }
    // 如果右子結(jié)點(diǎn)是紅色的而左子結(jié)點(diǎn)是黑色的隔心，進(jìn)行左旋轉(zhuǎn)
    if (isRed(h.left) && isRed(h.left.left)) {
        h = rotateRight(h);
    }
    // 如果左右子結(jié)點(diǎn)均為紅色，進(jìn)行顏色反轉(zhuǎn)
    if (isRed(h.left) && isRed(h.right)) {
        flipColors(h);
    }

    h.N = size(h.left) + size(h.right) + 1;
    return h;
}

有了上面講解的基礎(chǔ)尚胞，實(shí)現(xiàn)deleteMin就不難了硬霍。

private Node moveRedLeft(Node h) {
    // 當(dāng)此方法被調(diào)用時(shí)，h是紅色的笼裳，h.left和h.left.left都是黑色的
    // 整個(gè)方法結(jié)束后h.left或者h(yuǎn).left.left其中之一被變成RED
    flipColors(h);
    if (isRed(h.right.left)) {
        h.right = rotateRight(h.right);
        h = rotateLeft(h);
        flipColors(h);
    }
    return h;
}

public void deleteMin(Key key) {
    // 這里將root設(shè)置為紅色是為了和moveRedLeft里的處理一致
    // 即當(dāng)前結(jié)點(diǎn)h是紅色的唯卖，其兩個(gè)子結(jié)點(diǎn)都是黑色的，在反色后躬柬，當(dāng)前結(jié)點(diǎn)h變成黑色拜轨，而它的兩個(gè)子結(jié)點(diǎn)變成紅色
    if (!isRed(root.left) && !isRed(root.right)) {
        root.color = RED;
    }
    root = deleteMin(root, key);
    // 根結(jié)點(diǎn)只要不為空，刪除操作后保持始終是黑色的
    if (!isEmpty()) {
        root.color = BLACK;
    }
}

private Node deleteMin(Node h, Key key) {
    if (h.left == null) {
    // 不像標(biāo)準(zhǔn)二叉查找樹那樣返回h.right, 因?yàn)閜ut方法就決定了h.left和h.right要么同時(shí)為空要么同時(shí)不為空
        return null;
    }
    // 合并成4-結(jié)點(diǎn)或者從兄弟結(jié)點(diǎn)中借一個(gè)過來
    if (!isRed(h.left) && !isRed(h.left.left)) {
        h = moveRedLeft(h);
    }

    h.left = deleteMin(h.left, key);
    // 返回時(shí)允青，自下而上地修正路徑上的結(jié)點(diǎn)
    return fixUp(h);
}

看個(gè)刪除最小鍵的例子橄碾。

刪除最大鍵

刪除最大鍵和刪除最小鍵是對稱的，但有些不一樣颠锉。刪除最小鍵在自頂向下的過程中保證h.left或者h.left.left為紅色法牲，類似地刪除最大鍵在自頂向下的過程中要保證h.right或者h.right.right為紅色，但是我們定義紅黑樹是左傾的琼掠！這意味著紅色鏈接默認(rèn)就是左鏈接拒垃，因此要使用刪除最小鍵的方法來達(dá)到刪除最大鍵的目的，必須在處理之前將紅色鏈接變成右鏈接（右旋轉(zhuǎn)操作）瓷蛙，之后就和刪除最小鍵的處理對稱了恶复。

當(dāng)前結(jié)點(diǎn)h.right = BLACK && h.right.left = BLACK，反轉(zhuǎn)顏色速挑。

滿足上述情況的同時(shí)如果h.left.left = RED谤牡，說明需要從兄弟結(jié)點(diǎn)中借一個(gè)鍵過來，為此還要進(jìn)行下面的變換姥宝，最后h.right.right變成紅色翅萤。

實(shí)現(xiàn)如下

private Node moveRedRight(Node h) {
    flipColors(h);
    // 從兄弟結(jié)點(diǎn)借一個(gè)鍵
    if (isRed(h.left.left)) {
        h =rotateRight(h);
        flipColors(h);
    }
    return h;
}

public void deleteMax(Key key) {
    if (!isRed(root.left) && !isRed(root.right)) {
        root.color = RED;
    }
    root = deleteMax(root, key);
    if (!isEmpty()) {
        root.color = BLACK;
    }
}

private Node deleteMax(Node h, Key key) {
    // 為了和deleteMin對稱處理，先將紅色左鏈接轉(zhuǎn)換成紅色右鏈接
    // 轉(zhuǎn)換為紅色右鏈接是最先處理的腊满！
    if (isRed(h.left)) {
        h = rotateRight(h);
    }
    // 這個(gè)判斷不能再上句之前套么，因?yàn)榭赡苄D(zhuǎn)前h.right是null，旋轉(zhuǎn)后可就不是null了
    if (h.right == null) {
        return null;
    }
    // 這里條件中不是h.right.right碳蛋，因?yàn)?-結(jié)點(diǎn)是左鏈接表示的
    if (!isRed(h.right) && !isRed(h.right.left)) {
        h = moveRedRight(h);
    }
    h.right = deleteMax(h.right, key);
    return fixUp(h);
}

來看兩個(gè)刪除最大鍵的例子胚泌，其中第一個(gè)例子刪除后就已經(jīng)平衡，無需修正肃弟；第二個(gè)例子中在自下而上的過程中有修正玷室。

上面的例子無修正零蓉。

上面的例子有修正。

刪除任意鍵

最難的方法穷缤。我自己也沒太明白就來介紹這個(gè)方法可能不太妥當(dāng)敌蜂，只好盡力說個(gè)大概。至于代碼中的控制流程（if-else的順序）為什么是那樣津肛，本人也不理解章喉。

public void delete(Key key) {
    if (!contains(key)) {
        return;
    }

    if (!isRed(root.left) && !isRed(root.right)) {
        root.color = RED;
    }

    root = delete(root, key);

    if (!isEmpty()) {
        root.color = BLACK;
    }
}

private Node delete(Node h, Key key) {
    if (key.compareTo(h.key) < 0) {
        if (!isRed(h.left) && !isRed(h.left.left)) {
        h = moveRedLeft(h);
        }
        h.left = delete(h.left, key);
    } else { // 要么在根結(jié)點(diǎn)或者右子樹，兩種情況包含在一起了
    // 要在右子樹處理身坐，所以確保是紅色右鏈接
        if (isRed(h.left)) {
        h = rotateRight(h);
        }
      
        // 要?jiǎng)h除的結(jié)點(diǎn)在樹底
        if (key.compareTo(h.key) == 0 && (h.right == null)) {
        return null;
        }
        // 這個(gè)判斷必須在上個(gè)判斷之后秸脱，因?yàn)榇_保h.right不為空后才能調(diào)用h.right.left
        if (!isRed(h.right) && !isRed(h.right.left)) {
        h = moveRedRight(h);
        }
        // 要?jiǎng)h除的鍵不在樹底, 用它的后繼結(jié)點(diǎn)替代它后，刪除后繼結(jié)點(diǎn)
        if (key.compareTo(h.key) == 0) {
            Node x = min(h.right);
            h.key = x.key;
            h.value = x.value;
            h.right = deleteMin(h.right);
        // 沒有相等的鍵部蛇，在右子樹中遞歸
        } else {
        h.right = delete(h.right, key);
        }
    }
    // 自下而上的結(jié)點(diǎn)修正
    return fixUp(h);
}

公有delete方法中還是延續(xù)了deleteMin/deleteMax那一套撞反，只是增加了判斷——如果key不在紅黑樹中，不進(jìn)行任何操作直接返回√禄ǎ現(xiàn)在看私有方法：

大概的思路是：從root開始查找遏片，如果被刪除的鍵比根結(jié)點(diǎn)小，遞歸地在左子樹中查找撮竿；否則吮便，被刪除的鍵和根結(jié)點(diǎn)相同或者比根結(jié)點(diǎn)大，這個(gè)條件分支是最難的地方幢踏。**進(jìn)入else分支后髓需，不管是不是和當(dāng)前結(jié)點(diǎn)的鍵相同，首先就把紅色左鏈接轉(zhuǎn)換成紅色右鏈接房蝉，這之后才判斷當(dāng)前結(jié)點(diǎn)的鍵是否和被刪除結(jié)點(diǎn)的鍵相同僚匆。 **被刪除的結(jié)點(diǎn)位置有兩種情況，在樹底和不在樹底搭幻，不在樹底時(shí)需要用它的后繼結(jié)點(diǎn)替代更新被刪除結(jié)點(diǎn)咧擂，之后再刪除后繼結(jié)點(diǎn)。兩種情況下鍵都不相同的話檀蹋，就遞歸地在右子樹中查找松申。最后記得要自下而上地修正路徑上各個(gè)結(jié)點(diǎn)，保證刪除之后樹的有序性和平衡性俯逾。

看一個(gè)被刪除的鍵不在樹底的例子贸桶，如下圖刪除D。用D的后繼結(jié)點(diǎn)E替代了D的位置桌肴，之后刪除了E皇筛，最后修正結(jié)點(diǎn)顏色。

代碼中把“被刪除鍵和當(dāng)前鍵相同”坠七、“比當(dāng)前鍵大”這兩種情況合并在一起討論了水醋，我嘗試按照通常的思路旗笔，將這兩種情況分開，即else if (key.compareTo(h.key) == 0)和else > 0离例；或者將if (!isRed(h.right) && !isRed(h.right.left))這個(gè)判斷放到最后一個(gè)else里面，結(jié)果在進(jìn)行了幾次結(jié)點(diǎn)刪除后都會(huì)出錯(cuò)悉稠。

按照上面的控制流程宫蛆，執(zhí)行刪除就不會(huì)出錯(cuò)，不過如果你稍微改變下if-else語句的順序的猛，在若干次刪除操作后就可能出現(xiàn)錯(cuò)誤——多半是樹的平衡性被破壞了耀盗。

其他API

像min()/max()、select卦尊、rank叛拷、floor、ceiling和范圍查找等相關(guān)方法岂却，不作任何修改忿薇，直接套用標(biāo)準(zhǔn)二叉查找樹的對應(yīng)方法即可。

by @sunhaiyu

2017.10.21