高度平衡的二叉樹

1、高度平衡的二叉樹第1頁，共79頁，2022年，5月20日，20點22分，星期四 二叉搜索樹性能分析對于有 n 個關(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頁，共79頁，2022年，5月20日，20點22分，星期四同樣 3 個數(shù)據(jù) 1, 2, 3 ，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。如果輸入序列選得不好，會建立起一棵單支樹，使得二叉搜索樹的高度達到最大。用樹的搜索效率來評價這些二叉搜索樹

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

3、toq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)第5頁，共79頁，2022年，5月20日，20點22分，星期四在判定樹中 表示內(nèi)部結(jié)點，包含了關(guān)鍵碼集合中的某一個關(guān)鍵碼； 表示外部結(jié)點，代表各關(guān)鍵碼間隔中的不在關(guān)鍵碼集合中的關(guān)鍵碼。在每兩個外部結(jié)點間必存在一個內(nèi)部結(jié)點。一棵判定樹上的搜索成功的平均搜索長度ASLsucc可以定義為該樹所有內(nèi)部結(jié)點上的搜索概率pi與搜索該結(jié)點時所需的關(guān)鍵碼比較次數(shù)ci (= li, 即結(jié)點所在層次) 乘積之和：第6頁，共79頁，2022年，5月20日，20點22分，星期四設(shè)各關(guān)鍵碼的搜索概率相等：pi = 1/n搜索不成功

4、的平均搜索長度ASLunsucc為樹中所有外部結(jié)點上搜索概率qj與到達外部結(jié)點所需關(guān)鍵碼比較次數(shù)cj(= lj)乘積之和：設(shè)外部結(jié)點搜索概率相等：qj = 1/(n+1)：第7頁，共79頁，2022年，5月20日，20點22分，星期四設(shè)樹中所有內(nèi)、外部結(jié)點的搜索概率都相等： 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

5、*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+1/3*3+1/3*1 = 6/3, ASLunsucc = 1/4*2+1/4*3*2+1/4*1 = 9/4。(1) 相等搜索概率的情形第8頁，共79頁，2022年，5月20日，20點22分，星期四圖(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)的情

6、形所得的平均搜索長度最小。第9頁，共79頁，2022年，5月20日，20點22分，星期四設(shè)二叉搜索樹中所有內(nèi)、外部結(jié)點的搜索概率互不相等。 p1 = 0.5, p2 = 0.1, p3 = 0.05 q0 = 0.15, q1 = 0.1, q2 = 0.05, q3 = 0.05分別計算各個可能的擴充二叉搜索樹的搜索性能，判斷哪些擴充二叉搜索樹的平均搜索長度最小。(2) 不相等搜索概率的情形第10頁，共79頁，2022年，5月20日，20點22分，星期四doiftodoiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05q0=0.15q1=0.

7、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， ASLunsucc = (0.15+0.1+0.05+0.05)*2 = 0.7。第11頁，共79頁，2022年，5月20日，20點22分，星期四doifto q0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05do

8、iftoq0=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 = 0.15*2+0.1*3+0.05*3+0.05*1 = 0.8.第12頁，共79頁，2022年，5月20日，20點22分，星期四由此可知，圖(c)和圖(e)的情形下樹的平均搜索長度達到最小，因此，

9、圖(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頁，共79頁，2022年，5月20日，20點22分，星期四一般把平均搜索長度達到最小的擴充的二叉搜索樹稱作最優(yōu)二叉搜索樹。等概率條件下，最優(yōu)二叉搜索樹的最短內(nèi)部路徑長度與最短外部路徑長度, 課本383頁:第14頁，共79頁，2022年，5月20日，20點22分

10、，星期四 一、什么是平衡二叉樹 二、失衡二叉排序樹的分析與調(diào)整 平衡二叉樹第15頁，共79頁，2022年，5月20日，20點22分，星期四平衡二叉樹又稱為AVL樹。 一棵平衡二叉樹或者是空樹，或者是具有下列性質(zhì)的二叉排序樹： 左子樹與右子樹的高度之差的絕對值小于等于1； 左子樹和右子樹也是平衡二叉排序樹。第16頁，共79頁，2022年，5月20日，20點22分，星期四例：平衡二叉樹40247053452860 引入平衡二叉樹的目的是為了提高查找效率， 使其平均查找長度為O(log2n)。402470532860第17頁，共79頁，2022年，5月20日，20點22分，星期四 根據(jù)平衡二叉樹的定

11、義， 平衡二叉樹上所有結(jié)點的平衡因子只能是-1、 0，或1。當(dāng)我們在一個平衡二叉排序樹上插入一個結(jié)點時，有可能導(dǎo)致失衡，即出現(xiàn)絕對值大于1的平衡因子，如2、-2。 為了方便起見，給每個結(jié)點附加一個數(shù)字，給出該結(jié)點左子樹與右子樹的高度差。這個數(shù)字稱為結(jié)點的平衡因子。第18頁，共79頁，2022年，5月20日，20點22分，星期四40247053452860402470532860例：下圖對平衡二叉樹和失去平衡的二叉排序樹分別標注了平衡因子。01-1-100-110-1-20-1第19頁，共79頁，2022年，5月20日，20點22分，星期四 一、什么是平衡二叉樹 二、失衡二叉排序樹的分析與調(diào)整

12、平衡二叉樹第20頁，共79頁，2022年，5月20日，20點22分，星期四 如果在一棵AVL樹中插入一個新結(jié)點，就有可能造成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)?，F(xiàn)分別介紹這四種平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類： LL平衡旋轉(zhuǎn) RR平衡旋轉(zhuǎn) LR平衡旋轉(zhuǎn) RL平衡旋轉(zhuǎn)第21頁，共79頁，2022年，5月20日，20點22分，星期四 若在A的左子樹的左子樹上插入結(jié)點，使A的平衡因子從1增加至2，需要進行一次順時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）1）LL平衡旋轉(zhuǎn)：ABCABC第22頁，共79頁，2022年，5月20日，20點22分，星期四右單旋轉(zhuǎn) (RotateRigh

13、t )hhhACEBD(a) (b) (c)hh+1BACEDhhh+1CEABD在左子樹D上插入新結(jié)點使其高度增1，導(dǎo)致結(jié)點A的平衡因子增到 -2，造成了不平衡。為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3個結(jié)點A、B和D，它們處于一條方向為“/”的直線上，需要做右單旋轉(zhuǎn)。以結(jié)點B為旋轉(zhuǎn)軸，將結(jié)點A順時針旋轉(zhuǎn)。h000-1-1-2第23頁，共79頁，2022年，5月20日，20點22分，星期四 左改組（新插入結(jié)點出現(xiàn)在危機結(jié)點的左子樹上進行的調(diào)整）的情況分析：1、LL 情況：（LL：表示新插入結(jié)點在危機結(jié)點的 左子樹的左子樹上）AB+1h-10+2+1hh-1h-1LL 改組BLBRARBA0h0

14、h-1h-1BLBRAR危機結(jié)點改組前：高度為 h + 1 中序序列：ABBLBRAR改組后：高度為 h + 1 中序序列：ABBLBRAR注意：改組后 平衡度為 0AB第24頁，共79頁，2022年，5月20日，20點22分，星期四 若在A的右子樹的右子樹上插入結(jié)點，使A的平衡因子從-1增加至-2，需要進行一次逆時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABC第25頁，共79頁，2022年，5月20日，20點22分，星期四左單旋轉(zhuǎn) (RotateLeft )hhhACEBD(a) (b) (c)hhh+1BACEDhhh+1CEABD如果在子樹E中插入一個新結(jié)點，該子樹高度增1導(dǎo)致結(jié)

15、點A的平衡因子變成+2，出現(xiàn)不平衡。沿插入路徑檢查三個結(jié)點A、C和E。它們處于一條方向為“”的直線上，需要做左單旋轉(zhuǎn)。以結(jié)點C為旋轉(zhuǎn)軸，讓結(jié)點A反時針旋轉(zhuǎn)。+1+20+100第26頁，共79頁，2022年，5月20日，20點22分，星期四 若在A的左子樹的右子樹上插入結(jié)點，使A的平衡因子從1增加至2，需要先進行逆時針旋轉(zhuǎn)，再順時針旋轉(zhuǎn)。 (以插入的結(jié)點C為旋轉(zhuǎn)軸）ABCABCABC3）LR平衡旋轉(zhuǎn)：第27頁，共79頁，2022年，5月20日，20點22分，星期四2、LR 情況：（LR：表示新插入結(jié)點在危機結(jié)點的 左子樹的右子樹上） 情況A：AB+1h-10+2-1h-1LR 改組BLAR危機結(jié)

16、點改組前： 高度為 h + 1 中序序列：注意：改組后 平衡度為 0,0,-1CBCCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR改組后： 高度為 h + 1 中序序列：ABBLARCCLCRA第28頁，共79頁，2022年，5月20日，20點22分，星期四Double RotationsFig. 28-7 (a) The AVL tree in Fig. 28-5 after additions that maintain its balance; (b) after an addition that destroys the b

17、alance continued 第29頁，共79頁，2022年，5月20日，20點22分，星期四Double RotationsFig. 28-7 (ctd.) (c) after a left rotation; (d) after a right rotation.第30頁，共79頁，2022年，5月20日，20點22分，星期四若在A的右子樹的左子樹上插入結(jié)點，使A的平衡因子從-1增加至-2，需要先進行順時針旋轉(zhuǎn)，再逆時針旋轉(zhuǎn)。 (以插入的結(jié)點C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABCABCABC這種調(diào)整規(guī)則可以保證二叉排序樹的次序不變第31頁，共79頁，2022年，5月20日，20點22分，

18、星期四 綜上所述， 在一個平衡二叉排序樹上插入一個新結(jié)點S時，主要包括以下三步： (1)查找應(yīng)插位置，同時記錄離插入位置最近的可能失衡結(jié)點A（A的平衡因子不等于0）。 (2)插入新結(jié)點S， 并修改從A到S路徑上各結(jié)點的平衡因子。 (3)根據(jù)A、 B的平衡因子， 判斷是否失衡以及失衡類型， 并做相應(yīng)處理。 第32頁，共79頁，2022年，5月20日，20點22分，星期四Double RotationsFig. 28-5 (a) Adding 70 to the tree in Fig. 28-2c destroys its balance; to restore the balance, per

19、form both (b) a right rotation and (c) a left rotation.第33頁，共79頁，2022年，5月20日，20點22分，星期四013037024例：請將下面序列構(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頁，共79頁，2022年，5月20日，20點22分，星期四例如，輸入關(guān)鍵碼序列為 16, 3, 7, 11, 9, 26, 18, 14,

20、 15 ，插入和調(diào)整過程如下。160163-10左右雙旋731600073110-1116右單旋37169000111163701-273161190-1-223711269160112第35頁，共79頁，2022年，5月20日，20點22分，星期四右左雙旋0左單旋181600732611900031609171126183-1-17161426911127390182611-1161第36頁，共79頁，2022年，5月20日，20點22分，星期四1518231816-2左右雙旋73000117149-1161501112626141-29從空樹開始的建樹過程第37頁，共79頁，2022年，5

21、月20日，20點22分，星期四各種搜索結(jié)構(gòu)的比較課本397頁 圖10.14第38頁，共79頁，2022年，5月20日，20點22分，星期四作業(yè)1、設(shè)有關(guān)鍵碼序列55，31，11，37，46，73，63，02，07，從空樹開始構(gòu)造平衡二叉搜索樹，畫出每加入一個新結(jié)點時二叉樹的形態(tài)。第39頁，共79頁，2022年，5月20日，20點22分，星期四伸展樹（Splaying Tree） 伸展樹、AVL樹、并查集的用雙親表示的樹，都屬于自調(diào)整數(shù)據(jù)結(jié)構(gòu)（self-adjusting data structure）。AVL樹使得搜索樹保持高度平衡，讓葉結(jié)點只出現(xiàn)在最低的一層或兩層上，從而提高其搜索效率。伸展

22、樹是另一種提高搜索效率的方法，其思路是：單一旋轉(zhuǎn)：將經(jīng)常訪問的結(jié)點最終上移到靠近根的地方，使以后的訪問更快。第40頁，共79頁，2022年，5月20日，20點22分，星期四移動到根部：假設(shè)正訪問的結(jié)點將以很高的概率再次被訪問，對它反復(fù)進行子女父結(jié)點旋轉(zhuǎn)，直到被訪問的結(jié)點位于根部為止。伸展樹提出了一組改進二叉搜索樹性能的一組規(guī)則，每當(dāng)執(zhí)行搜索、插入、刪除等操作時，就要依據(jù)這些規(guī)則調(diào)整二叉搜索樹，從而保證操作的時間代價。每當(dāng)訪問（搜索、插入或刪除）一個結(jié)點 s 時，伸展樹就執(zhí)行一次叫做“展開(splaying)”的過程，將結(jié)點 s 移到二叉搜索樹的根部。 第41頁，共79頁，2022年，5月20日

23、，20點22分，星期四就像AVL樹，一次“展開”由一組旋轉(zhuǎn)組成。旋轉(zhuǎn)有三種類型：單旋轉(zhuǎn)、一字形旋轉(zhuǎn)和之字形旋轉(zhuǎn)。一次旋轉(zhuǎn)的目的是通過調(diào)整結(jié)點 s 與它的父結(jié)點 p 和祖父結(jié)點 g 之間位置，把它上移到樹的更高層。被訪問結(jié)點 s 的父結(jié)點 p 是根結(jié)點。此時執(zhí)行單旋轉(zhuǎn)。在保持二叉搜索樹特性的情況下，結(jié)點 s 成為新的根，原來的根 p 成為它的子女結(jié)點。 第42頁，共79頁，2022年，5月20日，20點22分，星期四同構(gòu)形狀（homogeneous configuration）。結(jié)點 s 是其父結(jié)點 p 的左子女，結(jié)點 p 又是其父結(jié)點 g 的左子女()。或者結(jié)點 s 是其父結(jié)點 p 的右子女，

24、結(jié)點 p 又是其父結(jié)點g 的右子女()。此時執(zhí)行一字形旋轉(zhuǎn) (zigzig rotation): pssp右單旋轉(zhuǎn)第43頁，共79頁，2022年，5月20日，20點22分，星期四異構(gòu)的形狀（heterogeneous configuration）。結(jié)點 s 是其父結(jié)點 p 的左子女，結(jié)點 p 又是其父結(jié)點 g 的右子女()。或結(jié)點 s 是其父結(jié)點 p 的右子女，結(jié)點 p 又是其父結(jié)點 g 的左子女()。此時執(zhí)行之字形旋轉(zhuǎn)(zigzag rotation)。 pgspgspgs右單旋轉(zhuǎn)右單旋轉(zhuǎn)第44頁，共79頁，2022年，5月20日，20點22分，星期四因為剛訪問的結(jié)點 s 與其父結(jié)點 p 和

25、祖父結(jié)點g 形成折線，需要做與AVL樹一樣的雙旋轉(zhuǎn)，首先圍繞 s 旋轉(zhuǎn) p，再圍繞 s 旋轉(zhuǎn) g，把結(jié)點 s上升到祖父結(jié)點的位置，并保持二叉搜索樹的特性。 pgspgssgp左單旋轉(zhuǎn)右單旋轉(zhuǎn)第45頁，共79頁，2022年，5月20日，20點22分，星期四將剛訪問的結(jié)點s上移到樹根部的算法 splaying (g, p, s) /g 是 p 的父結(jié)點，p 是 s 的父結(jié)點/算法將s移到根結(jié)點位置 while (s 不是樹的根結(jié)點) if (s 的父結(jié)點是根結(jié)點) 進行單旋轉(zhuǎn), 將 s 調(diào)整為根結(jié)點 else if (s 與它的前驅(qū) p, g 是同構(gòu)形狀) 進行一字形雙旋轉(zhuǎn)，將 s 上移 else

26、 /s 與它的前驅(qū) p, g 是異構(gòu)形狀 進行之字形雙旋轉(zhuǎn)，將 s 上移; 第46頁，共79頁，2022年，5月20日，20點22分，星期四伸展樹的性能分析之字形旋轉(zhuǎn)使得樹結(jié)構(gòu)趨向于平衡化，結(jié)果常常使樹結(jié)構(gòu)的高度減少1。而一字形旋轉(zhuǎn)一般不會降低樹結(jié)構(gòu)的高度，它只是把剛訪問的結(jié)點向根結(jié)點上移。伸展樹不要求每一個操作都是高效的，對于一個有 n 個結(jié)點的樹，執(zhí)行 m 次操作時可能一次插入或搜索操作需要花費O(n)時間。例如，對于一個有 n 個結(jié)點的單支樹，訪問最底層的結(jié)點，需要時間即為O(n)。第47頁，共79頁，2022年，5月20日，20點22分，星期四當(dāng)mn時，所有m個操作總共需要O(mlog

27、2n)時間，從而使每次訪問操作的所花費的平均時間達到O(log2n)，從整體上保持較高的時間性能。下面的實例描述了伸展樹如何通過“展開”實現(xiàn)自調(diào)整。首先在伸展樹中搜索70，搜索過程與二叉搜索樹完全一樣，一旦搜索成功，就執(zhí)行“展開”過程將該結(jié)點上移到根結(jié)點位置。伸展樹的插入操作與二叉搜索樹相同，但結(jié)點一經(jīng)插入之后立即展開到根結(jié)點。 第48頁，共79頁，2022年，5月20日，20點22分，星期四608030201070409050608030201070409050608030201070409050608030201070409050zigzig雙旋轉(zhuǎn)zigzag雙旋轉(zhuǎn)左單旋轉(zhuǎn)70調(diào)整完第49

28、頁，共79頁，2022年，5月20日，20點22分，星期四從伸展樹中刪除一個結(jié)點的操作也與二叉搜索樹相同，但需要把被刪結(jié)點的父結(jié)點展開到根結(jié)點。伸展樹與AVL樹在操作上稍有不同。伸展樹的調(diào)整與結(jié)點被訪問（包括搜索、插入、刪除）的頻率有關(guān)，能夠進行更合理的調(diào)整。而AVL樹的結(jié)構(gòu)調(diào)整只與插入、刪除的順序有關(guān)，與訪問的頻率無關(guān)。 第50頁，共79頁，2022年，5月20日，20點22分，星期四紅黑樹（Red-Black Tree） 紅黑樹是一棵二叉搜索樹：樹中的每一個結(jié)點的顏色不是黑色就是紅色?？梢园岩豢眉t黑樹視為一棵擴充二叉樹，用外部結(jié)點表示空指針。其特性描述如下：特性1：根結(jié)點和所有外部結(jié)點的顏

29、色是黑色。特性2：從根結(jié)點到外部結(jié)點的途中沒有連續(xù)兩個結(jié)點的顏色是紅色。特性3：所有從根到外部結(jié)點的路徑上都有相同數(shù)目的黑色結(jié)點。 第51頁，共79頁，2022年，5月20日，20點22分，星期四從紅黑樹中任一結(jié)點 x 出發(fā)(不包括結(jié)點 x )，到達一個外部結(jié)點的任一路徑上的黑結(jié)點個數(shù)叫做結(jié)點 x 的黑高度，稱為結(jié)點的階(rank)，記作 bh(x)。紅黑樹的黑高度定義為其根結(jié)點的黑高度。501030204060702050紅色結(jié)點黑色結(jié)點外部結(jié)點第52頁，共79頁，2022年，5月20日，20點22分，星期四另一種等價的定義是看結(jié)點指針的顏色。從父結(jié)點到黑色子女結(jié)點的指針為黑色的，從父結(jié)點到

30、紅色子女結(jié)點的指針為紅色的。50103020406070第53頁，共79頁，2022年，5月20日，20點22分，星期四特性1：從內(nèi)部結(jié)點指向外部結(jié)點的指針是黑色的。特性2：從根結(jié)點到外部結(jié)點的途中沒有兩個連續(xù)的紅色指針。特性3：所有根到外部結(jié)點的路徑上都有相同數(shù)目的黑色指針。如果知道指針的顏色，就能推斷結(jié)點的顏色，反之亦然。設(shè)從根到外部結(jié)點的路徑長度 (Path Length, PL) 為該路徑上指針的個數(shù)， 第54頁，共79頁，2022年，5月20日，20點22分，星期四結(jié)論1 如果P與Q是紅黑樹中的兩條從根到外部結(jié)點的路徑，則有：PL(P)2PL(Q)證明：考查任意一棵紅黑樹。假設(shè)根結(jié)點

31、的黑高度bh(root) = r。由特性1可知，每條從根結(jié)點到外部結(jié)點的路徑中最后一個指針為黑色；從特性2可知，不存在有連續(xù)兩個紅色指針的路徑。因此，每個紅色指針后面都會跟隨一個黑色指針，每條從根到外部結(jié)點的路徑上都有r2r個指針，綜上所述有 PL(P)2PL(Q)。第55頁，共79頁，2022年，5月20日，20點22分，星期四如上圖，從根到 40 左下的外部結(jié)點的路徑長度PL(40) = 4，從根到70右下的外部結(jié)點的路徑長度PL(70) = 3，因此PL(40)PL(70)或者PL(70)PL(40)。 50103020406070PL=4, bh=2 PL=3, bh=2第56頁，共7

32、9頁，2022年，5月20日，20點22分，星期四結(jié)論2 設(shè) h 是一棵紅黑樹的高度( 不包括外部結(jié)點)，n 是樹中內(nèi)部結(jié)點的個數(shù)，r 是根結(jié)點的黑高度，則以下關(guān)系式成立：(1) h2r (2) n2r-1(3) h2log2(n+1)證明：(1) 從結(jié)論1的證明可知，從根到任一外部結(jié)點的路徑長度不超過2r，同時從樹的定義可知，樹的高度即為根結(jié)點的高度，等于從根到離根最遠的外部結(jié)點的路徑的長度，有h2r。第57頁，共79頁，2022年，5月20日，20點22分，星期四(2) 因為紅黑樹的黑高度為r，則從樹的第 1 層到第 r 層沒有外部結(jié)點，在這些層中有2r-1個內(nèi)部結(jié)點，即內(nèi)部結(jié)點的總數(shù)至少

33、為2r-1。(3) 由(2)可得rlog2(n+1)，結(jié)合(1)，有h2log2(n+1)。由于紅黑樹的高度最大為2log2(n+1)，所以搜索、插入、刪除操作的時間復(fù)雜性為O(log2n)。注意，最差情況下的紅黑樹的高度大于最差情況下具有相同結(jié)點個數(shù)的AVL樹的高度（近似于1.44*log2(n+2)）。第58頁，共79頁，2022年，5月20日，20點22分，星期四紅黑樹的搜索 由于每一棵紅黑樹都是二叉搜索樹，可以使用二叉搜索樹的算法進行搜索。在搜索過程中不需使用顏色信息。對普通二叉搜索樹進行搜索的時間復(fù)雜性為O(h)，對于紅黑樹則為O(log2n)。因為在搜索二叉搜索樹、AVL樹和紅黑樹

34、時使用了相同算法。在最差情況下AVL樹的高度最小，因此，在那些以搜索操作為主的應(yīng)用程序中，最差情況下AVL樹能獲得最優(yōu)時間復(fù)雜性。 第59頁，共79頁，2022年，5月20日，20點22分，星期四紅黑樹的插入 首先使用二叉搜索樹的插入算法將一個元素插入到紅黑樹中，該元素將作為新的葉結(jié)點插入。在插入過程中需要為新元素染色。如果插入前是空樹，則那么新元素將成為根結(jié)點，根據(jù)特征1，根結(jié)點必須染成黑色。第60頁，共79頁，2022年，5月20日，20點22分，星期四如果插入前樹非空，若新結(jié)點被染成黑色，將違反紅黑樹的特性3，所有從根到外部結(jié)點的路徑上的黑色結(jié)點個數(shù)不等。因此，新插入的結(jié)點將染成紅色，但

35、這又可能違反紅黑樹的特性2，出現(xiàn)連續(xù)兩個紅色結(jié)點，因此需要重新平衡。guuL插入第61頁，共79頁，2022年，5月20日，20點22分，星期四設(shè)新插入的結(jié)點為u，它的父結(jié)點和祖父結(jié)點分別是pu和gu，現(xiàn)在來考查不平衡的類型。若pu是黑色結(jié)點，則特性2沒有破壞，結(jié)束重新平衡的過程。若pu是紅色結(jié)點，則出現(xiàn)連續(xù)兩個紅色結(jié)點的情形，這時還要考查pu的兄弟結(jié)點。插入puguugr第62頁，共79頁，2022年，5月20日，20點22分，星期四1)如果pu的兄弟結(jié)點gr是紅色結(jié)點，此時結(jié)點pu的父結(jié)點gu是黑色結(jié)點，它有兩個紅色子女結(jié)點。交換結(jié)點gu和它的子女結(jié)點的顏色，將可能破壞紅黑樹特性2的紅色結(jié)

36、點上移。puguugrpuguugruLuRpuRgrLgrRuLuRpuRgrLgrR第63頁，共79頁，2022年，5月20日，20點22分，星期四2)如果pu的兄弟結(jié)點gr是黑色結(jié)點，此時又有兩種情況。 u是pu的左子女，pu是gu的左子女。在這種情況下只要做一次右單旋轉(zhuǎn)，交換一下pu和gu的顏色，就可恢復(fù)紅黑樹的特性，并結(jié)束重新平衡過程。pugugrupugugruuLuRpuRgrLgrRuLuRpuRgrLgrR第64頁，共79頁，2022年，5月20日，20點22分，星期四 u是pu的右子女，pu是gu的左子女。在這種情況下做一次先左后右的雙旋轉(zhuǎn)，再交換一下u與gu的顏色，就可恢

37、復(fù)紅黑樹的特性，結(jié)束重新平衡過程。 puL gupuugrgrL grR uRuLgupuugrgrL grR uRuLpuL 第65頁，共79頁，2022年，5月20日，20點22分，星期四針對上述兩種情況，還有鏡像情況，即pu是gu的右子女時，當(dāng)u是pu的右子女則做左單旋轉(zhuǎn)，當(dāng)u是pu的左子女則做先右后左的雙旋轉(zhuǎn)。紅黑樹的刪除算法與二叉搜索樹的刪除算法類似，不同之處在于，在紅黑樹中執(zhí)行一次二叉搜索樹的刪除運算，可能會破壞紅黑樹的特性，需要重新平衡。紅黑樹的刪除第66頁，共79頁，2022年，5月20日，20點22分，星期四在紅黑樹中真正刪除的結(jié)點應(yīng)是葉結(jié)點或只有一個子女的結(jié)點。如果被刪結(jié)點

38、p是紅色的，刪去它樹中各結(jié)點的黑高度都沒有改變，也不會出現(xiàn)連續(xù)兩個紅色結(jié)點，紅黑樹的特性仍然保持，不需執(zhí)行重新平衡過程。pvguuL uR vRvL vguuL uR vRvL 直接刪除第67頁，共79頁，2022年，5月20日，20點22分，星期四如果被刪結(jié)點p是黑色的，一旦刪去它，紅黑樹將不滿足特性3的要求，因為在這條路徑上黑色結(jié)點少了一個，從根到外部結(jié)點的黑高度將會降低?？梢詫⒔Y(jié)點u視為具有雙重黑色的結(jié)點，這樣任意包含結(jié)點u的路徑上的黑高度仍保持刪除前的值，就能恢復(fù)紅黑樹的特性。問題是在紅黑樹的定義中沒有包括雙重黑色的結(jié)點，因此必須通過旋轉(zhuǎn)變換和改變結(jié)點的顏色，消除雙重黑色結(jié)點，恢復(fù)紅黑樹的特性。第68頁，共79頁，2022年，5月20日，20點22分，星期四設(shè)u是被刪結(jié)點p的唯一子女結(jié)點。如果結(jié)點u是紅色結(jié)點，可以把u染成黑色，從而恢復(fù)紅黑樹的特性。pugvugv第69頁，共79頁，2022年，5月20日，20點22分，星期四如果被刪結(jié)點p是黑色結(jié)點，它的唯一的子女結(jié)點u也是黑色結(jié)點，可先將p從鏈中摘下，將結(jié)點u鏈到其祖父g的下面。假設(shè)結(jié)點u成為結(jié)點g的右子女，v是u的左兄弟。根