第C#實現平衡查找樹目錄1.2-3查找樹1.查找2.向2-結點中插入新鍵3.向一棵只含有一個3-結點的樹中插入新鍵4.向一個父結點為2-結點的3-結點中插入新鍵5.向一個父結點為3-結點的3-結點插入新鍵6.分解根結點7.局部變換8.全局性質2.紅黑二叉查找樹1.定義2.一一對應3.顏色表示4.旋轉5.在旋轉后重置父結點的鏈接6.向單個2-結點中插入新鍵7.向樹底部的2-結點插入新鍵8.向一棵雙鍵樹（即一個3-結點）中插入新鍵9.顏色變換10.根結點總是黑色11.向樹底部的3-結點插入新鍵12.將紅鏈接在樹中向上傳遞13.實現3.刪除操作1.自頂向下的2-3-4樹2.刪除最小鍵3.刪除操作紅黑樹的性質之前講的二叉查找樹在最壞情況下性能還是很低的。平衡查找樹能夠保證無論如何構造它，它的運行時間都是對數級別。在一棵含有N個結點的樹中，我們希望樹高為~lgN，這樣我們就能保證所有查找都能在~lgN次比較內結束，就和二分查找一樣。但是，在動態插入中保證樹的完美平衡的代價太高。我們稍微降低完美平衡的要求，學習一種能夠保證符號表API中所有操作均能在對數時間內完成的數據結構。

1.2-3查找樹

為了保證查找樹的平衡性，我們需要一些靈活性，因此我們允許樹中的一個結點保存多個鍵。一棵標準的二叉查找樹中的結點稱為2-結點，含有一個鍵和兩條連接；將含有兩個鍵和三條連接的結點稱為3-結點（左連接指向的2-3樹中的鍵都小于該結點，中連接指向的2-3樹種中的鍵都位于該結點的兩個鍵之間，右鏈接指向的2-3樹中的鍵都大于該結點）。

一棵完美平衡的2-3查找樹中的所有空連接到根結點的距離都應該事相同的。簡潔起見，這里用2-3樹指代一棵完美平衡的2-3查找樹（在其他情況下這個次表示一種更一般的結構）。

1.查找

將二叉查找樹的查找算法一般化就能直接得到2-3樹的查找算法。要判斷一個鍵是否存在樹中，先將它和根結點中的鍵比較。如果它和其中任意一個鍵相等，查找命中；否則就根據比較的結果找到指向相應區間的鏈接，并在其指向的子樹中遞歸地繼續查找。

2.向2-結點中插入新鍵

要在2-3樹中插入一個新結點，我們可以和二叉查找樹一樣先進行一次未命中的查找，然后把新結點掛在樹的底部。但這樣的話樹無法保持完美平衡性。我們使用2-3樹的主要原因就在于它能夠在插入后繼續保持平衡。

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

但是，如果未命中的查找結束于一個3-結點，就要麻煩一些。

3.向一棵只含有一個3-結點的樹中插入新鍵

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

這棵樹既是一棵含有3個結點的二叉查找樹，同時也是一棵完美平衡的2-3樹，因為其中所有的空鏈接到根結點的距離都相等。插入樹前高度為0，插入樹后高度為1。

4.向一個父結點為2-結點的3-結點中插入新鍵

在這種情況下我們需要在維持樹的完美平衡下為新鍵騰出空間。先像上面一樣構造一個臨時的4-結點將其分解成3個2-結點，但此時我們不會為中鍵創建一個新結點，而是將其移至原父結點中。

5.向一個父結點為3-結點的3-結點插入新鍵

對于這種情況，我們還是構造一個臨時4-結點并將其分解，然后將它的中鍵插入它的父結點。但此時父結點也變成一個新的臨時4-結點，然后繼續在這個結點上進行相同的變換，直至遇到一個2-結點或到達根結點。

6.分解根結點

如果從插入結點到根結點都是3-結點，根結點最終變成一個臨時的4-結點。此時按照向一棵只有一個3-結點的樹中插入新鍵的方法，將臨時4-結點分解成3個2-結點，使得樹高加1。

7.局部變換

將一個4-結點分解成一棵2-3樹可能有6種情況：

2-3樹插入算法的根本在于這些變換都是局部的：除了相關結點和鏈接之外不必修改或者檢查樹的其他部分。每次變換中，變更的鏈接樹不會超過一個很小的常數。

8.全局性質

這些局部變換不會影響樹的全局有序性和平衡性：任意空鏈接到根結點的路徑長度都是相等的。和標準的二叉查找樹由上向下生長不同，2-3樹的生長是由下向上的。

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

但是，我們只是實現方式的一部分。盡管有可能編寫代碼來對表示2節點和3節點的不同數據類型執行轉換，但是我們已經描述的大多數任務在這種直接表示中都不方便實現。

2.紅黑二叉查找樹

我們使用紅黑二叉查找樹的簡單數據結構來表達并實現2-3樹。

1.定義

紅黑二叉樹背后的基本思想是用標準的二叉查找樹（完全由2-結點構成）和一些額外的信息（替換3-結點）來表示2-3樹。我們將樹中的鏈接分為兩種類型：紅鏈接將兩個2-結點鏈接起來構成一個3-結點，黑鏈接則是2-3樹中的普通鏈接。我們將3-結點表示為一條左斜的紅色鏈接（兩個2-結點其中之一是另一個的左子結點）相連的兩個2-結點。這種表示法的一個優點是，無需修改就可以直接使用標準二叉查找樹的Get（）方法。

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

1.左鏈接均為左鏈接；2.沒有任何一個結點同時和兩條紅鏈接相連；3.該樹是完美黑色平衡的，即任意空鏈接到根結點的路徑上的黑鏈接數量相同。

滿足這樣定義的紅黑樹和相應的2-3樹是一一對應的。

2.一一對應

如果我們將一棵紅黑樹中的紅鏈接畫平，那么所有的空鏈接到根結點的距離都是相同的。如果將有紅鏈接相連的結點合并，得到的就是一棵2-3樹。相反，如果將一棵2-3樹中的3-結點畫作由紅色鏈接相連的兩個2-結點，那么不會存在能夠和兩條紅鏈接相連的結點，且樹必然是完美黑色平衡的，因為黑鏈接即2-3樹中的普通鏈接，根據定義這些鏈接必然是完美平衡的。無論我們用那種方式取定義它們，紅黑樹都既是二叉查找樹，也是2-3樹。因此如果我們能夠在保持一一對應關系的基礎上實現2-3樹的插入算法，那么我們就能將兩個算法的優點結合起來：二叉查找樹中高效簡潔的查找方法和2-3樹中高效的平衡插入算法。

3.顏色表示

因為每個結點都只會有一條指向自己的鏈接（從父結點指向它），我們將鏈接的顏色保存在表示結點的Node數據類型的布爾變量中。如果指向它的鏈接是紅色的，那么該變量為true，黑色則為false。我們約定空鏈接為黑色。我們使用IsRed（）來測試鏈接的顏色。

publicclassRedBlackBSTKey,Value:BaseSymbolTablesKey,Value

whereKey:IComparable

privateNoderoot;

privateconstboolRED=true;

privateconstboolBLACK=false;

privateclassNode

publicKeykey;

publicValuevalue;

publicNodeleft,right;

publicintN;

publicboolcolor;

Node(Keykey,Valuevalue,intN,boolcolor)

this.key=key;

this.value=value;

this.N=N;

this.color=color;

privateboolIsRed(Nodex)

if(x==null)

returnfalse;

returnx.color==RED;

privateintSize(Nodex)

if(x==null)

return0;

else

returnx.N;

}

4.旋轉

在我們實現的某些操作中可能會出現紅色右鏈接或者兩條連續的紅鏈接，但在操作完成前這些情況都會被小心地旋轉并修復。旋轉操作會改變紅鏈接的指向。

一條紅色的右鏈接被轉換為左鏈接，稱為左旋轉。它對應的方法接受一條指向紅黑樹中的某個結點的鏈接作為參數。假設被指向的結點的右鏈接是紅色的，這個方法會對樹進行必要的調整并返回一個指向包含同一組鍵的子樹且左鏈接為紅色的根結點的鏈接。其代碼實現，只是將用兩個鍵中較小的作為根結點變成將較大的作為根結點。

privateNodeRotateLeft(Nodeh)

Nodex=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);

returnx;

privateNodeRotateRight(Nodeh)

Nodex=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);

returnx;

}

5.在旋轉后重置父結點的鏈接

無論是左旋轉還是右旋轉，旋轉操作都會返回一條鏈接。我們總是會用RotateLeft或RotateRight的返回值重置父結點或是根結點中相應的鏈接。返回的鏈接可能是左鏈接也可能是右鏈接，但是總會將它賦予父結點中的鏈接。這個鏈接可能是紅色也可能是黑色--RotateLeft和RotateRight都通過將x.color設為h.color保留它原來的顏色。這種簡潔的代碼是我們使用遞歸實現二叉查找樹的各種方法的原因。

在插入新鍵時我們可以使用旋轉操作保證2-3樹和紅黑樹之間的一一對應，因為旋轉操作可以保持紅黑樹的兩個重要性質：有序性和完美平衡性。下面來看如何使用旋轉操作來保持紅黑樹的另外兩個重要性質：不存在兩條連續的紅鏈接和不存在紅色的右鏈接。

6.向單個2-結點中插入新鍵

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

7.向樹底部的2-結點插入新鍵

用和二叉查找樹相同的方式向一棵紅黑樹中插入一個新鍵會在樹的底部新增一個結點（為了保證有序性），但總是用紅鏈接將新節點和它的父結點相連。

8.向一棵雙鍵樹（即一個3-結點）中插入新鍵

這種情況分為三種情況：新鍵小于樹中的兩個鍵，兩者之間，或是大于樹中的兩個鍵。每種情況都會產生一個同時連接兩條紅鏈接的結點，而我們的目的就是修正這一點：

總的來說，我們通過0次，1次和2次旋轉以及顏色的變換得到了期望的結果。這些轉換是紅黑樹的動態變化的關鍵。

9.顏色變換

我們專門用一個方法FlipColors方法來轉換一個結點的兩個紅色子結點的顏色。除了將子結點的顏色由紅變黑之外，同時還要將父結點的顏色由黑變紅。這項操作最重要的性質在于它和旋轉操作一樣是局部變換，不會影響整個樹的黑色平衡性。

privatevoidFlipColors(Nodeh)

h.color=RED;

h.left.color=BLACK;

h.right.color=BLACK;

}

10.根結點總是黑色

根據前面的情況，顏色轉換會使根結點變為紅色。這也可能出現在很大的紅黑樹中。嚴格地說，紅色的根結點說明根結點是一個3-結點的一部分，但實際情況并不是。因此我們在每次插入后都會將根結點設置為黑色。當根結點由紅變黑時樹的高度就會加1。

11.向樹底部的3-結點插入新鍵

對于這種情況，前面的三種情況都會出現：可能是3-結點的右鏈接（只需要轉換顏色），或是左鏈接（需要右轉然后轉換顏色），或是中鏈接（需要左旋轉下層鏈接然后右旋轉上層鏈接，最后變換顏色）。顏色轉換會使中間結點變紅。

12.將紅鏈接在樹中向上傳遞

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

總之，只要慎重地使用左旋轉，右旋轉和顏色轉換三種操作，就能保證插入操作后紅黑樹和2-3樹的一一對應。在沿著插入結點到根結點的路徑向上移動時所經過的每個結點中順序完成以下操作，就能完成插入操作：

1.如果右子結點是紅色且左子結點是黑色，進行左旋轉；2.如果左子結點和它的左子結點都是紅色，進行右轉；3.如果左右子結點均為紅色，進行顏色轉換。

13.實現

因為保持樹的平衡性所需的操作是由下至上在每個經歷的結點中進行，所以實現很簡單：只需要在遞歸調用之后完成上面所說的三種操作，這里通過三個if語句完成。

publicclassRedBlackBSTKey,Value:BaseSymbolTablesKey,Value

whereKey:IComparable

privateNoderoot;

privateconstboolRED=true;

privateconstboolBLACK=false;

privateclassNode

publicKeykey;

publicValuevalue;

publicNodeleft,right;

publicintN;

publicboolcolor;

publicNode(Keykey,Valuevalue,intN,boolcolor)

this.key=key;

this.value=value;

this.N=N;

this.color=color;

privateboolIsRed(Nodex)

if(x==null)

returnfalse;

returnx.color==RED;

privateNodeRotateLeft(Nodeh)

Nodex=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);

returnx;

privateNodeRotateRight(Nodeh)

Nodex=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);

returnx;

privateintSize(Nodex)

if(x==null)

return0;

else

returnx.N;

privatevoidFlipColors(Nodeh)

h.color=RED;

h.left.color=BLACK;

h.right.color=BLACK;

publicoverridevoidPut(Keykey,Valuevalue)

root=Put(root,key,value);

privateNodePut(Nodeh,Keykey,Valuevalue)

if(h==null)

returnnewNode(key,value,1,RED);

intcmp=key.CompareTo(h.key);

if(cmp0)

h.left=Put(h.left,key,value);

elseif(cmp0)

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;

returnh;

}

下圖時測試用例軌跡：

3.刪除操作

和插入操作一樣，我們也可以定義一系列局部變換來在刪除一個結點的同時保持樹的完美平衡性。這個過程比較復雜，因為不僅要在為了刪除一個結點而構造臨時4-結點時沿著查找路徑向下進行變換，還要分解遺留的4-結點時沿著查找路徑向上進行變換。

1.自頂向下的2-3-4樹

開始之前，先學習一個沿著查找路徑既能向上也能向下進行變換的簡單算法：2-3-4樹的插入算法，2-3-4樹=中允許存在4-結點。它的插入算法沿查找路徑向下變換是為了把凹征當前結點不是4-結點（這樣樹底才有空間插入新的鍵），沿查找路徑向上進行變換是為了將之前創建的4-結點配平。向下變換和2-3樹種分解4-結點所進行的變換相同。如果根結點是4-結點，就將它分解成3個2-結點，使得樹高加一。在向下查找的過程中，如果遇到一個父結點是2-結點的4-結點，將4-結點分解成兩個2-結點并將中間鍵傳遞給父結點，使得父結點變成3-結點。如果遇到一個父結點是3-結點的4-結點，將4-結點分解成兩個2-結點并將中間鍵傳遞給父結點，使得父結點變為4-結點；不必擔心遇到父結點為4-結點的4-結點，因為插入算法本身就保證了這種情況不會出現。到達樹底之后，只會遇到2-結點或3-結點，所以我們可以插入新的鍵。

要用紅黑樹實現這個算法，我們需要：

將4-結點表示由三個2-結點組成的一棵平衡的子樹，根結點和兩個子結點都用紅鏈接相連；

在向下的過程中分解所有4-結點并進行顏色轉換；

和插入操作一樣，在向上的過程用旋轉將4-結點配平。

只需移動上面算法的Put方法中的一行代碼就能實現2-3-4樹中的插入操作：將ColorFlip語句及其if語句一道遞歸調用之前（null測試和比較操作之間）。

2.刪除最小鍵

從樹底部的3-結點刪除鍵很簡單，但從2-結點刪除一個鍵會留下一個空鏈接，這樣會破環樹的完美平衡性。

為了保證我們不會刪除一個2-結點，我們沿著左連接向下進行變換，確保當前結點不是2-結點（可能是3-結點，也可能是臨時4-