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

1.2-3查找樹

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

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

1.查找

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

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

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

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

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

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

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

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

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

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

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

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

6.分解根結(jié)點

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

7.局部變換

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

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

8.全局性質(zhì)

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

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

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

2.紅黑二叉查找樹

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

1.定義

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

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

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

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

2.一一對應(yīng)

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

3.顏色表示

因為每個結(jié)點都只會有一條指向自己的鏈接（從父結(jié)點指向它），我們將鏈接的顏色保存在表示結(jié)點的Node數(shù)據(jù)類型的布爾變量中。如果指向它的鏈接是紅色的，那么該變量為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.旋轉(zhuǎn)

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

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

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.在旋轉(zhuǎn)后重置父結(jié)點的鏈接

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

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

6.向單個2-結(jié)點中插入新鍵

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

7.向樹底部的2-結(jié)點插入新鍵

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

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

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

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

9.顏色變換

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

privatevoidFlipColors(Nodeh)

h.color=RED;

h.left.color=BLACK;

h.right.color=BLACK;

}

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

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

11.向樹底部的3-結(jié)點插入新鍵

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

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

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

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

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

13.實現(xiàn)

因為保持樹的平衡性所需的操作是由下至上在每個經(jīng)歷的結(jié)點中進行，所以實現(xiàn)很簡單：只需要在遞歸調(diào)用之后完成上面所說的三種操作，這里通過三個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.刪除操作

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

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

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

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

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

在向下的過程中分解所有4-結(jié)點并進行顏色轉(zhuǎn)換；

和插入操作一樣，在向上的過程用旋轉(zhuǎn)將4-結(jié)點配平。

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

2.刪除最小鍵

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

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