數(shù)據(jù)結(jié)構(gòu)課件：紅黑樹（補充）

紅黑樹（補充）清華大學(xué)計算機系《數(shù)據(jù)結(jié)構(gòu)》課件

2-3樹

定義 一棵2-3樹或為空樹，或是具有下列性質(zhì)的搜索樹：每個內(nèi)結(jié)點是一個2-結(jié)點或3-結(jié)點。2-結(jié)點有一個數(shù)據(jù)元素；3-結(jié)點有兩個數(shù)據(jù)元素。2-結(jié)點中子女指針為leftChild和midChild，其數(shù)據(jù)元素為dataL，關(guān)鍵碼為dataL.key。 根為leftChild的2-3子樹（若非空）中所有數(shù)據(jù)元素的關(guān)鍵碼值都小于dataL.key，根為

midChild

的2-3子樹（若非空）中的所有數(shù)據(jù)元素的關(guān)鍵碼值都大于dataL.key。3-結(jié)點的子女指針為leftChild、midChild、rightChild，其數(shù)據(jù)元素為dataL和dataR，則dataL.key＜dataR.key。 根為leftChild

的2-3子樹（若非空）中的所有數(shù)據(jù)元素的關(guān)鍵碼值都小于dataL.key，根為midChild的2-3子樹（若非空）中所有數(shù)據(jù)元素的關(guān)鍵碼值都介于dataL.key和dataR.key之間，根為rightChild

的2-3子樹（若非空）中所有數(shù)據(jù)元素的關(guān)鍵碼值都大于dataR.key。所有外結(jié)點都在同一層次，它們代表搜索失敗到達(dá)的虛擬結(jié)點，指向它們的指針為空。在一棵高度為h（即外結(jié)點在h+1層上）的2-3樹中，數(shù)據(jù)元素個數(shù)在2h-l和3h-l之間。

102040BA80C3-結(jié)點2-結(jié)點外結(jié)點當(dāng)每個內(nèi)結(jié)點都是2-結(jié)點時，元素個數(shù)為2h-l，當(dāng)每個內(nèi)結(jié)點都是3-結(jié)點時，元素個數(shù)為3h-l。如果一棵2-3樹既有2-結(jié)點又有3-結(jié)點，則它所擁有的元素個數(shù)將是2h-l和3h-l之間。具有n個數(shù)據(jù)元素的2-3樹的高度在log2(n+1)

和log3(n+1)

之間。

4080201020405030607080定義 一棵234樹或者是一棵空樹，或者是一棵具有下列性質(zhì)的搜索樹：每個內(nèi)結(jié)點是一個2結(jié)點或3結(jié)點或4結(jié)點。一個2結(jié)點包含一個數(shù)據(jù)元素，一個3結(jié)點包含兩個數(shù)據(jù)元素，而一個4結(jié)點包含三個數(shù)據(jù)元素。4-結(jié)點的構(gòu)造2-3-4樹

dataL

dataM

dataRleftChild

leftmidChild

rightmidChild

rightChild

3-結(jié)點的構(gòu)造

2-結(jié)點的構(gòu)造其他規(guī)定與2-3樹類似。它的外結(jié)點也在同一層次且不計入高度，它們都是虛擬結(jié)點，指向它們的指針都是空。dataLleftChild

leftmidChilddataL

dataMleftChild

leftmidChild

rightmidChild如果一棵高度為h的234樹僅有2結(jié)點，則它包含2hl個數(shù)據(jù)元素。如果它僅有4結(jié)點，則數(shù)據(jù)元素個數(shù)是4hl。一棵高度為h并同時具有2結(jié)點、3結(jié)點和4結(jié)點的234樹，其數(shù)據(jù)元素個數(shù)在2hl和4hl之間。即是說，具有n個數(shù)據(jù)元素的234樹的高度在log4(n+1)

和log2(n+1)

之間。有趣的是，可以把234樹作為二叉樹（稱為紅黑樹）有效地表示。這樣做更有效地利用了空間。

紅黑樹

紅黑樹是2-3-4樹的二叉樹表示。在紅黑樹中，一個結(jié)點的子女指針分為兩類：紅指針和黑指針。如果子女指針是在原來的2-3-4樹中已有的指針，則它是黑指針。否則，它是紅指針。

enumColor{red,black}; template<classT>struct

RedBlackNode{ Element<T>data;

RedBlackNode<T>*LeftChild,*RightChild; ColorLeftColor,RightColor; };

把2-3-4樹變換成紅黑樹的規(guī)則2-結(jié)點變換為相應(yīng)的紅黑樹結(jié)點

用兩個紅黑樹結(jié)點表示一個3-結(jié)點，把這兩個紅黑樹結(jié)點用一個紅指針連接起來。

xpxabxabxypxabcxabycxabyc或用三個紅黑樹結(jié)點表示一個4-結(jié)點，用紅指針把一個紅黑樹結(jié)點和其余兩個紅黑樹結(jié)點連接起來

xabydzcxyzpxabcd50107080603040758590925795040608079075309285107095也可使用另一種結(jié)點結(jié)構(gòu)代替上面定義的結(jié)點結(jié)構(gòu)，在這種替代的結(jié)點結(jié)構(gòu)中每個結(jié)點只有一個顏色（color）數(shù)據(jù)成員，它記下了其父結(jié)點指向該結(jié)點的指針的顏色。如果一個結(jié)點有從它父結(jié)點指向它的紅指針，則該結(jié)點是紅結(jié)點；如果是黑指針，則該結(jié)點是黑結(jié)點。根結(jié)點是黑結(jié)點。紅黑樹（Red-BlackTree）是這樣的一棵二叉搜索樹：樹中的每一個結(jié)點的顏色不是黑色就是紅色?？梢园岩豢眉t黑樹視為一棵擴充二叉樹，用外結(jié)點表示空指針。其特性描述如下：50406080790753092851070955040608079075309285107095可以把一棵紅黑樹視為一棵擴充二叉樹，用外結(jié)點表示空指針。其特性描述如下：P1：根結(jié)點和所有外結(jié)點的顏色是黑色。P2：每條從根到外結(jié)點的路徑上都有相同數(shù)目的黑結(jié)點或黑指針（這可由下述事實推導(dǎo)出來：原來的2-3-4樹的所有外部結(jié)點都在同一層次上，而且黑指針代表原有的指針）。P3：從根結(jié)點到外結(jié)點的途中沒有連續(xù)兩個結(jié)點的顏色是紅色，即任何一條從根到外結(jié)點的路徑上都沒有兩個或更多個連續(xù)的紅指針。

紅黑樹的性質(zhì)樹中的每一個結(jié)點x都有一個黑高度，它是指從結(jié)點x出發(fā)（不包括結(jié)點x），到達(dá)外結(jié)點的任一路徑上的黑結(jié)點的個數(shù)。黑高度也稱結(jié)點x的層級(rank)，記作bh(x)。紅黑樹的黑高度定義為其根結(jié)點的黑高度。當(dāng)且僅當(dāng)一棵二叉搜索樹具有下列性質(zhì)時，它才是一棵紅―黑樹：Q1：每個外結(jié)點的黑高度都是0。

Q2：作為外結(jié)點雙親的每個內(nèi)結(jié)點x的黑高度都是bh(x)=l。紅黑樹的黑高度Q3：對于每一個雙親為p(x)的結(jié)點x來說，都有bh(x)≤bh(p(x))≤bh(x)+1。Q4：對每一個祖父為gp(x)的結(jié)點x來說，都有bh(x)＜bh(gp(x))。設(shè)樹的黑高度為r，則樹中至少有2r-1個結(jié)點。Bh()=0Bh()=1Bh()=2Bh()=250607020103040結(jié)論1設(shè)從根到外結(jié)點的路徑長度（PathLength，PL）為該路徑上指針的個數(shù)，如果P與Q是紅黑樹中的兩條從根到外結(jié)點的路徑，則有：PL(P)≤2PL(Q)50607020103040考查任意一棵紅黑樹。設(shè)根結(jié)點的黑高度bh(root)=r。如果原2-3-4樹每個結(jié)點都是2-結(jié)點，則對應(yīng)紅黑樹的黑高度就是原2-3-4樹的高度，恰好等于從根到外結(jié)點的路徑長度r。另一方面，由特性P1知，每條從根結(jié)點到外結(jié)點的路徑中最后一個指針為黑色；從特性P3知，不存在有連續(xù)兩個紅色指針的路徑。因此，每個紅色指針后面都會跟隨一個黑色指針，從根到外部結(jié)點的黑、紅指針個數(shù)最多等于2r。由此，每條從根到外結(jié)點的路徑上都有r～2r個指針，綜上所述，有PL(P)≤2PL(Q)。結(jié)論2

設(shè)h是一棵紅黑樹的高度（不包括外結(jié)點），n是樹中內(nèi)結(jié)點的個數(shù)，r是根結(jié)點的黑高度，則以下關(guān)系式成立：h≤2rn≥2r-1h≤2log2(n+1)從結(jié)論1的證明可知，從根到任一外結(jié)點的路徑長度不超過2r，同時從樹的定義可知，樹的高度即為根結(jié)點的高度，等于從根到離根最遠(yuǎn)的外結(jié)點的路徑的長度，因此有h≤2r。

因為紅黑樹的黑高度為r，則從樹的第1層到第r層沒有外結(jié)點，在這些層中有2r-1個內(nèi)結(jié)點，就是說，內(nèi)結(jié)點的總數(shù)至少為2r-1。例如，如果在對應(yīng)2-3-4樹中都是2-結(jié)點，轉(zhuǎn)換為紅黑樹后