高度平衡的二叉樹課件

1、高度平衡的二叉搜索樹AVL( Addison-Velski and Landis )樹伸展樹紅黑樹第1頁(yè)，共79頁(yè)。 二叉搜索樹性能分析對(duì)于有 n 個(gè)關(guān)鍵碼的集合，其關(guān)鍵碼有 n! 種不同排列，可構(gòu)成不同二叉搜索樹有 (棵) 2, 1, 3 1, 2, 3 1, 3, 2 2, 3, 1 3, 1, 2 3, 2, 1 123111132223323第2頁(yè)，共79頁(yè)。同樣 3 個(gè)數(shù)據(jù) 1, 2, 3 ，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。如果輸入序列選得不好，會(huì)建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大。用樹的搜索效率來評(píng)價(jià)這些二叉搜索樹。為此

2、，在二叉搜索樹中加入外結(jié)點(diǎn)，形成判定樹。外結(jié)點(diǎn)表示失敗結(jié)點(diǎn)，內(nèi)結(jié)點(diǎn)表示搜索樹中已有的數(shù)據(jù)。這樣的判定樹即為擴(kuò)充的二叉搜索樹。第3頁(yè)，共79頁(yè)。舉例說明。已知關(guān)鍵碼集合 a1, a2, a3 = do, if, to，對(duì)應(yīng)搜索概率p1, p2, p3, 在各搜索不成功間隔內(nèi)搜索概率分別為q0, q1, q2, q3?？赡艿亩嫠阉鳂淙缦滤?。doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)第4頁(yè)，共79頁(yè)。判定樹doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)第5

3、頁(yè)，共79頁(yè)。在判定樹中 表示內(nèi)部結(jié)點(diǎn)，包含了關(guān)鍵碼集合中的某一個(gè)關(guān)鍵碼； 表示外部結(jié)點(diǎn)，代表各關(guān)鍵碼間隔中的不在關(guān)鍵碼集合中的關(guān)鍵碼。在每?jī)蓚€(gè)外部結(jié)點(diǎn)間必存在一個(gè)內(nèi)部結(jié)點(diǎn)。一棵判定樹上的搜索成功的平均搜索長(zhǎng)度ASLsucc可以定義為該樹所有內(nèi)部結(jié)點(diǎn)上的搜索概率pi與搜索該結(jié)點(diǎn)時(shí)所需的關(guān)鍵碼比較次數(shù)ci (= li, 即結(jié)點(diǎn)所在層次) 乘積之和：第6頁(yè)，共79頁(yè)。設(shè)各關(guān)鍵碼的搜索概率相等：pi = 1/n搜索不成功的平均搜索長(zhǎng)度ASLunsucc為樹中所有外部結(jié)點(diǎn)上搜索概率qj與到達(dá)外部結(jié)點(diǎn)所需關(guān)鍵碼比較次數(shù)cj(= lj)乘積之和：設(shè)外部結(jié)點(diǎn)搜索概率相等：qj = 1/(n+1)：第7頁(yè)，共

4、79頁(yè)。設(shè)樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率都相等： pi = 1/3, 1i3, qj = 1/4, 0 j3 圖(a): ASLsucc = 1/3*3+1/3*2+1/3*1 = 6/3, ASLunsucc = 1/4*3*2+1/4*2+1/4*1 = 9/4。 圖(b): ASLsucc = 1/3*2*2+1/3*1 = 5/3, ASLunsucc = 1/4*2*4 = 8/4。 圖(c): ASLsucc = 1/3*1+1/3*2+1/3*3 = 6/3, ASLunsucc = 1/4*1+1/4*2+1/4*3*2 = 9/4。 圖(d): ASLsucc = 1/3*2

5、+1/3*3+1/3*1 = 6/3, ASLunsucc = 1/4*2+1/4*3*2+1/4*1 = 9/4。(1) 相等搜索概率的情形第8頁(yè)，共79頁(yè)。圖(e): ASLsucc = 1/3*1+1/3*3+1/3*2 = 6/3, ASLunsucc = 1/4*1+1/4*3*2+1/4*2 = 9/4。圖(b)的情形所得的平均搜索長(zhǎng)度最小。第9頁(yè)，共79頁(yè)。設(shè)二叉搜索樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率互不相等。 p1 = 0.5, p2 = 0.1, p3 = 0.05 q0 = 0.15, q1 = 0.1, q2 = 0.05, q3 = 0.05分別計(jì)算各個(gè)可能的擴(kuò)充二叉搜索樹

6、的搜索性能，判斷哪些擴(kuò)充二叉搜索樹的平均搜索長(zhǎng)度最小。(2) 不相等搜索概率的情形第10頁(yè)，共79頁(yè)。doiftodoiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05q0=0.15q1=0.1q2=0.05q3= 0.05p1=0.5p2=0.1p3=0.05(a)(b)圖(a): ASLsucc = 0.5*3+0.1*2+0.05*1 = 1.75， ASLunsucc = 0.15*3+0.1*3+0.05*2+ 0.05*1 = 0.9。圖(b): ASLsucc = 0.5*2+0.1*1+0.05*2 = 1.2， ASLunsu

7、cc = (0.15+0.1+0.05+0.05)*2 = 0.7。第11頁(yè)，共79頁(yè)。doifto q0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(d)(c)圖(c): ASLsucc = 0.5*1+0.1*2+0.05*3 = 0.85, ASLunsucc = 0.15*1+0.1*2+0.05*3+0.05*3 = 0.75.圖(d) : ASLsucc = 0.5*2+0.1*3+0.05*1 = 1.35, ASLunsucc =

8、0.15*2+0.1*3+0.05*3+0.05*1 = 0.8.第12頁(yè)，共79頁(yè)。由此可知，圖(c)和圖(e)的情形下樹的平均搜索長(zhǎng)度達(dá)到最小，因此，圖(c)和圖(e)的情形是最優(yōu)二叉搜索樹。doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(e) 圖(e) : ASLsucc = 0.5*1+ 0.1*3+0.05*2 = 0.9; ASLunsucc = 0.15*1+ 0.1*3+0.05*3+0.05*2 = 0.7;第13頁(yè)，共79頁(yè)。一般把平均搜索長(zhǎng)度達(dá)到最小的擴(kuò)充的二叉搜索樹稱作最優(yōu)二叉搜索樹。等概率條件下，最優(yōu)二叉搜索樹

9、的最短內(nèi)部路徑長(zhǎng)度與最短外部路徑長(zhǎng)度, 課本383頁(yè):第14頁(yè)，共79頁(yè)。 一、什么是平衡二叉樹 二、失衡二叉排序樹的分析與調(diào)整 平衡二叉樹第15頁(yè)，共79頁(yè)。平衡二叉樹又稱為AVL樹。 一棵平衡二叉樹或者是空樹，或者是具有下列性質(zhì)的二叉排序樹： 左子樹與右子樹的高度之差的絕對(duì)值小于等于1； 左子樹和右子樹也是平衡二叉排序樹。第16頁(yè)，共79頁(yè)。例：平衡二叉樹40247053452860 引入平衡二叉樹的目的是為了提高查找效率， 使其平均查找長(zhǎng)度為O(log2n)。402470532860第17頁(yè)，共79頁(yè)。 根據(jù)平衡二叉樹的定義， 平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只能是-1、 0，或1。當(dāng)我們

10、在一個(gè)平衡二叉排序樹上插入一個(gè)結(jié)點(diǎn)時(shí)，有可能導(dǎo)致失衡，即出現(xiàn)絕對(duì)值大于1的平衡因子，如2、-2。 為了方便起見，給每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)左子樹與右子樹的高度差。這個(gè)數(shù)字稱為結(jié)點(diǎn)的平衡因子。第18頁(yè)，共79頁(yè)。40247053452860402470532860例：下圖對(duì)平衡二叉樹和失去平衡的二叉排序樹分別標(biāo)注了平衡因子。01-1-100-110-1-20-1第19頁(yè)，共79頁(yè)。 一、什么是平衡二叉樹 二、失衡二叉排序樹的分析與調(diào)整 平衡二叉樹第20頁(yè)，共79頁(yè)。 如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)

11、。現(xiàn)分別介紹這四種平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類： LL平衡旋轉(zhuǎn) RR平衡旋轉(zhuǎn) LR平衡旋轉(zhuǎn) RL平衡旋轉(zhuǎn)第21頁(yè)，共79頁(yè)。 若在A的左子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）1）LL平衡旋轉(zhuǎn)：ABCABC第22頁(yè)，共79頁(yè)。右單旋轉(zhuǎn) (RotateRight )hhhACEBD(a) (b) (c)hh+1BACEDhhh+1CEABD在左子樹D上插入新結(jié)點(diǎn)使其高度增1，導(dǎo)致結(jié)點(diǎn)A的平衡因子增到 -2，造成了不平衡。為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3個(gè)結(jié)點(diǎn)A、B和D，它們處于一條方向?yàn)椤?”的直線上，需要做右單旋轉(zhuǎn)。以結(jié)點(diǎn)B為旋轉(zhuǎn)軸

12、，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)。h000-1-1-2第23頁(yè)，共79頁(yè)。 左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹上進(jìn)行的調(diào)整）的情況分析：1、LL 情況：（LL：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的 左子樹的左子樹上）AB+1h-10+2+1hh-1h-1LL 改組BLBRARBA0h0h-1h-1BLBRAR危機(jī)結(jié)點(diǎn)改組前：高度為 h + 1 中序序列：ABBLBRAR改組后：高度為 h + 1 中序序列：ABBLBRAR注意：改組后 平衡度為 0AB第24頁(yè)，共79頁(yè)。 若在A的右子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABC第

13、25頁(yè)，共79頁(yè)。左單旋轉(zhuǎn) (RotateLeft )hhhACEBD(a) (b) (c)hhh+1BACEDhhh+1CEABD如果在子樹E中插入一個(gè)新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成+2，出現(xiàn)不平衡。沿插入路徑檢查三個(gè)結(jié)點(diǎn)A、C和E。它們處于一條方向?yàn)椤啊钡闹本€上，需要做左單旋轉(zhuǎn)。以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)。+1+20+100第26頁(yè)，共79頁(yè)。 若在A的左子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要先進(jìn)行逆時(shí)針旋轉(zhuǎn)，再順時(shí)針旋轉(zhuǎn)。 (以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）ABCABCABC3）LR平衡旋轉(zhuǎn)：第27頁(yè)，共79頁(yè)。2、LR 情況：（LR：表示新插入結(jié)點(diǎn)在

14、危機(jī)結(jié)點(diǎn)的 左子樹的右子樹上） 情況A：AB+1h-10+2-1h-1LR 改組BLAR危機(jī)結(jié)點(diǎn)改組前： 高度為 h + 1 中序序列：注意：改組后 平衡度為 0,0,-1CBCCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR改組后： 高度為 h + 1 中序序列：ABBLARCCLCRA第28頁(yè)，共79頁(yè)。Double RotationsFig. 28-7 (a) The AVL tree in Fig. 28-5 after additions that maintain its balance; (b) after an add

15、ition that destroys the balance continued 第29頁(yè)，共79頁(yè)。Double RotationsFig. 28-7 (ctd.) (c) after a left rotation; (d) after a right rotation.第30頁(yè)，共79頁(yè)。若在A的右子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要先進(jìn)行順時(shí)針旋轉(zhuǎn)，再逆時(shí)針旋轉(zhuǎn)。 (以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABCABCABC這種調(diào)整規(guī)則可以保證二叉排序樹的次序不變第31頁(yè)，共79頁(yè)。 綜上所述， 在一個(gè)平衡二叉排序樹上插入一個(gè)新結(jié)點(diǎn)S時(shí)，主要包括以下三步：

16、(1)查找應(yīng)插位置，同時(shí)記錄離插入位置最近的可能失衡結(jié)點(diǎn)A（A的平衡因子不等于0）。 (2)插入新結(jié)點(diǎn)S， 并修改從A到S路徑上各結(jié)點(diǎn)的平衡因子。 (3)根據(jù)A、 B的平衡因子， 判斷是否失衡以及失衡類型， 并做相應(yīng)處理。 第32頁(yè)，共79頁(yè)。Double RotationsFig. 28-5 (a) Adding 70 to the tree in Fig. 28-2c destroys its balance; to restore the balance, perform both (b) a right rotation and (c) a left rotation.第33頁(yè)，共79

17、頁(yè)。013037024例：請(qǐng)將下面序列構(gòu)成一棵平衡二叉排序樹： （ 13，24，37，90，53）013037-113024-124-213需要RR平衡旋轉(zhuǎn)(繞B逆轉(zhuǎn),B為根）090-124-137053190-237需要RL平衡旋轉(zhuǎn)(繞C先順后逆）037090053037090053第34頁(yè)，共79頁(yè)。例如，輸入關(guān)鍵碼序列為 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和調(diào)整過程如下。160163-10左右雙旋731600073110-1116右單旋37169000111163701-273161190-1-223711269160112第35頁(yè)，共79頁(yè)。右左雙旋

18、0左單旋181600732611900031609171126183-1-17161426911127390182611-1161第36頁(yè)，共79頁(yè)。1518231816-2左右雙旋73000117149-1161501112626141-29從空樹開始的建樹過程第37頁(yè)，共79頁(yè)。各種搜索結(jié)構(gòu)的比較課本397頁(yè) 圖10.14第38頁(yè)，共79頁(yè)。作業(yè)1、設(shè)有關(guān)鍵碼序列55，31，11，37，46，73，63，02，07，從空樹開始構(gòu)造平衡二叉搜索樹，畫出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹的形態(tài)。第39頁(yè)，共79頁(yè)。伸展樹（Splaying Tree） 伸展樹、AVL樹、并查集的用雙親表示的樹，都屬于自調(diào)

19、整數(shù)據(jù)結(jié)構(gòu)（self-adjusting data structure）。AVL樹使得搜索樹保持高度平衡，讓葉結(jié)點(diǎn)只出現(xiàn)在最低的一層或兩層上，從而提高其搜索效率。伸展樹是另一種提高搜索效率的方法，其思路是：?jiǎn)我恍D(zhuǎn)：將經(jīng)常訪問的結(jié)點(diǎn)最終上移到靠近根的地方，使以后的訪問更快。第40頁(yè)，共79頁(yè)。移動(dòng)到根部：假設(shè)正訪問的結(jié)點(diǎn)將以很高的概率再次被訪問，對(duì)它反復(fù)進(jìn)行子女父結(jié)點(diǎn)旋轉(zhuǎn)，直到被訪問的結(jié)點(diǎn)位于根部為止。伸展樹提出了一組改進(jìn)二叉搜索樹性能的一組規(guī)則，每當(dāng)執(zhí)行搜索、插入、刪除等操作時(shí)，就要依據(jù)這些規(guī)則調(diào)整二叉搜索樹，從而保證操作的時(shí)間代價(jià)。每當(dāng)訪問（搜索、插入或刪除）一個(gè)結(jié)點(diǎn) s 時(shí)，伸展樹就執(zhí)行

20、一次叫做“展開(splaying)”的過程，將結(jié)點(diǎn) s 移到二叉搜索樹的根部。 第41頁(yè)，共79頁(yè)。就像AVL樹，一次“展開”由一組旋轉(zhuǎn)組成。旋轉(zhuǎn)有三種類型：?jiǎn)涡D(zhuǎn)、一字形旋轉(zhuǎn)和之字形旋轉(zhuǎn)。一次旋轉(zhuǎn)的目的是通過調(diào)整結(jié)點(diǎn) s 與它的父結(jié)點(diǎn) p 和祖父結(jié)點(diǎn) g 之間位置，把它上移到樹的更高層。被訪問結(jié)點(diǎn) s 的父結(jié)點(diǎn) p 是根結(jié)點(diǎn)。此時(shí)執(zhí)行單旋轉(zhuǎn)。在保持二叉搜索樹特性的情況下，結(jié)點(diǎn) s 成為新的根，原來的根 p 成為它的子女結(jié)點(diǎn)。 第42頁(yè)，共79頁(yè)。同構(gòu)形狀（homogeneous configuration）。結(jié)點(diǎn) s 是其父結(jié)點(diǎn) p 的左子女，結(jié)點(diǎn) p 又是其父結(jié)點(diǎn) g 的左子女()?；蛘呓Y(jié)

21、點(diǎn) s 是其父結(jié)點(diǎn) p 的右子女，結(jié)點(diǎn) p 又是其父結(jié)點(diǎn)g 的右子女()。此時(shí)執(zhí)行一字形旋轉(zhuǎn) (zigzig rotation): pssp右單旋轉(zhuǎn)第43頁(yè)，共79頁(yè)。異構(gòu)的形狀（heterogeneous configuration）。結(jié)點(diǎn) s 是其父結(jié)點(diǎn) p 的左子女，結(jié)點(diǎn) p 又是其父結(jié)點(diǎn) g 的右子女()。或結(jié)點(diǎn) s 是其父結(jié)點(diǎn) p 的右子女，結(jié)點(diǎn) p 又是其父結(jié)點(diǎn) g 的左子女()。此時(shí)執(zhí)行之字形旋轉(zhuǎn)(zigzag rotation)。 pgspgspgs右單旋轉(zhuǎn)右單旋轉(zhuǎn)第44頁(yè)，共79頁(yè)。因?yàn)閯傇L問的結(jié)點(diǎn) s 與其父結(jié)點(diǎn) p 和祖父結(jié)點(diǎn)g 形成折線，需要做與AVL樹一樣的雙旋轉(zhuǎn)，首

22、先圍繞 s 旋轉(zhuǎn) p，再圍繞 s 旋轉(zhuǎn) g，把結(jié)點(diǎn) s上升到祖父結(jié)點(diǎn)的位置，并保持二叉搜索樹的特性。 pgspgssgp左單旋轉(zhuǎn)右單旋轉(zhuǎn)第45頁(yè)，共79頁(yè)。將剛訪問的結(jié)點(diǎn)s上移到樹根部的算法 splaying (g, p, s) /g 是 p 的父結(jié)點(diǎn)，p 是 s 的父結(jié)點(diǎn)/算法將s移到根結(jié)點(diǎn)位置 while (s 不是樹的根結(jié)點(diǎn)) if (s 的父結(jié)點(diǎn)是根結(jié)點(diǎn)) 進(jìn)行單旋轉(zhuǎn), 將 s 調(diào)整為根結(jié)點(diǎn) else if (s 與它的前驅(qū) p, g 是同構(gòu)形狀) 進(jìn)行一字形雙旋轉(zhuǎn)，將 s 上移 else /s 與它的前驅(qū) p, g 是異構(gòu)形狀 進(jìn)行之字形雙旋轉(zhuǎn)，將 s 上移; 第46頁(yè)，共79頁(yè)。伸

23、展樹的性能分析之字形旋轉(zhuǎn)使得樹結(jié)構(gòu)趨向于平衡化，結(jié)果常常使樹結(jié)構(gòu)的高度減少1。而一字形旋轉(zhuǎn)一般不會(huì)降低樹結(jié)構(gòu)的高度，它只是把剛訪問的結(jié)點(diǎn)向根結(jié)點(diǎn)上移。伸展樹不要求每一個(gè)操作都是高效的，對(duì)于一個(gè)有 n 個(gè)結(jié)點(diǎn)的樹，執(zhí)行 m 次操作時(shí)可能一次插入或搜索操作需要花費(fèi)O(n)時(shí)間。例如，對(duì)于一個(gè)有 n 個(gè)結(jié)點(diǎn)的單支樹，訪問最底層的結(jié)點(diǎn)，需要時(shí)間即為O(n)。第47頁(yè)，共79頁(yè)。當(dāng)mn時(shí)，所有m個(gè)操作總共需要O(mlog2n)時(shí)間，從而使每次訪問操作的所花費(fèi)的平均時(shí)間達(dá)到O(log2n)，從整體上保持較高的時(shí)間性能。下面的實(shí)例描述了伸展樹如何通過“展開”實(shí)現(xiàn)自調(diào)整。首先在伸展樹中搜索70，搜索過程與二叉

24、搜索樹完全一樣，一旦搜索成功，就執(zhí)行“展開”過程將該結(jié)點(diǎn)上移到根結(jié)點(diǎn)位置。伸展樹的插入操作與二叉搜索樹相同，但結(jié)點(diǎn)一經(jīng)插入之后立即展開到根結(jié)點(diǎn)。 第48頁(yè)，共79頁(yè)。608030201070409050608030201070409050608030201070409050608030201070409050zigzig雙旋轉(zhuǎn)zigzag雙旋轉(zhuǎn)左單旋轉(zhuǎn)70調(diào)整完第49頁(yè)，共79頁(yè)。從伸展樹中刪除一個(gè)結(jié)點(diǎn)的操作也與二叉搜索樹相同，但需要把被刪結(jié)點(diǎn)的父結(jié)點(diǎn)展開到根結(jié)點(diǎn)。伸展樹與AVL樹在操作上稍有不同。伸展樹的調(diào)整與結(jié)點(diǎn)被訪問（包括搜索、插入、刪除）的頻率有關(guān)，能夠進(jìn)行更合理的調(diào)整。而AVL樹的結(jié)

25、構(gòu)調(diào)整只與插入、刪除的順序有關(guān)，與訪問的頻率無關(guān)。 第50頁(yè)，共79頁(yè)。紅黑樹（Red-Black Tree） 紅黑樹是一棵二叉搜索樹：樹中的每一個(gè)結(jié)點(diǎn)的顏色不是黑色就是紅色。可以把一棵紅黑樹視為一棵擴(kuò)充二叉樹，用外部結(jié)點(diǎn)表示空指針。其特性描述如下：特性1：根結(jié)點(diǎn)和所有外部結(jié)點(diǎn)的顏色是黑色。特性2：從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的途中沒有連續(xù)兩個(gè)結(jié)點(diǎn)的顏色是紅色。特性3：所有從根到外部結(jié)點(diǎn)的路徑上都有相同數(shù)目的黑色結(jié)點(diǎn)。 第51頁(yè)，共79頁(yè)。從紅黑樹中任一結(jié)點(diǎn) x 出發(fā)(不包括結(jié)點(diǎn) x )，到達(dá)一個(gè)外部結(jié)點(diǎn)的任一路徑上的黑結(jié)點(diǎn)個(gè)數(shù)叫做結(jié)點(diǎn) x 的黑高度，稱為結(jié)點(diǎn)的階(rank)，記作 bh(x)。紅黑樹的

26、黑高度定義為其根結(jié)點(diǎn)的黑高度。501030204060702050紅色結(jié)點(diǎn)黑色結(jié)點(diǎn)外部結(jié)點(diǎn)第52頁(yè)，共79頁(yè)。另一種等價(jià)的定義是看結(jié)點(diǎn)指針的顏色。從父結(jié)點(diǎn)到黑色子女結(jié)點(diǎn)的指針為黑色的，從父結(jié)點(diǎn)到紅色子女結(jié)點(diǎn)的指針為紅色的。50103020406070第53頁(yè)，共79頁(yè)。特性1：從內(nèi)部結(jié)點(diǎn)指向外部結(jié)點(diǎn)的指針是黑色的。特性2：從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的途中沒有兩個(gè)連續(xù)的紅色指針。特性3：所有根到外部結(jié)點(diǎn)的路徑上都有相同數(shù)目的黑色指針。如果知道指針的顏色，就能推斷結(jié)點(diǎn)的顏色，反之亦然。設(shè)從根到外部結(jié)點(diǎn)的路徑長(zhǎng)度 (Path Length, PL) 為該路徑上指針的個(gè)數(shù)， 第54頁(yè)，共79頁(yè)。結(jié)論1 如果P

27、與Q是紅黑樹中的兩條從根到外部結(jié)點(diǎn)的路徑，則有：PL(P)2PL(Q)證明：考查任意一棵紅黑樹。假設(shè)根結(jié)點(diǎn)的黑高度bh(root) = r。由特性1可知，每條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑中最后一個(gè)指針為黑色；從特性2可知，不存在有連續(xù)兩個(gè)紅色指針的路徑。因此，每個(gè)紅色指針后面都會(huì)跟隨一個(gè)黑色指針，每條從根到外部結(jié)點(diǎn)的路徑上都有r2r個(gè)指針，綜上所述有 PL(P)2PL(Q)。第55頁(yè)，共79頁(yè)。如上圖，從根到 40 左下的外部結(jié)點(diǎn)的路徑長(zhǎng)度PL(40) = 4，從根到70右下的外部結(jié)點(diǎn)的路徑長(zhǎng)度PL(70) = 3，因此PL(40)PL(70)或者PL(70)PL(40)。 50103020406

28、070PL=4, bh=2 PL=3, bh=2第56頁(yè)，共79頁(yè)。結(jié)論2 設(shè) h 是一棵紅黑樹的高度( 不包括外部結(jié)點(diǎn))，n 是樹中內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)，r 是根結(jié)點(diǎn)的黑高度，則以下關(guān)系式成立：(1) h2r (2) n2r-1(3) h2log2(n+1)證明：(1) 從結(jié)論1的證明可知，從根到任一外部結(jié)點(diǎn)的路徑長(zhǎng)度不超過2r，同時(shí)從樹的定義可知，樹的高度即為根結(jié)點(diǎn)的高度，等于從根到離根最遠(yuǎn)的外部結(jié)點(diǎn)的路徑的長(zhǎng)度，有h2r。第57頁(yè)，共79頁(yè)。(2) 因?yàn)榧t黑樹的黑高度為r，則從樹的第 1 層到第 r 層沒有外部結(jié)點(diǎn)，在這些層中有2r-1個(gè)內(nèi)部結(jié)點(diǎn)，即內(nèi)部結(jié)點(diǎn)的總數(shù)至少為2r-1。(3) 由(2

29、)可得rlog2(n+1)，結(jié)合(1)，有h2log2(n+1)。由于紅黑樹的高度最大為2log2(n+1)，所以搜索、插入、刪除操作的時(shí)間復(fù)雜性為O(log2n)。注意，最差情況下的紅黑樹的高度大于最差情況下具有相同結(jié)點(diǎn)個(gè)數(shù)的AVL樹的高度（近似于1.44*log2(n+2)）。第58頁(yè)，共79頁(yè)。紅黑樹的搜索 由于每一棵紅黑樹都是二叉搜索樹，可以使用二叉搜索樹的算法進(jìn)行搜索。在搜索過程中不需使用顏色信息。對(duì)普通二叉搜索樹進(jìn)行搜索的時(shí)間復(fù)雜性為O(h)，對(duì)于紅黑樹則為O(log2n)。因?yàn)樵谒阉鞫嫠阉鳂?、AVL樹和紅黑樹時(shí)使用了相同算法。在最差情況下AVL樹的高度最小，因此，在那些以搜索操

30、作為主的應(yīng)用程序中，最差情況下AVL樹能獲得最優(yōu)時(shí)間復(fù)雜性。 第59頁(yè)，共79頁(yè)。紅黑樹的插入 首先使用二叉搜索樹的插入算法將一個(gè)元素插入到紅黑樹中，該元素將作為新的葉結(jié)點(diǎn)插入。在插入過程中需要為新元素染色。如果插入前是空樹，則那么新元素將成為根結(jié)點(diǎn)，根據(jù)特征1，根結(jié)點(diǎn)必須染成黑色。第60頁(yè)，共79頁(yè)。如果插入前樹非空，若新結(jié)點(diǎn)被染成黑色，將違反紅黑樹的特性3，所有從根到外部結(jié)點(diǎn)的路徑上的黑色結(jié)點(diǎn)個(gè)數(shù)不等。因此，新插入的結(jié)點(diǎn)將染成紅色，但這又可能違反紅黑樹的特性2，出現(xiàn)連續(xù)兩個(gè)紅色結(jié)點(diǎn)，因此需要重新平衡。guuL插入第61頁(yè)，共79頁(yè)。設(shè)新插入的結(jié)點(diǎn)為u，它的父結(jié)點(diǎn)和祖父結(jié)點(diǎn)分別是pu和gu，

31、現(xiàn)在來考查不平衡的類型。若pu是黑色結(jié)點(diǎn)，則特性2沒有破壞，結(jié)束重新平衡的過程。若pu是紅色結(jié)點(diǎn)，則出現(xiàn)連續(xù)兩個(gè)紅色結(jié)點(diǎn)的情形，這時(shí)還要考查pu的兄弟結(jié)點(diǎn)。插入puguugr第62頁(yè)，共79頁(yè)。1)如果pu的兄弟結(jié)點(diǎn)gr是紅色結(jié)點(diǎn)，此時(shí)結(jié)點(diǎn)pu的父結(jié)點(diǎn)gu是黑色結(jié)點(diǎn)，它有兩個(gè)紅色子女結(jié)點(diǎn)。交換結(jié)點(diǎn)gu和它的子女結(jié)點(diǎn)的顏色，將可能破壞紅黑樹特性2的紅色結(jié)點(diǎn)上移。puguugrpuguugruLuRpuRgrLgrRuLuRpuRgrLgrR第63頁(yè)，共79頁(yè)。2)如果pu的兄弟結(jié)點(diǎn)gr是黑色結(jié)點(diǎn)，此時(shí)又有兩種情況。 u是pu的左子女，pu是gu的左子女。在這種情況下只要做一次右單旋轉(zhuǎn)，交換一下p

32、u和gu的顏色，就可恢復(fù)紅黑樹的特性，并結(jié)束重新平衡過程。pugugrupugugruuLuRpuRgrLgrRuLuRpuRgrLgrR第64頁(yè)，共79頁(yè)。 u是pu的右子女，pu是gu的左子女。在這種情況下做一次先左后右的雙旋轉(zhuǎn)，再交換一下u與gu的顏色，就可恢復(fù)紅黑樹的特性，結(jié)束重新平衡過程。 puL gupuugrgrL grR uRuLgupuugrgrL grR uRuLpuL 第65頁(yè)，共79頁(yè)。針對(duì)上述兩種情況，還有鏡像情況，即pu是gu的右子女時(shí)，當(dāng)u是pu的右子女則做左單旋轉(zhuǎn)，當(dāng)u是pu的左子女則做先右后左的雙旋轉(zhuǎn)。紅黑樹的刪除算法與二叉搜索樹的刪除算法類似，不同之處在于，

33、在紅黑樹中執(zhí)行一次二叉搜索樹的刪除運(yùn)算，可能會(huì)破壞紅黑樹的特性，需要重新平衡。紅黑樹的刪除第66頁(yè)，共79頁(yè)。在紅黑樹中真正刪除的結(jié)點(diǎn)應(yīng)是葉結(jié)點(diǎn)或只有一個(gè)子女的結(jié)點(diǎn)。如果被刪結(jié)點(diǎn)p是紅色的，刪去它樹中各結(jié)點(diǎn)的黑高度都沒有改變，也不會(huì)出現(xiàn)連續(xù)兩個(gè)紅色結(jié)點(diǎn)，紅黑樹的特性仍然保持，不需執(zhí)行重新平衡過程。pvguuL uR vRvL vguuL uR vRvL 直接刪除第67頁(yè)，共79頁(yè)。如果被刪結(jié)點(diǎn)p是黑色的，一旦刪去它，紅黑樹將不滿足特性3的要求，因?yàn)樵谶@條路徑上黑色結(jié)點(diǎn)少了一個(gè)，從根到外部結(jié)點(diǎn)的黑高度將會(huì)降低?？梢詫⒔Y(jié)點(diǎn)u視為具有雙重黑色的結(jié)點(diǎn)，這樣任意包含結(jié)點(diǎn)u的路徑上的黑高度仍保持刪除前的值，就能恢復(fù)紅黑樹的特性。問題是在紅黑樹的定義中沒有包括雙重黑色的結(jié)點(diǎn)，因此必須通過旋轉(zhuǎn)變換和改變結(jié)點(diǎn)的顏色，消除雙重黑色結(jié)點(diǎn)，恢復(fù)紅黑樹的特性。第68頁(yè)，共79頁(yè)。設(shè)u是被刪結(jié)點(diǎn)p的唯一子女結(jié)點(diǎn)。如果結(jié)點(diǎn)u是紅色結(jié)點(diǎn)，可以把u染成黑色，從而恢復(fù)紅黑樹的特性。pugvugv第69頁(yè)，共79頁(yè)。如果被刪結(jié)點(diǎn)p是黑色結(jié)點(diǎn)，它的唯一的子女結(jié)點(diǎn)u也是黑色結(jié)