【正文】 （取值為 red或 black ）、 key、 left、 right和 p（省略了相關(guān)數(shù)據(jù)或指針）。 RB樹把包含 key域的結(jié)點(diǎn)作為內(nèi)部結(jié)點(diǎn)，而以 NULL（空）作為其“外部結(jié)點(diǎn)”，這些外部結(jié)點(diǎn)與 left、 right、 p域中的NULL指針值相對(duì)應(yīng)（見 ），空結(jié)點(diǎn)與實(shí)際的數(shù)據(jù)元素或關(guān)鍵字都無關(guān)。 一個(gè)在結(jié)構(gòu)上做了上述改變的二叉搜索樹稱為一個(gè) RB樹 。 23 24 RB樹滿足下面的性質(zhì)： 1. 每個(gè)結(jié)點(diǎn)的 color域必須為 red或 black； 2. 每個(gè)葉結(jié)點(diǎn)（ NULL）的 color為 black； 3. 如果一個(gè)結(jié)點(diǎn)的 color為 red，則其子結(jié)點(diǎn)全為 black結(jié)點(diǎn)。 4. 從某一結(jié)點(diǎn)到其子樹上任意一個(gè)葉結(jié)點(diǎn)的所有簡(jiǎn)單路徑，包含相同個(gè)數(shù)的 black結(jié)點(diǎn)。 從一個(gè)結(jié)點(diǎn) x到（其子樹中的）任一葉結(jié)點(diǎn)的簡(jiǎn)單路徑上的黑結(jié)點(diǎn)的個(gè)數(shù)稱為結(jié)點(diǎn) x的 black高（ blackheight），表示為bh(x) 。 定理 具有 n個(gè)內(nèi)部結(jié)點(diǎn)的 RB樹的樹高 h ≤ 2ln(n+1)。 證明： 1. 首先用歸納法證明以 RB樹上任一結(jié)點(diǎn) x為根的子樹至少 包含 個(gè)內(nèi)部結(jié)點(diǎn)。 12 )x(bh ?25 1176。 遞歸基礎(chǔ)：對(duì)于高度為 0的結(jié)點(diǎn) x， 即 x為葉結(jié)點(diǎn) （ NULL） ，以其為根的子樹有 0個(gè)內(nèi)部結(jié)點(diǎn) ， 即至少有 個(gè)內(nèi)部結(jié)點(diǎn) 。 命題成立 。 2176。 設(shè)對(duì)于高度為 h1的結(jié)點(diǎn)命題成立 。 3176。 考察高為 h(0)的結(jié)點(diǎn) x， 由于 h0， x是 RB樹的內(nèi)部結(jié)點(diǎn) ，必有兩個(gè)子結(jié)點(diǎn) x x2， 其高為 h1， 且有 根據(jù)歸納假設(shè)，以 x x2為根的兩子樹分別至少有 個(gè)內(nèi)部結(jié)點(diǎn)， ∴ 以 x為根的子樹至少有 個(gè)內(nèi)部結(jié)點(diǎn)。 ∴ 歸納完成。 01212 0)x(bh ???????????b l ac kx,1)x(bhr e dx,)x(bh)x(bh111 ???????b l ackx,1)x(bhr e dx,)x(bh)x(bh22212 )x(bh ?121)12()12( )x(bh1)x(bh1)x(bh ?????? ??26 2. 證明對(duì)于 RB樹的根 r， 設(shè)其高為 h， bh(r)≥h/2。 這一點(diǎn)由性質(zhì) 3， 即從根到葉的任一條路上 ， red結(jié)點(diǎn)數(shù)不超過一半即可證明 。 3. 由上面兩個(gè)命題可知：高為 h的 RB樹 ， 其內(nèi)部結(jié)點(diǎn)數(shù) n 至少為 ， 即 。 故有 ， 定理得證 。 定理 ， 動(dòng)態(tài)數(shù)據(jù)集上的基本操作在 RB樹上的執(zhí)行代價(jià)為 O(h)=O(logn) 階 。 換句話說 ， 用 RB樹的形式實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)集 ， 在任何時(shí)刻 ， 樹高 h總能保持在 O(logn) 階 。 1212 2/h)x(bh ???2/h)1nl n (21n12n 2/h2/h ????????)1nln (2h ??27 ? RedBlack樹的插入與刪除算法 在插入或刪除結(jié)點(diǎn)時(shí)，為了使樹重新具有 RedBlack性質(zhì)，除了要改變結(jié)點(diǎn)間的指針鏈接關(guān)系外，還要對(duì)某些結(jié)點(diǎn)的著色進(jìn)行調(diào)整。 對(duì)于結(jié)點(diǎn)間指針鏈接關(guān)系的修改歸結(jié)為 旋轉(zhuǎn) （ Rotation）操作，旋轉(zhuǎn)是調(diào)整樹的平衡狀態(tài)的基本手段。 Rotation操作對(duì)二叉搜索樹上的某一局部進(jìn)行調(diào)整，通過交換一對(duì)父子結(jié)點(diǎn)的父子關(guān)系，在保持樹結(jié)點(diǎn)間的有序關(guān)系的條件下（即保持其中序遍歷的結(jié)果為單調(diào)序列），改變?cè)撟訕涞钠胶鉅顟B(tài)。 28 Rotation操作分為左旋（ LeftRotation）和 右旋 (RightRotation)，如 。 29 左旋算法 Left_Rotation(root,x) 。 Right_Rotation(root,x)的算法與 Left_Rotation(root,x)類似 。 30 這個(gè)算法主要完成兩件事： 1176。 把結(jié)點(diǎn) x與其左子結(jié)點(diǎn) y的父子關(guān)系進(jìn)行調(diào)整， 即把 xp— x— y的父子關(guān)系改變?yōu)?xp— y— x的順序； 2176。 把 y的左子樹變?yōu)?x的右子樹。 算法不存在與結(jié)點(diǎn)數(shù) n相關(guān)的操作，因此時(shí)間代價(jià)為 O(1)階。 RB樹的插入操作，首先調(diào)用 Tree_Insert(root,x)函數(shù)完成二叉搜索樹的插入操作，然后調(diào)用 Tree_Rotation()函數(shù)，并對(duì)結(jié)點(diǎn)的著色進(jìn)行調(diào)整，使之恢復(fù)為一個(gè) RB樹。 插入操作算法 RB_Insert(root,x) 31 簡(jiǎn)單的實(shí)例 ， 作為RB_Insert()算法運(yùn)行的示意圖 。 32 從算法 RB_Insert()的執(zhí)行過程可以看出： 1176。 對(duì)于空樹或插入后 xp為 black結(jié)點(diǎn)的情形，無需進(jìn)一步處理； 2176。 xp為 red結(jié)點(diǎn)時(shí)，首先按 case1處理，對(duì)以 xpp為根的子樹進(jìn)行調(diào)整，然后向上擴(kuò)展，分別按 case case3處理。 RB樹的 Delete算法與 RB_Insert()算法的思路是一致的，首先按二叉搜索樹的刪除方法刪去需要?jiǎng)h除的結(jié)點(diǎn)。在刪除過程中會(huì)出現(xiàn)三種情形，在第二、三種情形中，若被摘除（ splicedout）結(jié)點(diǎn)是 black結(jié)點(diǎn)，這時(shí) RedBlack性質(zhì) 4可能被破壞，就需要對(duì) RB樹進(jìn)行恢復(fù)，恢復(fù)方法與插入操作后的修復(fù)類似。 33 ? 關(guān)于 RedBlack樹的幾點(diǎn)討論 1. RB樹是一種二叉搜索樹 ， 在其上進(jìn)行的查詢操作 Search、Minimum、 Maximum、 Successor、 Predecessor等與一般二叉搜索樹的查詢操作完全相同 ， 而且算法簡(jiǎn)明 ， 也即 RB樹具有一般二叉搜索樹的優(yōu)點(diǎn) 。 2. 如定理 ， RB樹是平衡樹 ， 在其上進(jìn)行的所有操作的時(shí)間代價(jià)都是 O(logn)階的 ， RB樹的樹高 h總是保持在一個(gè)很小的范圍 ， 即 h≤2ln(n1) 。 3. RB樹與一般平衡樹的平衡機(jī)制不同 ， 雖然它不需要計(jì)算平衡因子 ， 但 RedBlack性質(zhì) （ 特別是性質(zhì) 4） 保證了整棵樹的平衡性 ， 即絕大多數(shù)內(nèi)部結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn) 。 事實(shí)上 ， red結(jié)點(diǎn)不可能僅有一個(gè) black子結(jié)點(diǎn) ， 而只可能為以下兩種情形之一：有兩個(gè) black（ 數(shù)據(jù) ） 子結(jié)點(diǎn)；或左 、 右子結(jié)點(diǎn)均為 NULL。 34 black結(jié)點(diǎn)的子結(jié)點(diǎn)有三種情形：有兩個(gè) （ 數(shù)據(jù) ） 子結(jié)點(diǎn)；左右子結(jié)點(diǎn)為 NULL；第三種情形只可能出現(xiàn)在樹的下層 ， 只有一個(gè)數(shù)據(jù)子結(jié)點(diǎn) ， 這時(shí)該子結(jié)點(diǎn)必為 red， 且子結(jié)點(diǎn)左右兒子為空 。 如 。 RB樹幾乎是一個(gè) 2樹 ， 不可能出現(xiàn)單鏈的情形 ， 從而保證了整棵樹的平衡性 。 4. 另一種非二叉的平衡搜索樹 —— 234樹 ， 很容易轉(zhuǎn)變?yōu)镽edBlack樹 。 35 234樹 ? 234樹及其實(shí)例 1. 234樹有三種不同的結(jié)點(diǎn)： 2結(jié)點(diǎn)、 3結(jié)點(diǎn)和 4結(jié)點(diǎn)。 ?2結(jié)點(diǎn)與二叉樹的結(jié)點(diǎn)相同，除了關(guān)鍵字域 key外，有三個(gè)指針域 p、 p p2， p指針指向父結(jié)點(diǎn)、 p1指針為左指針、 p2指針為右指針。另外增加一個(gè)結(jié)點(diǎn)類型域 type，用來區(qū)分結(jié)點(diǎn)類型。數(shù)據(jù)域保持?jǐn)?shù)據(jù)元素的內(nèi)容或指向數(shù)據(jù)元素的指針 。 ?3結(jié)點(diǎn)有兩個(gè)關(guān)鍵字域 key1和 key2，其中 key1key2，并增加一個(gè)指針域 p3。當(dāng)搜索結(jié)點(diǎn) x時(shí)，用 xkey與 key key2進(jìn)行比較，如相等即找到，不相等則根據(jù)比較結(jié)果的三種情形轉(zhuǎn)入該結(jié)點(diǎn)的子樹： xkey key1 轉(zhuǎn)向 p1； key1 xkey key2 轉(zhuǎn)向 p2； xkey key2 轉(zhuǎn)向 p3。 36 ?4結(jié)點(diǎn)與 3結(jié)點(diǎn)類似，增加了 key3域和 p4指針。在 234樹種，4結(jié)點(diǎn)是一種臨時(shí)結(jié)點(diǎn)，在插入和刪除過程中可能產(chǎn)生 4結(jié)點(diǎn)，但該結(jié)點(diǎn)可隨時(shí)由三個(gè) 2結(jié)點(diǎn)取代。 2. 234樹的最主要的特征是其所有的葉結(jié)點(diǎn)都在同一深度。如 ： 假定動(dòng)態(tài)數(shù)據(jù)集的關(guān)鍵字值域?yàn)橛⒄Z字母集合，即從小到大為 A,B,C,D,E,...,X,Y,Z。 圖中的結(jié)點(diǎn) I是根，是一個(gè)2結(jié)點(diǎn)，其左子樹中的關(guān)鍵字值均小于 I，右子樹中的關(guān)鍵字值均大于 I，該樹 T中只有 2結(jié)點(diǎn)和 3結(jié)點(diǎn)。 37 ? 234樹上的查詢操作算法 234樹上的搜索算法與二叉搜索樹上的搜索算法差別不大 ，只需要區(qū)別 2結(jié)點(diǎn)和 3結(jié)點(diǎn) 。 234樹的搜索算法 ? 234樹的構(gòu)造過程 234樹的插入算法是保證樹的基本特征 （ 即所有葉結(jié)點(diǎn)在同一深度 ） 的關(guān)鍵 。 在插入時(shí) ， 2結(jié)點(diǎn)可以變?yōu)?3結(jié)點(diǎn) ， 3結(jié)點(diǎn)可以變?yōu)?4結(jié)點(diǎn) ， 當(dāng)出現(xiàn) 4結(jié)點(diǎn)時(shí) ， 自動(dòng)分裂為三個(gè) 2結(jié)點(diǎn) ，并且把中間的 2結(jié)點(diǎn)插入到上一層的父結(jié)點(diǎn)中 。 在一般二叉搜索樹中 ， 每插入一個(gè)結(jié)點(diǎn)是在最下層添加一個(gè)葉結(jié)點(diǎn) ， 而 234樹是在整體擴(kuò)大的情況下進(jìn)行向上擴(kuò)展 。 每當(dāng)樹增加一層時(shí)，即是把根結(jié)點(diǎn)上升一層，于是樹中所有結(jié)點(diǎn)的深度同時(shí)加 1。 38 39 在插入算法中 ， 一旦產(chǎn)生了 4結(jié)點(diǎn)就要進(jìn)行分裂 ， 這時(shí)就會(huì)利用到父結(jié)點(diǎn)指針 p。 在 4結(jié)點(diǎn)分裂時(shí) ， 存在三種情形： (1) 4結(jié)點(diǎn)是 234樹的根，這時(shí)，中間的 2結(jié)點(diǎn)作為新的根，樹增加一層； (2) 4結(jié)點(diǎn)的父結(jié)點(diǎn)是一個(gè) 2結(jié)點(diǎn)，只需把 4結(jié)點(diǎn)中的中間關(guān)鍵字插入到 2結(jié)點(diǎn)，該 2結(jié)點(diǎn)變?yōu)?3結(jié)點(diǎn)； (3) 4結(jié)點(diǎn)的父結(jié)點(diǎn)是一個(gè) 3結(jié)點(diǎn)，把 4結(jié)點(diǎn)的中間關(guān)鍵字插入到這個(gè) 3結(jié)點(diǎn)中，該 3結(jié)點(diǎn)又變成一個(gè)新的 4結(jié)點(diǎn)，于是繼續(xù)向上分裂。 假設(shè)插入時(shí)樹高為 h，插入過程在最壞情形下是從根到葉、再從葉到根，至多進(jìn)行 2h次處理，因此插入算法的時(shí)間代價(jià)仍是 O(h)階的。 40 ? 234樹的性能分析 定理 由 n個(gè)關(guān)鍵字生成的 234樹實(shí)際上是一個(gè)完全的 23樹 ， 設(shè)其高為 h， 結(jié)點(diǎn)數(shù)為 m， 則其結(jié)點(diǎn)數(shù) m介于同樣高度為h的完全二叉樹和完全三叉樹的結(jié)點(diǎn)數(shù)之間 ， 即： 2h+11 ≤ m ≤ (3h+11) / 2 且關(guān)鍵字個(gè)數(shù) n≥m， 故有 n ≥ 2h+11 即 h ≤ ln(n+1)1 或 h =θ(logn) ， 定理得證 。 由定理 ， 234樹上的基本操作的代價(jià)在最壞情形下也是 O(logn)階的 。 ? 有關(guān) 234樹的幾點(diǎn)討論 1. 234樹實(shí)際上是一種 23樹 ， 4結(jié)點(diǎn)是臨時(shí)結(jié)點(diǎn) ， 不會(huì)占用較多空間 ， 可以分配臨時(shí)性的工作單元存放 4結(jié)點(diǎn) 。 41 2. 可以采用同一種數(shù)據(jù)類型來表示 2結(jié)點(diǎn)和 3結(jié)點(diǎn)（按 3結(jié)點(diǎn)來設(shè)計(jì)），只在 type域用不同的標(biāo)記來區(qū)分結(jié)點(diǎn)類型即可。 3. 為了減少插入算法的代價(jià)，還有一種把分裂 4結(jié)點(diǎn)的工作分?jǐn)偟讲煌牟僮髦腥サ姆桨?，即每次生?4結(jié)點(diǎn)時(shí)進(jìn)行一次分裂，如果其父結(jié)點(diǎn)又變?yōu)?4結(jié)點(diǎn)，則不在這一次插入操作中繼續(xù)分裂。當(dāng)進(jìn)行下次插入或搜索操作時(shí)，每遇到一個(gè)4結(jié)點(diǎn)就進(jìn)行一次分裂，這樣可以減少一次插入操作的代價(jià)。 4. 與插入算法相比，刪除操作 Delete算法是一個(gè)逆過程。插入操作中，關(guān)鍵字要按規(guī)則逐層向上插入，而刪除操作應(yīng)在刪除其關(guān)鍵字后按一定規(guī)則逐層向下壓， 42 5. 234樹獲得平衡性的方法很巧妙 ， 但缺點(diǎn)是結(jié)點(diǎn)類型較為復(fù)雜 ， 可以通過一種簡(jiǎn)單的變換把 234樹轉(zhuǎn)化為二叉搜索樹 。方法是把 234樹中的 3結(jié)點(diǎn) （ 或 4結(jié)點(diǎn) ） 用一個(gè) 2結(jié)點(diǎn)結(jié)構(gòu)來取代 ， 取代的方法如 。 43 用上述變換將 234樹轉(zhuǎn)化為一個(gè)二叉搜索樹 ， 不難發(fā)現(xiàn) ， 這是一棵 RB樹 。 從中也可以看出 RB樹與 234樹的內(nèi)在聯(lián)系 。 44 Hashing技術(shù) ? Hash算法的基本思想與一般模型 Hash方法的基本思想是，首先產(chǎn)生從可能的關(guān)鍵字集合（又稱全域） U=[0..N1]到存儲(chǔ)空間（