C#實(shí)現(xiàn)平衡查找樹(shù)
之前講的二叉查找樹(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ù)中的紅鏈接畫平,那么所有的空鏈接到根結(jié)點(diǎn)的距離都是相同的。如果將有紅鏈接相連的結(jié)點(diǎn)合并,得到的就是一棵 2-3 樹(shù)。相反,如果將一棵 2-3 樹(shù)中的 3- 結(jié)點(diǎn)畫作由紅色鏈接相連的兩個(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)楸3謽?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)椴迦胨惴ū旧砭捅WC了這種情況不會(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í)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
詳解如何在ASP.NET Core配置請(qǐng)求超時(shí)中間件
本文參考官方文檔,為大家詳細(xì)介紹如何使用Asp.net core 8.0 的最小API 模板項(xiàng)目,配置超時(shí)中間件,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解下2024-01-01C#將Excel中的數(shù)據(jù)轉(zhuǎn)換成DataSet
這篇文章主要介紹了C#將Excel中的數(shù)據(jù)轉(zhuǎn)換成DataSet的方法,非常簡(jiǎn)單實(shí)用,從本人項(xiàng)目中提取出來(lái)的,推薦給大家,希望對(duì)大家學(xué)習(xí)C#能夠有所幫助。2015-03-03WCF分布式開(kāi)發(fā)之MSMQ消息隊(duì)列
這篇文章介紹了WCF分布式開(kāi)發(fā)之MSMQ消息隊(duì)列,文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-05-05C#通過(guò)XML節(jié)點(diǎn)屬性/屬性值讀取寫入XML操作代碼實(shí)例
本文主要介紹C#通過(guò)XML節(jié)點(diǎn)屬性、屬性值對(duì)XML的讀取,寫入操作,大家參考使用吧2013-11-11C#調(diào)用百度地圖API根據(jù)地名獲取經(jīng)緯度geocoding
本文主要介紹了C#調(diào)用百度地圖API根據(jù)地名獲取經(jīng)緯度geocoding,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-04-04Winform學(xué)生信息管理系統(tǒng)主頁(yè)面設(shè)計(jì)(2)
這篇文章主要為大家詳細(xì)介紹了Winform學(xué)生信息管理系統(tǒng)主頁(yè)面設(shè)計(jì)思路,感興趣的小伙伴們可以參考一下2016-05-05C#調(diào)用RabbitMQ實(shí)現(xiàn)消息隊(duì)列的示例代碼
這篇文章主要介紹了C#調(diào)用RabbitMQ實(shí)現(xiàn)消息隊(duì)列的示例代碼,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12DevExpress實(shí)現(xiàn)GridView當(dāng)無(wú)數(shù)據(jù)行時(shí)提示消息
這篇文章主要介紹了DevExpress實(shí)現(xiàn)GridView當(dāng)無(wú)數(shù)據(jù)行時(shí)提示消息,需要的朋友可以參考下2014-08-08