數(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)的左子樹深度減右子樹深度的值。易知，對(duì)于一棵平衡二叉樹，每個(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ù)），對(duì)結(jié)點(diǎn)3進(jìn)行右旋轉(zhuǎn)修正成上圖2的樣子。

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

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

接下來(lái)看看這個(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)的左孩子的左子樹上插入，對(duì)根結(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)。調(diào)用rotateRight
• 在根結(jié)點(diǎn)的右孩子的右子樹上插入，對(duì)根結(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)。調(diào)用rotateLeft
• 在根結(jié)點(diǎn)的左孩子的右子樹上插入，先對(duì)根結(jié)點(diǎn)的左孩子進(jìn)行左旋轉(zhuǎn)，再對(duì)根結(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)。調(diào)用rotateLeft(h.left);rotateRight(h);
• 在根結(jié)點(diǎn)的右孩子的左子樹上插入，先對(duì)根結(jié)點(diǎn)的右孩子進(jìn)行右旋轉(zhuǎn)，再對(duì)根結(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)。調(diào)用rotateRight(h.right);rotateLeft(h);

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

2-3樹介紹

為了保證查找樹的平衡性，我們?cè)试S樹中一個(gè)結(jié)點(diǎn)保存多個(gè)鍵 。標(biāo)準(zhǔn)二叉查找樹中的結(jié)點(diǎn)只能保存一個(gè)鍵，擁有兩條鏈接，這種結(jié)點(diǎn)被稱為2-結(jié)點(diǎn)；如果某個(gè)結(jié)點(diǎn)可以存儲(chǔ)兩個(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)的路徑長(zhǎng)度是一樣的，達(dá)到了所謂的完美平衡。如下是一棵2-3樹

2-3樹的查找

2-3樹的查找和標(biāo)準(zhǔn)的二叉查找樹如出一轍，只是多了在中鏈接的遞歸查找。具體來(lái)說：先將要查找的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)就好了?？扇绻檎医Y(jié)束于一個(gè)3-結(jié)點(diǎn)該怎么辦呢？2-3樹中并不允許4-結(jié)點(diǎn)啊。

有幾種情況，我們一一來(lái)看。

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

考慮一種最簡(jiǎ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)系，和上面的簡(jiǎn)單情況是同樣的處理方法。

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

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

一樣的處理方法，無(wú)非就是再向上移，如下左圖所示，在樹的底部插入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)的路徑長(zhǎng)度都是相等的。

2-3樹的刪除

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

如果要?jiǎng)h除的結(jié)點(diǎn)是一個(gè)3-結(jié)點(diǎn)，最簡(jiǎ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樹理解不難，而且和平衡二叉樹比討論情況有所減少。而接下來(lái)介紹的左傾紅黑樹（Left leaning Red-Black Tree）就是為了用簡(jiǎn)單的方法實(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ī)的定義方法。接下來(lái)你會(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黑樹”那它指代就是“左傾紅黑樹”。

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

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

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

比如上圖中C、E之間的鏈接是紅色的，這條鏈接指向C，因此這條鏈接的顏色是屬于結(jié)點(diǎn)C的，我們也可以簡(jiǎn)單地說“（指向）C結(jié)點(diǎn)（的鏈接）是紅色的”；那么對(duì)于結(jié)點(diǎn)J，指向它的鏈接顏色是黑的。葉子結(jié)點(diǎn)也有左右鏈接，雖然它們都是空，約定（指向null的）空鏈接的顏色是黑色的。如A的左子結(jié)點(diǎn)的鏈接顏色A.left.color = BLACK。哦對(duì)了，還有指向根結(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í)和兩條紅鏈接相連?？傊厦嫣岬搅艘恍┘s定，這些都是為了我們實(shí)現(xiàn)時(shí)更加方便，所以在代碼中要時(shí)刻保證這些約定。

說了這么多，來(lái)試著用代碼實(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)的鏈接顏色。對(duì)應(yīng)的isRed(Node x)判斷指向該結(jié)點(diǎn)的鏈接是不是紅色的，如果x == null表示這是條空鏈接，出于之前的約定，應(yīng)該返回黑色。

旋轉(zhuǎn)

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

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

上面兩張圖，從紅色右鏈接變到紅色左鏈接，是左旋轉(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; // 原來(lái)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)操作后原來(lái)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原來(lái)是紅色的
    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樹，所以插入情況請(qǐng)參考上述對(duì)2-3樹插入的探討。

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

這是最簡(jiǎn)單的情況了，按照2-3樹插入的思路，直接使這個(gè)2-3結(jié)點(diǎn)變成3-結(jié)點(diǎn)。對(duì)應(yīng)到紅黑樹中，如果新鍵小于父結(jié)點(diǎn)，只需將該鍵掛到父結(jié)點(diǎn)的左邊且鏈接是紅色；如果新鍵大于父結(jié)點(diǎn)，只需將該鍵掛到老鍵的右邊且鏈接是紅色，但這就違反了紅黑樹的特性（右鏈接不能是紅色），因此上面的旋轉(zhuǎn)操作就派上用場(chǎng)了，只需對(duì)其進(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)鏈接顏色的代碼非常簡(jiǎ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)系如下圖所示

對(duì)了還有一點(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樹的刪除是一致的。對(duì)照著上述2-3樹刪除的各種情況來(lái)實(shí)現(xiàn)紅黑樹的刪除，理解起來(lái)就不那么復(fù)雜了。

還是先從簡(jiǎn)單的入手。

刪除最小鍵

如果要?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)，之后再刪除就簡(jiǎ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?；蛘呷绻f歸到了C是當(dāng)前結(jié)點(diǎn)，C.left = RED也能直接刪除而無(wú)需其他操作。

在遞歸自頂而下的過程中，我們對(duì)若干結(jié)點(diǎn)都進(jìn)行了顏色反轉(zhuǎn)及旋轉(zhuǎn)操作，這些操作都可能影響數(shù)的有序性和平衡性，所以在返回的自下而上的過程中，要對(duì)樹進(jìn)行修正，修正的方法和put方法中的修正方法完全一樣，抽取出來(lái)作為一個(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è)過來(lái)
    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è)刪除最小鍵的例子。

刪除最大鍵

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

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

滿足上述情況的同時(shí)如果h.left.left = RED，說明需要從兄弟結(jié)點(diǎn)中借一個(gè)鍵過來(lái)，為此還要進(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對(duì)稱處理，先將紅色左鏈接轉(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);
}

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

上面的例子無(wú)修正。

上面的例子有修正。

刪除任意鍵

最難的方法。我自己也沒太明白就來(lái)介紹這個(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語(yǔ)句的順序，在若干次刪除操作后就可能出現(xiàn)錯(cuò)誤——多半是樹的平衡性被破壞了。

其他API

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

by @sunhaiyu

2017.10.21