之前講的二叉查找樹(shù)在最壞情況下性能還是很低的。平衡查找樹(shù)能夠保證無(wú)論如何構(gòu)造它，它的運(yùn)行時(shí)間都是對(duì)數(shù)級(jí)別。在一棵含有 N 個(gè)結(jié)點(diǎn)的樹(shù)中，我們希望樹(shù)高為 ~lgN，這樣我們就能保證所有查找都能在 ~lgN 次比較內(nèi)結(jié)束，就和二分查找一樣。但是，在動(dòng)態(tài)插入中保證樹(shù)的完美平衡的代價(jià)太高。我們稍微降低完美平衡的要求，學(xué)習(xí)一種能夠保證符號(hào)表 API 中所有操作均能在對(duì)數(shù)時(shí)間內(nèi)完成的數(shù)據(jù)結(jié)構(gòu)。

1. 2-3查找樹(shù)

為了保證查找樹(shù)的平衡性，我們需要一些靈活性，因此我們?cè)试S樹(shù)中的一個(gè)結(jié)點(diǎn)保存多個(gè)鍵。一棵標(biāo)準(zhǔn)的二叉查找樹(shù)中的結(jié)點(diǎn)稱為 2- 結(jié)點(diǎn)，含有一個(gè)鍵和兩條連接；將含有兩個(gè)鍵和三條連接的結(jié)點(diǎn)稱為 3- 結(jié)點(diǎn)（左連接指向的 2-3 樹(shù)中的鍵都小于該結(jié)點(diǎn)，中連接指向的 2-3 樹(shù)種中的鍵都位于該結(jié)點(diǎn)的兩個(gè)鍵之間，右鏈接指向的 2-3 樹(shù)中的鍵都大于該結(jié)點(diǎn)）。

一棵完美平衡的 2-3 查找樹(shù)中的所有空連接到根結(jié)點(diǎn)的距離都應(yīng)該事相同的。簡(jiǎn)潔起見(jiàn)，這里用 2-3 樹(shù)指代一棵完美平衡的 2-3 查找樹(shù)（在其他情況下這個(gè)次表示一種更一般的結(jié)構(gòu)）。

1.查找

將二叉查找樹(shù)的查找算法一般化就能直接得到 2-3 樹(shù)的查找算法。要判斷一個(gè)鍵是否存在樹(shù)中，先將它和根結(jié)點(diǎn)中的鍵比較。如果它和其中任意一個(gè)鍵相等，查找命中；否則就根據(jù)比較的結(jié)果找到指向相應(yīng)區(qū)間的鏈接，并在其指向的子樹(shù)中遞歸地繼續(xù)查找。

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

要在 2-3 樹(shù)中插入一個(gè)新結(jié)點(diǎn)，我們可以和二叉查找樹(shù)一樣先進(jìn)行一次未命中的查找，然后把新結(jié)點(diǎn)掛在樹(shù)的底部。但這樣的話樹(shù)無(wú)法保持完美平衡性。我們使用 2-3 樹(shù)的主要原因就在于它能夠在插入后繼續(xù)保持平衡。

如果未命中的查找結(jié)束于一個(gè) 2- 結(jié)點(diǎn)，處理就簡(jiǎn)單：我們只要把這個(gè) 2- 結(jié)點(diǎn)替換成一個(gè) 3- 結(jié)點(diǎn)，將要插入的鍵保存在其中即可。

但是，如果未命中的查找結(jié)束于一個(gè) 3- 結(jié)點(diǎn)，就要麻煩一些。

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

在考慮一般情況之前，先假設(shè)我們需要向一棵只含有一個(gè) 3- 結(jié)點(diǎn)的樹(shù)中插入一個(gè)新鍵。這棵樹(shù)中有兩個(gè)鍵，所以它已經(jīng)沒(méi)有可插入新鍵的空間了。為了將新鍵插入，我們先臨時(shí)將新鍵存入該結(jié)點(diǎn)，使之稱為一個(gè) 4- 結(jié)點(diǎn)（三個(gè)鍵和四條鏈接）。然后把這個(gè) 4- 結(jié)點(diǎn)轉(zhuǎn)換未一棵由 3個(gè) 2- 結(jié)點(diǎn)組成的 2-3 樹(shù)，其中一個(gè)結(jié)點(diǎn)（根）含有中鍵，一個(gè)結(jié)點(diǎn)含有3個(gè)鍵中的最小者（和根結(jié)點(diǎn)的左連接相連），一個(gè)結(jié)點(diǎn)含有3個(gè)鍵中的最大者。

這棵樹(shù)既是一棵含有3個(gè)結(jié)點(diǎn)的二叉查找樹(shù)，同時(shí)也是一棵完美平衡的 2-3 樹(shù)，因?yàn)槠渲兴械目真溄拥礁Y(jié)點(diǎn)的距離都相等。插入樹(shù)前高度為 0，插入樹(shù)后高度為 1。

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

在這種情況下我們需要在維持樹(shù)的完美平衡下為新鍵騰出空間。先像上面一樣構(gòu)造一個(gè)臨時(shí)的 4- 結(jié)點(diǎn)將其分解成3個(gè) 2- 結(jié)點(diǎn)，但此時(shí)我們不會(huì)為中鍵創(chuàng)建一個(gè)新結(jié)點(diǎn)，而是將其移至原父結(jié)點(diǎn)中。

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

對(duì)于這種情況，我們還是構(gòu)造一個(gè)臨時(shí) 4- 結(jié)點(diǎn)并將其分解，然后將它的中鍵插入它的父結(jié)點(diǎn)。但此時(shí)父結(jié)點(diǎn)也變成一個(gè)新的臨時(shí) 4- 結(jié)點(diǎn)，然后繼續(xù)在這個(gè)結(jié)點(diǎn)上進(jìn)行相同的變換，直至遇到一個(gè) 2- 結(jié)點(diǎn)或到達(dá)根結(jié)點(diǎn)。

6.分解根結(jié)點(diǎn)

如果從插入結(jié)點(diǎn)到根結(jié)點(diǎn)都是 3- 結(jié)點(diǎn)，根結(jié)點(diǎn)最終變成一個(gè)臨時(shí)的 4- 結(jié)點(diǎn)。此時(shí)按照向一棵只有一個(gè) 3- 結(jié)點(diǎn)的樹(shù)中插入新鍵的方法，將臨時(shí) 4- 結(jié)點(diǎn)分解成3個(gè) 2- 結(jié)點(diǎn)，使得樹(shù)高加1。

7.局部變換

將一個(gè) 4- 結(jié)點(diǎn)分解成一棵 2-3 樹(shù)可能有6種情況：

2-3 樹(shù)插入算法的根本在于這些變換都是局部的：除了相關(guān)結(jié)點(diǎn)和鏈接之外不必修改或者檢查樹(shù)的其他部分。每次變換中，變更的鏈接樹(shù)不會(huì)超過(guò)一個(gè)很小的常數(shù)。

8.全局性質(zhì)

這些局部變換不會(huì)影響樹(shù)的全局有序性和平衡性：任意空鏈接到根結(jié)點(diǎn)的路徑長(zhǎng)度都是相等的。和標(biāo)準(zhǔn)的二叉查找樹(shù)由上向下生長(zhǎng)不同， 2-3 樹(shù)的生長(zhǎng)是由下向上的。

在一棵大小為 N 的 2-3 樹(shù)中，插入和查找操作訪問(wèn)的結(jié)點(diǎn)必然不超過(guò) lgN 個(gè)。因此可以確定 2-3 樹(shù)在最壞的情況下仍有較好的性能，任何查找或者插入的成本都肯定不會(huì)超過(guò)對(duì)數(shù)級(jí)別。例如，含有 10億個(gè)結(jié)點(diǎn)的 2-3 樹(shù)的高度僅在 19到30之間。

但是，我們只是實(shí)現(xiàn)方式的一部分。盡管有可能編寫代碼來(lái)對(duì)表示2節(jié)點(diǎn)和3節(jié)點(diǎn)的不同數(shù)據(jù)類型執(zhí)行轉(zhuǎn)換，但是我們已經(jīng)描述的大多數(shù)任務(wù)在這種直接表示中都不方便實(shí)現(xiàn)。

2.紅黑二叉查找樹(shù)

我們使用紅黑二叉查找樹(shù)的簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)來(lái)表達(dá)并實(shí)現(xiàn) 2-3 樹(shù)。

1.定義

紅黑二叉樹(shù)背后的基本思想是用標(biāo)準(zhǔn)的二叉查找樹(shù)（完全由 2- 結(jié)點(diǎn)構(gòu)成）和一些額外的信息（替換 3- 結(jié)點(diǎn)）來(lái)表示 2-3 樹(shù)。我們將樹(shù)中的鏈接分為兩種類型：紅鏈接將兩個(gè) 2- 結(jié)點(diǎn)鏈接起來(lái)構(gòu)成一個(gè) 3- 結(jié)點(diǎn)，黑鏈接則是 2-3 樹(shù)中的普通鏈接。我們將 3- 結(jié)點(diǎn)表示為一條左斜的紅色鏈接（兩個(gè) 2- 結(jié)點(diǎn)其中之一是另一個(gè)的左子結(jié)點(diǎn)）相連的兩個(gè) 2- 結(jié)點(diǎn)。這種表示法的一個(gè)優(yōu)點(diǎn)是，無(wú)需修改就可以直接使用標(biāo)準(zhǔn)二叉查找樹(shù)的 Get（）方法。

紅黑樹(shù)的另一種定義是含有紅黑鏈接并滿足下列條件的二叉查找樹(shù)：

• 1.左鏈接均為左鏈接；
• 2.沒(méi)有任何一個(gè)結(jié)點(diǎn)同時(shí)和兩條紅鏈接相連；
• 3.該樹(shù)是完美黑色平衡的，即任意空鏈接到根結(jié)點(diǎn)的路徑上的黑鏈接數(shù)量相同。

滿足這樣定義的紅黑樹(shù)和相應(yīng)的 2-3 樹(shù)是一一對(duì)應(yīng)的。

2.一一對(duì)應(yīng)

如果我們將一棵紅黑樹(shù)中的紅鏈接畫(huà)平，那么所有的空鏈接到根結(jié)點(diǎn)的距離都是相同的。如果將有紅鏈接相連的結(jié)點(diǎn)合并，得到的就是一棵 2-3 樹(shù)。相反，如果將一棵 2-3 樹(shù)中的 3- 結(jié)點(diǎn)畫(huà)作由紅色鏈接相連的兩個(gè) 2- 結(jié)點(diǎn)，那么不會(huì)存在能夠和兩條紅鏈接相連的結(jié)點(diǎn)，且樹(shù)必然是完美黑色平衡的，因?yàn)楹阪溄蛹?2-3 樹(shù)中的普通鏈接，根據(jù)定義這些鏈接必然是完美平衡的。無(wú)論我們用那種方式取定義它們，紅黑樹(shù)都既是二叉查找樹(shù)，也是 2-3 樹(shù)。因此如果我們能夠在保持一一對(duì)應(yīng)關(guān)系的基礎(chǔ)上實(shí)現(xiàn) 2-3 樹(shù)的插入算法，那么我們就能將兩個(gè)算法的優(yōu)點(diǎn)結(jié)合起來(lái)：二叉查找樹(shù)中高效簡(jiǎn)潔的查找方法和 2-3 樹(shù)中高效的平衡插入算法。

3.顏色表示

因?yàn)槊總€(gè)結(jié)點(diǎn)都只會(huì)有一條指向自己的鏈接（從父結(jié)點(diǎn)指向它），我們將鏈接的顏色保存在表示結(jié)點(diǎn)的 Node 數(shù)據(jù)類型的布爾變量中。如果指向它的鏈接是紅色的，那么該變量為 true，黑色則為 false。我們約定空鏈接為黑色。我們使用 IsRed（） 來(lái)測(cè)試鏈接的顏色。

    public class RedBlackBST<Key, Value> : BaseSymbolTables<Key, Value>
        where Key : IComparable
    {
        private Node root;
        private  const bool RED = true;
        private const bool BLACK = false;
        private class Node
        {
            public Key key;
            public Value value;
            public Node left, right;
            public int N;
            public bool color;

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

        private bool IsRed(Node x)
        {
            if (x == null)
            {
                return false;
            }
            return x.color == RED;
        }

        private int Size(Node x)
        {
            if (x == null)
                return 0;
            else
                return x.N;
        }
    }

4.旋轉(zhuǎn)

在我們實(shí)現(xiàn)的某些操作中可能會(huì)出現(xiàn)紅色右鏈接或者兩條連續(xù)的紅鏈接，但在操作完成前這些情況都會(huì)被小心地旋轉(zhuǎn)并修復(fù)。旋轉(zhuǎn)操作會(huì)改變紅鏈接的指向。

一條紅色的右鏈接被轉(zhuǎn)換為左鏈接，稱為左旋轉(zhuǎn)。它對(duì)應(yīng)的方法接受一條指向紅黑樹(shù)中的某個(gè)結(jié)點(diǎn)的鏈接作為參數(shù)。假設(shè)被指向的結(jié)點(diǎn)的右鏈接是紅色的，這個(gè)方法會(huì)對(duì)樹(shù)進(jìn)行必要的調(diào)整并返回一個(gè)指向包含同一組鍵的子樹(shù)且左鏈接為紅色的根結(jié)點(diǎn)的鏈接。其代碼實(shí)現(xiàn)，只是將用兩個(gè)鍵中較小的作為根結(jié)點(diǎn)變成將較大的作為根結(jié)點(diǎn)。

        private Node RotateLeft(Node h)
        {
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }

        private Node RotateRight(Node h)
        {
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }

5.在旋轉(zhuǎn)后重置父結(jié)點(diǎn)的鏈接

無(wú)論是左旋轉(zhuǎn)還是右旋轉(zhuǎn)，旋轉(zhuǎn)操作都會(huì)返回一條鏈接。我們總是會(huì)用 RotateLeft 或 RotateRight 的返回值重置父結(jié)點(diǎn)或是根結(jié)點(diǎn)中相應(yīng)的鏈接。返回的鏈接可能是左鏈接也可能是右鏈接，但是總會(huì)將它賦予父結(jié)點(diǎn)中的鏈接。這個(gè)鏈接可能是紅色也可能是黑色 --RotateLeft 和 RotateRight 都通過(guò)將x.color 設(shè)為 h.color 保留它原來(lái)的顏色。這種簡(jiǎn)潔的代碼是我們使用遞歸實(shí)現(xiàn)二叉查找樹(shù)的各種方法的原因。

在插入新鍵時(shí)我們可以使用旋轉(zhuǎn)操作保證 2-3 樹(shù)和紅黑樹(shù)之間的一一對(duì)應(yīng)，因?yàn)樾D(zhuǎn)操作可以保持紅黑樹(shù)的兩個(gè)重要性質(zhì)：有序性和完美平衡性。下面來(lái)看如何使用旋轉(zhuǎn)操作來(lái)保持紅黑樹(shù)的另外兩個(gè)重要性質(zhì)：不存在兩條連續(xù)的紅鏈接和不存在紅色的右鏈接。

6.向單個(gè) 2- 結(jié)點(diǎn)中插入新鍵

一棵只含有一個(gè)鍵的紅黑樹(shù)只含有一個(gè) 2- 結(jié)點(diǎn)。插入另一個(gè)鍵后，需要馬上將它們旋轉(zhuǎn)。如果新鍵小于老鍵，只需新增一個(gè)紅色的結(jié)點(diǎn)即可。如果新鍵大于老鍵，那么新增的紅色結(jié)點(diǎn)將會(huì)產(chǎn)生一條紅色的右鏈接，需要左旋轉(zhuǎn)將其旋轉(zhuǎn)為紅色左連接并修改根結(jié)點(diǎn)的鏈接，插入操作才算完成。兩種情況的結(jié)果均為一棵和單個(gè) 3- 結(jié)點(diǎn)等價(jià)的紅黑樹(shù),其中含有兩個(gè)鍵，一條紅鏈接，樹(shù)的黑鏈接高度為 1。

7.向樹(shù)底部的 2- 結(jié)點(diǎn)插入新鍵

用和二叉查找樹(shù)相同的方式向一棵紅黑樹(shù)中插入一個(gè)新鍵會(huì)在樹(shù)的底部新增一個(gè)結(jié)點(diǎn)（為了保證有序性），但總是用紅鏈接將新節(jié)點(diǎn)和它的父結(jié)點(diǎn)相連。

8.向一棵雙鍵樹(shù)（即一個(gè) 3- 結(jié)點(diǎn)）中插入新鍵

這種情況分為三種情況：新鍵小于樹(shù)中的兩個(gè)鍵，兩者之間，或是大于樹(shù)中的兩個(gè)鍵。每種情況都會(huì)產(chǎn)生一個(gè)同時(shí)連接兩條紅鏈接的結(jié)點(diǎn)，而我們的目的就是修正這一點(diǎn)：

總的來(lái)說(shuō)，我們通過(guò) 0 次，1 次和 2 次旋轉(zhuǎn)以及顏色的變換得到了期望的結(jié)果。這些轉(zhuǎn)換是紅黑樹(shù)的動(dòng)態(tài)變化的關(guān)鍵。

9.顏色變換

我們專門用一個(gè)方法 FlipColors 方法來(lái)轉(zhuǎn)換一個(gè)結(jié)點(diǎn)的兩個(gè)紅色子結(jié)點(diǎn)的顏色。除了將子結(jié)點(diǎn)的顏色由紅變黑之外，同時(shí)還要將父結(jié)點(diǎn)的顏色由黑變紅。 這項(xiàng)操作最重要的性質(zhì)在于它和旋轉(zhuǎn)操作一樣是局部變換，不會(huì)影響整個(gè)樹(shù)的黑色平衡性。

        private void FlipColors(Node h)
        {
            h.color = RED;
            h.left.color = BLACK;
            h.right.color = BLACK;
        }

10.根結(jié)點(diǎn)總是黑色

根據(jù)前面的情況，顏色轉(zhuǎn)換會(huì)使根結(jié)點(diǎn)變?yōu)榧t色。這也可能出現(xiàn)在很大的紅黑樹(shù)中。嚴(yán)格地說(shuō)，紅色的根結(jié)點(diǎn)說(shuō)明根結(jié)點(diǎn)是一個(gè) 3- 結(jié)點(diǎn)的一部分，但實(shí)際情況并不是。因此我們?cè)诿看尾迦牒蠖紩?huì)將根結(jié)點(diǎn)設(shè)置為黑色。當(dāng)根結(jié)點(diǎn)由紅變黑時(shí)樹(shù)的高度就會(huì)加1。

11.向樹(shù)底部的 3- 結(jié)點(diǎn)插入新鍵

對(duì)于這種情況，前面的三種情況都會(huì)出現(xiàn)：可能是 3- 結(jié)點(diǎn)的右鏈接（只需要轉(zhuǎn)換顏色），或是左鏈接（需要右轉(zhuǎn)然后轉(zhuǎn)換顏色），或是中鏈接（需要左旋轉(zhuǎn)下層鏈接然后右旋轉(zhuǎn)上層鏈接，最后變換顏色）。顏色轉(zhuǎn)換會(huì)使中間結(jié)點(diǎn)變紅。

12.將紅鏈接在樹(shù)中向上傳遞

每次必要的旋轉(zhuǎn)之后都會(huì)進(jìn)行顏色轉(zhuǎn)換，這使得中結(jié)點(diǎn)變紅。在父結(jié)點(diǎn)看來(lái)，處理這樣一個(gè)紅色的結(jié)點(diǎn)的方式和處理一個(gè)新插入的紅色結(jié)點(diǎn)完全相同，即繼續(xù)把紅鏈接轉(zhuǎn)移到中結(jié)點(diǎn)上去。下圖總結(jié)的三種情況顯示了在紅黑樹(shù)中實(shí)現(xiàn) 2-3 樹(shù)的插入算法的關(guān)鍵操作所需的步驟：要在一個(gè) 3- 結(jié)點(diǎn)下插入新鍵，先臨時(shí)創(chuàng)建一個(gè) 4- 結(jié)點(diǎn)，將其分解并將紅鏈接由中間鍵傳遞給它的父結(jié)點(diǎn)。重復(fù)這個(gè)過(guò)程，就能將紅鏈接在樹(shù)中向上傳遞，直至遇到一個(gè) 2- 結(jié)點(diǎn)或者根結(jié)點(diǎn)。

總之，只要慎重地使用左旋轉(zhuǎn)，右旋轉(zhuǎn)和顏色轉(zhuǎn)換三種操作，就能保證插入操作后紅黑樹(shù)和 2-3 樹(shù)的一一對(duì)應(yīng)。在沿著插入結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑向上移動(dòng)時(shí)所經(jīng)過(guò)的每個(gè)結(jié)點(diǎn)中順序完成以下操作，就能完成插入操作：

• 1.如果右子結(jié)點(diǎn)是紅色且左子結(jié)點(diǎn)是黑色，進(jìn)行左旋轉(zhuǎn)；
• 2.如果左子結(jié)點(diǎn)和它的左子結(jié)點(diǎn)都是紅色，進(jìn)行右轉(zhuǎn)；
• 3.如果左右子結(jié)點(diǎn)均為紅色，進(jìn)行顏色轉(zhuǎn)換。

13.實(shí)現(xiàn)

因?yàn)楸３謽?shù)的平衡性所需的操作是由下至上在每個(gè)經(jīng)歷的結(jié)點(diǎn)中進(jìn)行，所以實(shí)現(xiàn)很簡(jiǎn)單：只需要在遞歸調(diào)用之后完成上面所說(shuō)的三種操作，這里通過(guò)三個(gè) if 語(yǔ)句完成。

    public class RedBlackBST<Key, Value> : BaseSymbolTables<Key, Value>
        where Key : IComparable
    {
        private Node root;
        private  const bool RED = true;
        private const bool BLACK = false;
        private class Node
        {
            public Key key;
            public Value value;
            public Node left, right;
            public int N;
            public bool color;

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

        private bool IsRed(Node x)
        {
            if (x == null)
            {
                return false;
            }
            return x.color == RED;
        }

        private Node RotateLeft(Node h)
        {
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }

        private Node RotateRight(Node h)
        {
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }
        private int Size(Node x)
        {
            if (x == null)
                return 0;
            else
                return x.N;
        }

        private void FlipColors(Node h)
        {
            h.color = RED;
            h.left.color = BLACK;
            h.right.color = BLACK;
        }

        public override void Put(Key key, Value value)
        {
            root = Put(root,key,value);
        }

        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;

            if (IsRed(h.right) && !IsRed(h.left))
                h = RotateLeft(h);
            if (IsRed(h.left) && IsRed(h.left.left))
                h = RotateRight(h);
            if (IsRed(h.left) && IsRed(h.right))
                FlipColors(h);

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

下圖時(shí)測(cè)試用例軌跡：

3.刪除操作

和插入操作一樣，我們也可以定義一系列局部變換來(lái)在刪除一個(gè)結(jié)點(diǎn)的同時(shí)保持樹(shù)的完美平衡性。這個(gè)過(guò)程比較復(fù)雜，因?yàn)椴粌H要在為了刪除一個(gè)結(jié)點(diǎn)而構(gòu)造臨時(shí) 4- 結(jié)點(diǎn)時(shí)沿著查找路徑向下進(jìn)行變換，還要分解遺留的 4- 結(jié)點(diǎn)時(shí)沿著查找路徑向上進(jìn)行變換。

1.自頂向下的 2-3-4 樹(shù)

開(kāi)始之前，先學(xué)習(xí)一個(gè)沿著查找路徑既能向上也能向下進(jìn)行變換的簡(jiǎn)單算法： 2-3-4 樹(shù)的插入算法，2-3-4 樹(shù)=中允許存在 4- 結(jié)點(diǎn)。它的插入算法沿查找路徑向下變換是為了把凹征當(dāng)前結(jié)點(diǎn)不是 4- 結(jié)點(diǎn)（這樣樹(shù)底才有空間插入新的鍵），沿查找路徑向上進(jìn)行變換是為了將之前創(chuàng)建的 4- 結(jié)點(diǎn)配平。向下變換和 2-3 樹(shù)種分解 4- 結(jié)點(diǎn)所進(jìn)行的變換相同。如果根結(jié)點(diǎn)是4-結(jié)點(diǎn)，就將它分解成3個(gè) 2- 結(jié)點(diǎn)，使得樹(shù)高加一。在向下查找的過(guò)程中，如果遇到一個(gè)父結(jié)點(diǎn)是 2- 結(jié)點(diǎn)的 4- 結(jié)點(diǎn)，將 4- 結(jié)點(diǎn)分解成兩個(gè) 2- 結(jié)點(diǎn)并將中間鍵傳遞給父結(jié)點(diǎn)，使得父結(jié)點(diǎn)變成 3- 結(jié)點(diǎn)。如果遇到一個(gè)父結(jié)點(diǎn)是 3- 結(jié)點(diǎn)的 4- 結(jié)點(diǎn)，將 4- 結(jié)點(diǎn)分解成兩個(gè) 2- 結(jié)點(diǎn)并將中間鍵傳遞給父結(jié)點(diǎn)，使得父結(jié)點(diǎn)變?yōu)?4- 結(jié)點(diǎn)；不必?fù)?dān)心遇到父結(jié)點(diǎn)為 4- 結(jié)點(diǎn)的 4- 結(jié)點(diǎn)，因?yàn)椴迦胨惴ū旧砭捅ＷC了這種情況不會(huì)出現(xiàn)。到達(dá)樹(shù)底之后，只會(huì)遇到 2- 結(jié)點(diǎn)或 3- 結(jié)點(diǎn)，所以我們可以插入新的鍵。

要用紅黑樹(shù)實(shí)現(xiàn)這個(gè)算法，我們需要：

將 4- 結(jié)點(diǎn) 表示由三個(gè) 2- 結(jié)點(diǎn)組成的一棵平衡的子樹(shù)，根結(jié)點(diǎn)和兩個(gè)子結(jié)點(diǎn)都用紅鏈接相連；
在向下的過(guò)程中分解所有 4- 結(jié)點(diǎn)并進(jìn)行顏色轉(zhuǎn)換；
和插入操作一樣，在向上的過(guò)程用旋轉(zhuǎn)將 4- 結(jié)點(diǎn)配平。
只需移動(dòng)上面算法的 Put 方法中的一行代碼就能實(shí)現(xiàn) 2-3-4 樹(shù)中的插入操作：將 ColorFlip 語(yǔ)句及其 if 語(yǔ)句一道遞歸調(diào)用之前（null 測(cè)試和比較操作之間）。

2.刪除最小鍵

從樹(shù)底部的 3- 結(jié)點(diǎn)刪除鍵很簡(jiǎn)單，但從 2- 結(jié)點(diǎn)刪除一個(gè)鍵會(huì)留下一個(gè)空鏈接，這樣會(huì)破環(huán)樹(shù)的完美平衡性。
為了保證我們不會(huì)刪除一個(gè) 2- 結(jié)點(diǎn)，我們沿著左連接向下進(jìn)行變換，確保當(dāng)前結(jié)點(diǎn)不是 2- 結(jié)點(diǎn)（可能是 3- 結(jié)點(diǎn)，也可能是臨時(shí) 4- 結(jié)點(diǎn)）。
首先，根結(jié)點(diǎn)可能有兩種情況。如果根結(jié)點(diǎn)是 2- 結(jié)點(diǎn)且它的兩個(gè)子結(jié)點(diǎn)都是 2- 結(jié)點(diǎn)，我們可以直接將這三個(gè)結(jié)點(diǎn)變成一個(gè) 4- 結(jié)點(diǎn)；否則我們需要保證根結(jié)點(diǎn)的左子結(jié)點(diǎn)不是 2- 結(jié)點(diǎn)，如有必要可以從它右側(cè)的兄弟結(jié)點(diǎn)“借”一個(gè)鍵來(lái)。如圖。在沿著左連接向下的過(guò)程中，保證一下情況之一成立：
如果當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)不是 2- 結(jié)點(diǎn)，完成；
如果當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)是 2- 結(jié)點(diǎn)而它的親兄弟結(jié)點(diǎn)不是 2- 結(jié)點(diǎn)，將左子結(jié)點(diǎn)的兄弟結(jié)點(diǎn)中的一個(gè)鍵移動(dòng)到左子結(jié)點(diǎn)中；
如果當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)和它的親兄弟結(jié)點(diǎn)都是 2- 結(jié)點(diǎn)，將左子結(jié)點(diǎn)，父結(jié)點(diǎn)中的最小鍵和左子節(jié)點(diǎn)最近的兄弟結(jié)點(diǎn)合并成一個(gè) 4- 結(jié)點(diǎn)，使父結(jié)點(diǎn)由 3- 結(jié)點(diǎn)變成 2- 結(jié)點(diǎn)或者由 4- 結(jié)點(diǎn)變成 3- 結(jié)點(diǎn)。
在遍歷的過(guò)程中執(zhí)行這個(gè)過(guò)程，最后能夠得到一個(gè)含有最小鍵的 3- 結(jié)點(diǎn)或者 4- 結(jié)點(diǎn)，然后就可以直接從中將其刪除。我們?cè)倩仡^向上分解所有臨時(shí)的 4- 結(jié)點(diǎn)。

3.刪除操作

在查找路徑上進(jìn)行和刪除最小鍵相同的變換同樣可以保證在查找過(guò)程中任意當(dāng)前結(jié)點(diǎn)均不是 2- 結(jié)點(diǎn)。如果被查找的鍵在樹(shù)的底部，可以直接刪除。如果不在，需要將它和它的后繼結(jié)點(diǎn)交換，和二叉查找樹(shù)
一樣。

紅黑樹(shù)的性質(zhì)

研究紅黑樹(shù)的性質(zhì)就是要檢查對(duì)應(yīng)的 2-3 樹(shù)并對(duì)相應(yīng)的 2-3 樹(shù)進(jìn)行分析過(guò)程。所有基于紅黑樹(shù)的符號(hào)表實(shí)現(xiàn)都能保證操作的運(yùn)行時(shí)間為對(duì)數(shù)級(jí)別（范圍查找除外）。
無(wú)論鍵的插入順序如何，紅黑樹(shù)都幾乎是完美平衡的。一棵大小為 N 的紅黑樹(shù)的高度不會(huì)超過(guò) 2lgN 。紅黑樹(shù)的最壞情況是它所對(duì)應(yīng)的 2-3 樹(shù)中構(gòu)成最左邊的路徑結(jié)點(diǎn)全部都是 3- 結(jié)點(diǎn)而其余均是 2- 結(jié)點(diǎn)。
最左邊的路徑長(zhǎng)度是只包含 2- 結(jié)點(diǎn)的路徑長(zhǎng)度（~lgN）的兩倍。使用隨機(jī)的鍵序列，在一棵大小為 N 的紅黑樹(shù)中一次查找所需的比較次數(shù)約為（1.00 lgN - 0.5）,根結(jié)點(diǎn)到任意結(jié)點(diǎn)的平均路徑長(zhǎng)度 ~ 1.00lgN 。
紅黑樹(shù)的 Get 方法不會(huì)檢查結(jié)點(diǎn)的顏色，因此平衡性相關(guān)的操作不會(huì)產(chǎn)生任何負(fù)擔(dān)；因?yàn)闃?shù)是平衡的，所以查找比二叉查找樹(shù)更快。每個(gè)只會(huì)被插入一次，但卻可能查找無(wú)數(shù)次。

到此這篇關(guān)于C#實(shí)現(xiàn)平衡查找樹(shù)的文章就介紹到這了。希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。