數(shù)據(jù)結構課件：紅黑樹（補充）

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

2-3樹

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

midChild

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

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

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

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

和log3(n+1)

之間。

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

dataL

dataM

dataRleftChild

leftmidChild

rightmidChild

rightChild

3-結點的構造

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

leftmidChilddataL

dataMleftChild

leftmidChild

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

和log2(n+1)

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

紅黑樹

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

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

RedBlackNode{ Element<T>data;

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

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

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

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

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

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

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

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

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