C#實(shí)現(xiàn)平衡查找樹

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

1.2-3查找樹

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

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

1.查找

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

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

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

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

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

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

在考慮一般情況之前，先假設(shè)我們需要向一棵只含有一個(gè)3-結(jié)點(diǎn)的樹中插入一個(gè)新鍵。這棵樹中有兩個(gè)鍵，所以它已經(jīng)沒有可插入新鍵的空間了。為了將新鍵插入，我們先臨時(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樹，其中一個(gè)結(jié)點(diǎn)（根）含有中鍵，一個(gè)結(jié)點(diǎn)含有3個(gè)鍵中的最小者（和根結(jié)點(diǎn)的左連接相連），一個(gè)結(jié)點(diǎn)含有3個(gè)鍵中的最大者。

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

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

在這種情況下我們需要在維持樹的完美平衡下為新鍵騰出空間。先像上面一樣構(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í)4-結(jié)點(diǎn)分解成3個(gè)2-結(jié)點(diǎn)，使得樹高加1。

7.局部變換

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

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

8.全局性質(zhì)

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

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

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

2.紅黑二叉查找樹

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

1.定義

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

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

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

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

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

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

3.顏色表示

因?yàn)槊總€(gè)結(jié)點(diǎn)都只會(huì)有一條指向自己的鏈接（從父結(jié)點(diǎn)指向它），我們將鏈接的顏色保存在表示結(jié)點(diǎn)的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)

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

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

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é)點(diǎn)的鏈接

無論是左旋轉(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都通過將x.color設(shè)為h.color保留它原來的顏色。這種簡潔的代碼是我們使用遞歸實(shí)現(xiàn)二叉查找樹的各種方法的原因。

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

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

一棵只含有一個(gè)鍵的紅黑樹只含有一個(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à)的紅黑樹,其中含有兩個(gè)鍵，一條紅鏈接，樹的黑鏈接高度為1。

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

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

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

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

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

9.顏色變換

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

privatevoidFlipColors(Nodeh)

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)在很大的紅黑樹中。嚴(yán)格地說，紅色的根結(jié)點(diǎn)說明根結(jié)點(diǎn)是一個(gè)3-結(jié)點(diǎn)的一部分，但實(shí)際情況并不是。因此我們?cè)诿看尾迦牒蠖紩?huì)將根結(jié)點(diǎn)設(shè)置為黑色。當(dāng)根結(jié)點(diǎn)由紅變黑時(shí)樹的高度就會(huì)加1。

11.向樹底部的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.將紅鏈接在樹中向上傳遞

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

總之，只要慎重地使用左旋轉(zhuǎn)，右旋轉(zhuǎn)和顏色轉(zhuǎn)換三種操作，就能保證插入操作后紅黑樹和2-3樹的一一對(duì)應(yīng)。在沿著插入結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑向上移動(dòng)時(shí)所經(jīng)過的每個(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)楸３謽涞钠胶庑运璧牟僮魇怯上轮辽显诿總€(gè)經(jīng)歷的結(jié)點(diǎn)中進(jìn)行，所以實(shí)現(xiàn)很簡單：只需要在遞歸調(diào)用之后完成上面所說的三種操作，這里通過三個(gè)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;

}

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

3.刪除操作

和插入操作一樣，我們也可以定義一系列局部變換來在刪除一個(gè)結(jié)點(diǎn)的同時(shí)保持樹的完美平衡性。這個(gè)過程比較復(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樹

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

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

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

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

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

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

2.刪除最小鍵

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

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