高度平衡的二叉樹高度平衡的二叉樹1

二叉搜索樹性能分析對(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二叉搜索樹性能分析對(duì)于有n個(gè)關(guān)鍵碼的集合，其關(guān)鍵2同樣3個(gè)數(shù)據(jù){1,2,3}，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。如果輸入序列選得不好，會(huì)建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大。用樹的搜索效率來評(píng)價(jià)這些二叉搜索樹。為此，在二叉搜索樹中加入外結(jié)點(diǎn)，形成判定樹。外結(jié)點(diǎn)表示失敗結(jié)點(diǎn)，內(nèi)結(jié)點(diǎn)表示搜索樹中已有的數(shù)據(jù)。這樣的判定樹即為擴(kuò)充的二叉搜索樹。同樣3個(gè)數(shù)據(jù){1,2,3}，輸入順序不同，建立起3舉例說明。已知關(guān)鍵碼集合

{a1,a2,a3}=

{do,if,to}，對(duì)應(yīng)搜索概率p1,p2,p3,在各搜索不成功間隔內(nèi)搜索概率分別為q0,q1,q2,q3?？赡艿亩嫠阉鳂淙缦滤尽oiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)舉例說明。已知關(guān)鍵碼集合{a1,a2,a3}={d4判定樹doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)判定樹doiftoq0q1p1q2p2q3p3doiftoq5在判定樹中

○表示內(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)上的搜索概率p[i]與搜索該結(jié)點(diǎn)時(shí)所需的關(guān)鍵碼比較次數(shù)c[i](=l[i],即結(jié)點(diǎn)所在層次)乘積之和：在判定樹中6設(shè)各關(guān)鍵碼的搜索概率相等：p[i]=1/n搜索不成功的平均搜索長(zhǎng)度ASLunsucc為樹中所有外部結(jié)點(diǎn)上搜索概率q[j]與到達(dá)外部結(jié)點(diǎn)所需關(guān)鍵碼比較次數(shù)c'[j](=l'[j])乘積之和：設(shè)外部結(jié)點(diǎn)搜索概率相等：q[j]=1/(n+1)：設(shè)各關(guān)鍵碼的搜索概率相等：p[i]=1/n7設(shè)樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率都相等：

p[i]=1/3,1≤i≤3,q[j]=1/4,0≤

j≤3

圖(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+1/3*3+1/3*1=6/3,

ASLunsucc=1/4*2+1/4*3*2+1/4*1=9/4。(1)相等搜索概率的情形設(shè)樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率都相等：(1)相等搜索概率8

圖(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)度最小。 圖(e):ASLsucc=1/3*1+1/3*3+19設(shè)二叉搜索樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率互不相等。

p[1]=0.5,p[2]=0.1,p[3]=0.05

q[0]=0.15,q[1]=0.1,q[2]=0.05,q[3]=0.05分別計(jì)算各個(gè)可能的擴(kuò)充二叉搜索樹的搜索性能，判斷哪些擴(kuò)充二叉搜索樹的平均搜索長(zhǎng)度最小。(2)不相等搜索概率的情形設(shè)二叉搜索樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率互不相等。

10doiftodoiftoq0=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，

ASLunsucc=(0.15+0.1+0.05+0.05)*2=0.7。doiftodoiftoq0=0.15q1=0.1p1=0.11doifto

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=0.15*2+0.1*3+0.05*3+0.05*1=0.8.doiftoq0=q1=0.1p1=0.5q2=0.0512由此可知，圖(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;由此可知，圖(c)和圖(e)的情形下樹的平均搜索長(zhǎng)度達(dá)到最小13一般把平均搜索長(zhǎng)度達(dá)到最小的擴(kuò)充的二叉搜索樹稱作最優(yōu)二叉搜索樹。等概率條件下，最優(yōu)二叉搜索樹的最短內(nèi)部路徑長(zhǎng)度與最短外部路徑長(zhǎng)度,課本383頁:高度平衡的二叉樹優(yōu)質(zhì)精選課件14?一、什么是平衡二叉樹二、失衡二叉排序樹的分析與調(diào)整

平衡二叉樹?一、什么是平衡二叉樹平衡二叉樹15平衡二叉樹又稱為AVL樹。

一棵平衡二叉樹或者是空樹，或者是具有下列性質(zhì)的二叉排序樹：

①

左子樹與右子樹的高度之差的絕對(duì)值小于等于1；②左子樹和右子樹也是平衡二叉排序樹。平衡二叉樹又稱為AVL樹。16結(jié)論2設(shè)h是一棵紅黑樹的高度(不包括外部結(jié)點(diǎn))，n是樹中內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)，r是根結(jié)點(diǎn)的黑高度，則以下關(guān)系式成立：當(dāng)m≥n時(shí)，所有m個(gè)操作總共需要O(mlog2n)時(shí)間，從而使每次訪問操作的所花費(fèi)的平均時(shí)間達(dá)到O(log2n)，從整體上保持較高的時(shí)間性能。28-7(ctd.由特性1‘可知，每條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑中最后一個(gè)指針為黑色；(1)h≤2r如果插入前是空樹，則那么新元素將成為根結(jié)點(diǎn)，根據(jù)特征1，根結(jié)點(diǎn)必須染成黑色。設(shè)新插入的結(jié)點(diǎn)為u，它的父結(jié)點(diǎn)和祖父結(jié)點(diǎn)分別是pu和gu，現(xiàn)在來考查不平衡的類型。0.紅黑樹的黑高度定義為其根結(jié)點(diǎn)的黑高度。(2)n≥2r-1可能的二叉搜索樹如下所示。一棵判定樹上的搜索成功的平均搜索長(zhǎng)度ASLsucc可以定義為該樹所有內(nèi)部結(jié)點(diǎn)上的搜索概率p[i]與搜索該結(jié)點(diǎn)時(shí)所需的關(guān)鍵碼比較次數(shù)c[i](=l[i],即結(jié)點(diǎn)所在層次)乘積之和：{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}p[i]=1/3,1≤i≤3,q[j]=1/4,0≤j≤3特性2：從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的途中沒有連續(xù)兩個(gè)結(jié)點(diǎn)的顏色是紅色。伸展樹、AVL樹、并查集的用雙親表示的樹，都屬于自調(diào)整數(shù)據(jù)結(jié)構(gòu)（self-adjustingdatastructure）。(3)由(2)可得r≤log2(n+1)，結(jié)合(1)，有根據(jù)紅黑樹的特性2，r一定是黑色結(jié)點(diǎn)。從父結(jié)點(diǎn)到黑色子女結(jié)點(diǎn)的指針為黑色的，從父結(jié)點(diǎn)到紅色子女結(jié)點(diǎn)的指針為紅色的。如果插入前樹非空，若新結(jié)點(diǎn)被染成黑色，將違反紅黑樹的特性3，所有從根到外部結(jié)點(diǎn)的路徑上的黑色結(jié)點(diǎn)個(gè)數(shù)不等。例：平衡二叉樹40247053452860引入平衡二叉樹的目的是為了提高查找效率，使其平均查找長(zhǎng)度為O(log2n)。402470532860結(jié)論2設(shè)h是一棵紅黑樹的高度(不包括外部結(jié)點(diǎn))，17根據(jù)平衡二叉樹的定義，平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只能是-1、0，或1。當(dāng)我們?cè)谝粋€(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)的平衡因子。根據(jù)平衡二叉樹的定義，平衡二叉樹上所有結(jié)點(diǎn)的平1840247053452860402470532860例：下圖對(duì)平衡二叉樹和失去平衡的二叉排序樹分別標(biāo)注了平衡因子。01-1-100-110-1-20-140247053452860402470532860例：下圖19一、什么是平衡二叉樹

?二、失衡二叉排序樹的分析與調(diào)整

平衡二叉樹一、什么是平衡二叉樹平衡二叉樹20如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)。現(xiàn)分別介紹這四種平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類：

LL平衡旋轉(zhuǎn)

RR平衡旋轉(zhuǎn)

LR平衡旋轉(zhuǎn)

RL平衡旋轉(zhuǎn)如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成21若在A的左子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）1）LL平衡旋轉(zhuǎn)：ABCABC若在A的左子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增22右單旋轉(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)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)。h000-1-1-2右單旋轉(zhuǎn)(RotateRight)hhhACEBD(a)23

左改組（新插入結(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左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹上進(jìn)行的調(diào)整）AB24若在A的右子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABC若在A的右子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從-125左單旋轉(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左單旋轉(zhuǎn)(RotateLeft)hhhACEBD(a)26若pu是紅色結(jié)點(diǎn)，則出現(xiàn)連續(xù)兩個(gè)紅色結(jié)點(diǎn)的情形，這時(shí)還要考查pu的兄弟結(jié)點(diǎn)。在保持二叉搜索樹特性的情況下，結(jié)點(diǎn)s成為新的根，原來的根p成為它的子女結(jié)點(diǎn)。因?yàn)樵谒阉鞫嫠阉鳂洹VL樹和紅黑樹時(shí)使用了相同算法。課本397頁圖10.平衡二叉樹又稱為AVL樹。針對(duì)上述兩種情況，還有鏡像情況，即pu是gu的右子女時(shí)，當(dāng)u是pu的右子女則做左單旋轉(zhuǎn)，當(dāng)u是pu的左子女則做先右后左的雙旋轉(zhuǎn)。由于每一棵紅黑樹都是二叉搜索樹，可以使用二叉搜索樹的算法進(jìn)行搜索。假設(shè)根結(jié)點(diǎn)的黑高度bh(root)=r。為了方便起見，給每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)左子樹與右子樹的高度差。28-7(ctd.28-2cdestroysitsbalance;torestorethebalance,performboth

(b)arightrotationand(c)aleftrotation.splaying(g,p,s){二、失衡二叉排序樹的分析與調(diào)整在這種情況下只要做一次右單旋轉(zhuǎn)，交換一下pu和gu的顏色，就可恢復(fù)紅黑樹的特性，并結(jié)束重新平衡過程。伸展樹、AVL樹、并查集的用雙親表示的樹，都屬于自調(diào)整數(shù)據(jù)結(jié)構(gòu)（self-adjustingdatastructure）。else//s與它的前驅(qū)p,g是異構(gòu)形狀{2,1,3}假設(shè)根結(jié)點(diǎn)的黑高度bh(root)=r。由此可知，圖(c)和圖(e)的情形下樹的平均搜索長(zhǎng)度達(dá)到最小，因此，圖(c)和圖(e)的情形是最優(yōu)二叉搜索樹。28-5afteradditionsthatmaintainitsbalance;(b)afteranadditionthatdestroysthebalance…continued→若在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)：若pu是紅色結(jié)點(diǎn)，則出現(xiàn)連續(xù)兩個(gè)紅色結(jié)點(diǎn)的情形，這時(shí)還要考查272、LR情況：（LR：表示新插入結(jié)點(diǎn)在危機(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中序序列：ABBLARCCLCRA2、LR情況：（LR：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的AB+1h28DoubleRotationsFig.28-7(a)TheAVLtreeinFig.28-5afteradditionsthatmaintainitsbalance;(b)afteranadditionthatdestroysthebalance…continued→

DoubleRotationsFig.28-7(a)29DoubleRotationsFig.28-7(ctd.)(c)afteraleftrotation;

(d)afterarightrotation.DoubleRotationsFig.28-7(ctd30若在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ī)則可以保證二叉排序樹的次序不變?nèi)粼贏的右子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至31綜上所述，在一個(gè)平衡二叉排序樹上插入一個(gè)新結(jié)點(diǎn)S時(shí)，主要包括以下三步：

(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)處理。綜上所述，在一個(gè)平衡二叉排序樹上插入一個(gè)新結(jié)點(diǎn)S時(shí)，32DoubleRotationsFig.28-5(a)Adding70tothetreeinFig.28-2cdestroysitsbalance;torestorethebalance,performboth

(b)arightrotationand(c)aleftrotation.DoubleRotationsFig.28-5(a)33013037024例：請(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先順后逆）037090053037090053000例：請(qǐng)將下面序列構(gòu)成一棵平衡二叉排序樹：

34例如，輸入關(guān)鍵碼序列為{16,3,7,11,9,26,18,14,15}，插入和調(diào)整過程如下。160163-10左右雙旋731600073110-1116右單旋37169000111163701-273161190-1-223711269160112例如，輸入關(guān)鍵碼序列為{16,3,7,11,9,35右左雙旋0左單旋181600732611900031609171126183-1-17161426911127390182611-1161右左雙旋0左單旋181600732611900031609136在最差情況下AVL樹的高度最小，因此，在那些以搜索操作為主的應(yīng)用程序中，最差情況下AVL樹能獲得最優(yōu)時(shí)間復(fù)雜性?？梢詫⒔Y(jié)點(diǎn)u視為具有雙重黑色的結(jié)點(diǎn)，這樣任意包含結(jié)點(diǎn)u的路徑上的黑高度仍保持刪除前的值，就能恢復(fù)紅黑樹的特性。結(jié)點(diǎn)w是紅色結(jié)點(diǎn)，作一次右單旋轉(zhuǎn)，將w、g染成黑色，v染成紅色，就可消除結(jié)點(diǎn)u的雙重黑色，恢復(fù)紅黑樹的性質(zhì)。交換結(jié)點(diǎn)gu和它的子女結(jié)點(diǎn)的顏色，將可能破壞紅黑樹特性2的紅色結(jié)點(diǎn)上移。當(dāng)m≥n時(shí)，所有m個(gè)操作總共需要O(mlog2n)時(shí)間，從而使每次訪問操作的所花費(fèi)的平均時(shí)間達(dá)到O(log2n)，從整體上保持較高的時(shí)間性能。伸展樹與AVL樹在操作上稍有不同。一棵判定樹上的搜索成功的平均搜索長(zhǎng)度ASLsucc可以定義為該樹所有內(nèi)部結(jié)點(diǎn)上的搜索概率p[i]與搜索該結(jié)點(diǎn)時(shí)所需的關(guān)鍵碼比較次數(shù)c[i](=l[i],即結(jié)點(diǎn)所在層次)乘積之和：=0.改組后：高度為h+1這樣的判定樹即為擴(kuò)充的二叉搜索樹。結(jié)點(diǎn)s是其父結(jié)點(diǎn)p的左子女，結(jié)點(diǎn)p又是其父結(jié)點(diǎn)g的左子女(／)。grLgrR對(duì)于有n個(gè)關(guān)鍵碼的集合，其關(guān)鍵碼有n!種不同排列，可構(gòu)成不同二叉搜索樹有(a)(b)(c)設(shè)u是被刪結(jié)點(diǎn)p的唯一子女結(jié)點(diǎn)。?二、失衡二叉排序樹的分析與調(diào)整?二、失衡二叉排序樹的分析與調(diào)整外結(jié)點(diǎn)表示失敗結(jié)點(diǎn)，內(nèi)結(jié)點(diǎn)表示搜索樹中已有的數(shù)據(jù)。1,p[3]=0.因?yàn)樵谒阉鞫嫠阉鳂洹VL樹和紅黑樹時(shí)使用了相同算法。1518231816-2左右雙旋73000117149-1161501112626141-29從空樹開始的建樹過程在最差情況下AVL樹的高度最小，因此，在那些以搜索操作為主的37各種搜索結(jié)構(gòu)的比較課本397頁圖10.14各種搜索結(jié)構(gòu)的比較課本397頁圖10.1438作業(yè)1、設(shè)有關(guān)鍵碼序列{55，31，11，37，46，73，63，02，07}，從空樹開始構(gòu)造平衡二叉搜索樹，畫出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹的形態(tài)。作業(yè)1、設(shè)有關(guān)鍵碼序列{55，31，11，37，46，73，39伸展樹（SplayingTree）

伸展樹、AVL樹、并查集的用雙親表示的樹，都屬于自調(diào)整數(shù)據(jù)結(jié)構(gòu)（self-adjustingdatastructure）。AVL樹使得搜索樹保持高度平衡，讓葉結(jié)點(diǎn)只出現(xiàn)在最低的一層或兩層上，從而提高其搜索效率。伸展樹是另一種提高搜索效率的方法，其思路是：?jiǎn)我恍D(zhuǎn)：將經(jīng)常訪問的結(jié)點(diǎn)最終上移到靠近根的地方，使以后的訪問更快。伸展樹（SplayingTree）伸展樹、AVL樹、并查40移動(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í)行一次叫做“展開(splaying)”的過程，將結(jié)點(diǎn)s移到二叉搜索樹的根部。

移動(dòng)到根部：假設(shè)正訪問的結(jié)點(diǎn)將以很高的概率再次被訪問，對(duì)它反41就像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)。

就像AVL樹，一次“展開”由一組旋轉(zhuǎn)組成。42同構(gòu)形狀（homogeneousconfiguration）。結(jié)點(diǎn)s

是其父結(jié)點(diǎn)p

的左子女，結(jié)點(diǎn)p

又是其父結(jié)點(diǎn)g

的左子女(／)?；蛘呓Y(jié)點(diǎn)s

是其父結(jié)點(diǎn)p

的右子女，結(jié)點(diǎn)p

又是其父結(jié)點(diǎn)g的右子女(＼)。此時(shí)執(zhí)行一字形旋轉(zhuǎn)(zigzigrotation):

pssp右單旋轉(zhuǎn)同構(gòu)形狀（homogeneousconfiguration43異構(gòu)的形狀（heterogeneousconfiguration）。結(jié)點(diǎn)s

是其父結(jié)點(diǎn)p

的左子女，結(jié)點(diǎn)p又是其父結(jié)點(diǎn)g

的右子女(＞)?；蚪Y(jié)點(diǎn)s

是其父結(jié)點(diǎn)

p

的右子女，結(jié)點(diǎn)p

又是其父結(jié)點(diǎn)g

的左子女(＜)。此時(shí)執(zhí)行之字形旋轉(zhuǎn)(zigzagrotation)。

pgspgspgs右單旋轉(zhuǎn)右單旋轉(zhuǎn)異構(gòu)的形狀（heterogeneousconfigurat44因?yàn)閯傇L問的結(jié)點(diǎn)s與其父結(jié)點(diǎn)p

和祖父結(jié)點(diǎn)g

形成折線，需要做與AVL樹一樣的雙旋轉(zhuǎn)，首先圍繞s

旋轉(zhuǎn)p，再圍繞s旋轉(zhuǎn)g，把結(jié)點(diǎn)s上升到祖父結(jié)點(diǎn)的位置，并保持二叉搜索樹的特性。

pgspgssgp左單旋轉(zhuǎn)右單旋轉(zhuǎn)因?yàn)閯傇L問的結(jié)點(diǎn)s與其父結(jié)點(diǎn)p和祖父結(jié)點(diǎn)g形成折線45將剛訪問的結(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)

elseif(s與它的前驅(qū)

p,g是同構(gòu)形狀)

進(jìn)行一字形雙旋轉(zhuǎn)，將

s

上移

else//s

與它的前驅(qū)

p,g是異構(gòu)形狀

進(jìn)行之字形雙旋轉(zhuǎn)，將

s

上移};將剛訪問的結(jié)點(diǎn)s上移到樹根部的算法splaying(g,46交換結(jié)點(diǎn)gu和它的子女結(jié)點(diǎn)的顏色，將可能破壞紅黑樹特性2的紅色結(jié)點(diǎn)上移。每當(dāng)訪問（搜索、插入或刪除）一個(gè)結(jié)點(diǎn)s時(shí)，伸展樹就執(zhí)行一次叫做“展開(splaying)”的過程，將結(jié)點(diǎn)s移到二叉搜索樹的根部。為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3個(gè)結(jié)點(diǎn)A、B和D，它們處于一條方向?yàn)椤?”的直線上，需要做右單旋轉(zhuǎn)。else//s與它的前驅(qū)p,g是異構(gòu)形狀特性2：從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的途中沒有連續(xù)兩個(gè)結(jié)點(diǎn)的顏色是紅色。設(shè)新插入的結(jié)點(diǎn)為u，它的父結(jié)點(diǎn)和祖父結(jié)點(diǎn)分別是pu和gu，現(xiàn)在來考查不平衡的類型。例如，輸入關(guān)鍵碼序列為{16,3,7,11,9,26,18,14,15}，插入和調(diào)整過程如下。若在A的左子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要先進(jìn)行逆時(shí)針旋轉(zhuǎn)，再順時(shí)針旋轉(zhuǎn)。44*log2(n+2)）。在紅黑樹中真正刪除的結(jié)點(diǎn)應(yīng)是葉結(jié)點(diǎn)或只有一個(gè)子女的結(jié)點(diǎn)。圖(c):ASLsucc=1/3*1+1/3*2+1/3*3=6/3,設(shè)新插入的結(jié)點(diǎn)為u，它的父結(jié)點(diǎn)和祖父結(jié)點(diǎn)分別是pu和gu，現(xiàn)在來考查不平衡的類型。DoubleRotations0.圖(d):ASLsucc=1/3*2+1/3*3+1/3*1=6/3,?二、失衡二叉排序樹的分析與調(diào)整如果結(jié)點(diǎn)u是紅色結(jié)點(diǎn)，可以把u染成黑色，從而恢復(fù)紅黑樹的特性。44*log2(n+2)）。異構(gòu)的形狀（heterogeneousconfiguration）。課本397頁圖10.伸展樹的性能分析之字形旋轉(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)。交換結(jié)點(diǎn)gu和它的子女結(jié)點(diǎn)的顏色，將可能破壞紅黑樹特性2的紅47當(dāng)m≥n時(shí)，所有m個(gè)操作總共需要O(mlog2n)時(shí)間，從而使每次訪問操作的所花費(fèi)的平均時(shí)間達(dá)到O(log2n)，從整體上保持較高的時(shí)間性能。下面的實(shí)例描述了伸展樹如何通過“展開”實(shí)現(xiàn)自調(diào)整。首先在伸展樹中搜索70，搜索過程與二叉搜索樹完全一樣，一旦搜索成功，就執(zhí)行“展開”過程將該結(jié)點(diǎn)上移到根結(jié)點(diǎn)位置。伸展樹的插入操作與二叉搜索樹相同，但結(jié)點(diǎn)一經(jīng)插入之后立即展開到根結(jié)點(diǎn)。

當(dāng)m≥n時(shí)，所有m個(gè)操作總共需要O(mlog2n)時(shí)間，從而48608030201070409050608030201070409050608030201070409050608030201070409050zigzig雙旋轉(zhuǎn)zigzag雙旋轉(zhuǎn)左單旋轉(zhuǎn)70調(diào)整完60803020107040905060803020107049從伸展樹中刪除一個(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é)構(gòu)調(diào)整只與插入、刪除的順序有關(guān)，與訪問的頻率無關(guān)。從伸展樹中刪除一個(gè)結(jié)點(diǎn)的操作也與二叉搜索樹相同，但需要把被刪50紅黑樹（Red-BlackTree）

紅黑樹是一棵二叉搜索樹：樹中的每一個(gè)結(jié)點(diǎn)的顏色不是黑色就是紅色?？梢园岩豢眉t黑樹視為一棵擴(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)。紅黑樹（Red-BlackTree）紅黑樹是一棵二叉搜索51從紅黑樹中任一結(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)。紅黑樹的黑高度定義為其根結(jié)點(diǎn)的黑高度。501030204060702050紅色結(jié)點(diǎn)黑色結(jié)點(diǎn)外部結(jié)點(diǎn)從紅黑樹中任一結(jié)點(diǎn)x出發(fā)(不包括結(jié)點(diǎn)x)，到達(dá)一個(gè)外52另一種等價(jià)的定義是看結(jié)點(diǎn)指針的顏色。從父結(jié)點(diǎn)到黑色子女結(jié)點(diǎn)的指針為黑色的，從父結(jié)點(diǎn)到紅色子女結(jié)點(diǎn)的指針為紅色的。50103020406070另一種等價(jià)的定義是看結(jié)點(diǎn)指針的顏色。50103020406053特性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)度(PathLength,PL)為該路徑上指針的個(gè)數(shù)，特性1'：從內(nèi)部結(jié)點(diǎn)指向外部結(jié)點(diǎn)的指針是黑色的。54結(jié)論1

如果P與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)的路徑上都有r～2r個(gè)指針，綜上所述有PL(P)≤2PL(Q)。結(jié)論1如果P與Q是紅黑樹中的兩條從根到外部結(jié)點(diǎn)的路徑55如上圖，從根到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)。

50103020406070PL=4,bh=2PL=3,bh=2如上圖，從根到40左下的外部結(jié)點(diǎn)的路徑長(zhǎng)度PL(40)56(a)(b)(c)uLuR課本397頁圖10.1,p[3]=0.中序序列：旋轉(zhuǎn)有三種類型：?jiǎn)涡D(zhuǎn)、一字形旋轉(zhuǎn)和之字形旋轉(zhuǎn)。這個(gè)數(shù)字稱為結(jié)點(diǎn)的平衡因子。就像AVL樹，一次“展開”由一組旋轉(zhuǎn)組成。28-2cdestroysitsbalance;torestorethebalance,performboth

(b)arightrotationand(c)aleftrotation.如上圖，從根到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)。假設(shè)根結(jié)點(diǎn)的黑高度bh(root)=r。u是pu的右子女，pu是gu的左子女。而一字形旋轉(zhuǎn)一般不會(huì)降低樹結(jié)構(gòu)的高度，它只是把剛訪問的結(jié)點(diǎn)向根結(jié)點(diǎn)上移。若pu是黑色結(jié)點(diǎn)，則特性2沒有破壞，結(jié)束重新平衡的過程。這樣的判定樹即為擴(kuò)充的二叉搜索樹。針對(duì)上述兩種情況，還有鏡像情況，即pu是gu的右子女時(shí)，當(dāng)u是pu的右子女則做左單旋轉(zhuǎn)，當(dāng)u是pu的左子女則做先右后左的雙旋轉(zhuǎn)。如果插入前是空樹，則那么新元素將成為根結(jié)點(diǎn)，根據(jù)特征1，根結(jié)點(diǎn)必須染成黑色。進(jìn)行單旋轉(zhuǎn),將s調(diào)整為根結(jié)點(diǎn)課本397頁圖10.每當(dāng)訪問（搜索、插入或刪除）一個(gè)結(jié)點(diǎn)s時(shí)，伸展樹就執(zhí)行一次叫做“展開(splaying)”的過程，將結(jié)點(diǎn)s移到二叉搜索樹的根部。結(jié)論2

設(shè)h

是一棵紅黑樹的高度(不包括外部結(jié)點(diǎn))，n

是樹中內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)，r

是根結(jié)點(diǎn)的黑高度，則以下關(guān)系式成立：

(1)h≤2r

(2)n≥2r-1 (3)h≤2log2(n+1)

證明：

(1)從結(jié)論1的證明可知，從根到任一外部結(jié)點(diǎn)的路徑長(zhǎng)度不超過2r，同時(shí)從樹的定義可知，樹的高度即為根結(jié)點(diǎn)的高度，等于從根到離根最遠(yuǎn)的外部結(jié)點(diǎn)的路徑的長(zhǎng)度，有h≤2r。(a)(b57

(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)可得r≤log2(n+1)，結(jié)合(1)，有

h≤2log2(n+1)。由于紅黑樹的高度最大為2log2(n+1)，所以搜索、插入、刪除操作的時(shí)間復(fù)雜性為O(log2n)。注意，最差情況下的紅黑樹的高度大于最差情況下具有相同結(jié)點(diǎn)個(gè)數(shù)的AVL樹的高度（近似于1.44*log2(n+2)）。 (2)因?yàn)榧t黑樹的黑高度為r，則從樹的第1層到第r58紅黑樹的搜索

由于每一棵紅黑樹都是二叉搜索樹，可以使用二叉搜索樹的算法進(jìn)行搜索。在搜索過程中不需使用顏色信息。對(duì)普通二叉搜索樹進(jìn)行搜索的時(shí)間復(fù)雜性為O(h)，對(duì)于紅黑樹則為O(log2n)。因?yàn)樵谒阉鞫嫠阉鳂?、AVL樹和紅黑樹時(shí)使用了相同算法。在最差情況下AVL樹的高度最小，因此，在那些以搜索操作為主的應(yīng)用程序中，最差情況下AVL樹能獲得最優(yōu)時(shí)間復(fù)雜性。

紅黑樹的搜索由于每一棵紅黑樹都是二叉搜索樹，可以使用二叉搜59紅黑樹的插入

首先使用二叉搜索樹的插入算法將一個(gè)元素插入到紅黑樹中，該元素將作為新的葉結(jié)點(diǎn)插入。在插入過程中需要為新元素染色。如果插入前是空樹，則那么新元素將成為根結(jié)點(diǎn)，根據(jù)特征1，根結(jié)點(diǎn)必須染成黑色。Ф紅黑樹的插入首先使用二叉搜索樹的插入算法將一個(gè)元素插入到紅60如果插入前樹非空，若新結(jié)點(diǎn)被染成黑色，將違反紅黑樹的特性3，所有從根到外部結(jié)點(diǎn)的路徑上的黑色結(jié)點(diǎn)個(gè)數(shù)不等。因此，新插入的結(jié)點(diǎn)將染成紅色，但這又可能違反紅黑樹的特性2，出現(xiàn)連續(xù)兩個(gè)紅色結(jié)點(diǎn)，因此需要重新平衡。guuL插入╳如果插入前樹非空，若新結(jié)點(diǎn)被染成黑色，將違反紅黑樹的特性3，61設(shè)新插入的結(jié)點(diǎn)為u，它的父結(jié)點(diǎn)和祖父結(jié)點(diǎn)分別是pu和gu，現(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設(shè)新插入的結(jié)點(diǎn)為u，它的父結(jié)點(diǎn)和祖父結(jié)點(diǎn)分別是pu和gu，現(xiàn)621) 如果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)上移。puguugrpuguugruLuRpuRgrLgrRuLuRpuRgrLgrR1) 如果pu的兄弟結(jié)點(diǎn)gr是紅色結(jié)點(diǎn)，此時(shí)結(jié)點(diǎn)pu的父結(jié)點(diǎn)632) 如果pu的兄弟結(jié)點(diǎn)gr是黑色結(jié)點(diǎn)，此時(shí)又有兩種情況。

u是pu的左子女，pu是gu的左子女。在這種情況下只要做一次右單旋轉(zhuǎn)，交換一下pu和gu的顏色，就可恢復(fù)紅黑樹的特性，并結(jié)束重新平衡過程。pugugrupugugruuLuRpuRgrLgrRuLuRpuRgrLgrR2) 如果pu的兄弟結(jié)點(diǎn)gr是黑色結(jié)點(diǎn)，此時(shí)又有兩種情況。p64

u是pu的右子女，pu是gu的左子女。在這種情況下做一次先左后右的雙旋轉(zhuǎn)，再交換一下u與gu的顏色，就可恢復(fù)紅黑樹的特性，結(jié)束重新平衡過程。

puL

gupuugrgrLgrR

uRuLgupuugrgrLgrR

uRuLpuL

u是pu的右子女，pu是gu的左子女。在這種情況下做一次先65針對(duì)上述兩種情況，還有鏡像情況，即pu是gu的右子女時(shí)，當(dāng)u是pu的右子女則做左單旋轉(zhuǎn)，當(dāng)u是pu的左子女則做先右后左的雙旋轉(zhuǎn)。紅黑樹的刪除算法與二叉搜索樹的刪除算法類似，不同之處在于，在紅黑樹中執(zhí)行一次二叉搜索樹的刪除運(yùn)算，可能會(huì)破壞紅黑樹的特性，需要重新平衡。紅黑樹的刪除針對(duì)上述兩種情況，還有鏡像情況，即pu是gu的右子女時(shí)，當(dāng)u66在紅黑樹中真正刪除的結(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í)行重新平衡過程。pvguuLuR

vRvL

vguuLuR

vRvL

直接刪除在紅黑樹中真正刪除的結(jié)點(diǎn)應(yīng)是葉結(jié)點(diǎn)或只有一個(gè)子女的結(jié)點(diǎn)。pv67如果被刪結(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ù)紅黑樹的特性。如果被刪結(jié)點(diǎn)p是黑色的，一旦刪去它，紅黑樹將不滿足特性3的要68設(shè)u是被刪結(jié)點(diǎn)p的唯一子女結(jié)點(diǎn)。如果結(jié)點(diǎn)u是紅色結(jié)點(diǎn)，可以把u染成黑色，從而恢復(fù)紅黑樹的特性。

pugvugv設(shè)u是被刪結(jié)點(diǎn)p的唯一子女結(jié)點(diǎn)。如果結(jié)點(diǎn)u是紅色結(jié)點(diǎn)，可以把69如果被刪結(jié)點(diǎn)p是黑色結(jié)點(diǎn)，它的唯一的子女結(jié)點(diǎn)u也是黑色結(jié)點(diǎn)，可先將p從鏈中摘下，將結(jié)點(diǎn)u鏈到其祖父g的下面。假設(shè)結(jié)點(diǎn)u成為結(jié)點(diǎn)g的右子女，v是u的左兄弟。根據(jù)v的顏色，分以下兩種情況：結(jié)點(diǎn)v是黑色結(jié)點(diǎn)，若設(shè)結(jié)點(diǎn)v的左子女結(jié)點(diǎn)為w。根據(jù)w的顏色分別討論：

如果被刪結(jié)點(diǎn)p是黑色結(jié)點(diǎn)，它的唯一的子女結(jié)點(diǎn)u也是黑色結(jié)點(diǎn)，70結(jié)點(diǎn)w是紅色結(jié)點(diǎn)，作一次右單旋轉(zhuǎn)，將w、g染成黑色，v染成紅色，就可消除結(jié)點(diǎn)u的雙重黑色，恢復(fù)紅黑樹的性質(zhì)。結(jié)點(diǎn)w是黑色結(jié)點(diǎn)，還要看結(jié)點(diǎn)w的右兄弟結(jié)點(diǎn)r。根據(jù)r的顏色，分兩種情況：gvuvRuLuR

wRwLwgvvRuuLuR

wRwLw結(jié)點(diǎn)w是紅色結(jié)點(diǎn)，作一次右單旋轉(zhuǎn)，將w、g染成黑色，v染成紅71結(jié)點(diǎn)r是紅色結(jié)點(diǎn)，可通過一次先左后右的雙旋轉(zhuǎn)，并將g染成黑色，就可消除u的雙重黑色，恢復(fù)紅黑樹的特性。結(jié)點(diǎn)r是黑色結(jié)點(diǎn)，這時(shí)還要看結(jié)點(diǎn)g的顏色。如果g是紅色結(jié)點(diǎn)，只要交換結(jié)uLuR

wRwLgvuwrrRrLgvuwruLuR

rRrLwRwL結(jié)點(diǎn)r是紅色結(jié)點(diǎn)，可通過一次先左后右的雙旋轉(zhuǎn)，并將g染成黑色72

點(diǎn)g和其子女結(jié)點(diǎn)v的顏色就能恢復(fù)紅黑樹的特性。

如果g是黑色結(jié)點(diǎn)，可做一次右單旋轉(zhuǎn)，將結(jié)點(diǎn)v上升并染成雙重黑色，從而消除結(jié)點(diǎn)u的雙重黑色，將雙重黑色結(jié)點(diǎn)向根gvuuLuR

wRwLwrrRrLgvuuLuR

wRwLwrrRrL 點(diǎn)g和其子女結(jié)點(diǎn)v的顏色就能恢復(fù)紅黑樹的特性。gvuuL73

的方向轉(zhuǎn)移。結(jié)點(diǎn)v是紅色結(jié)點(diǎn)?？疾関的右子女結(jié)點(diǎn)r。根據(jù)紅黑樹的特性2，r一定是黑色結(jié)點(diǎn)。再看結(jié)點(diǎn)r的左子女結(jié)點(diǎn)s。根據(jù)s的顏色，可以分為兩種情況討論。

gvuuLuR

wRwLwrrRrLgvuuLuR

wRwLwrrRrL 的方向轉(zhuǎn)移。gvuuLuRwRwLw741) 結(jié)點(diǎn)s是紅色結(jié)點(diǎn)。通過一次先左后右雙旋轉(zhuǎn)，讓r上升，使包含u的路徑的黑高度增1，從而消除結(jié)點(diǎn)u的雙重黑色，恢復(fù)紅黑樹的特性。

gvuuLuR

sRvLsrrRsLgvuuLuR

sRvLsrrRsL1) 結(jié)點(diǎn)s是紅色結(jié)點(diǎn)。通過一次先左后右雙旋轉(zhuǎn)，讓r上升，使752) 結(jié)點(diǎn)s是黑色結(jié)點(diǎn)，再看結(jié)點(diǎn)s的右兄弟結(jié)點(diǎn)t。根據(jù)結(jié)點(diǎn)t的顏色又可分為兩種情況進(jìn)行討論。若結(jié)點(diǎn)t為紅色結(jié)點(diǎn)，先以t為旋轉(zhuǎn)軸，做左單旋轉(zhuǎn)，以t替補(bǔ)r的位置；然后再以t為旋轉(zhuǎn)軸，做一次先左后右的雙旋轉(zhuǎn)，可消除結(jié)點(diǎn)u的雙重黑色，恢復(fù)紅黑樹特性。

2) 結(jié)點(diǎn)s是黑色結(jié)點(diǎn)，再看結(jié)點(diǎn)s的右兄弟結(jié)點(diǎn)t。根據(jù)結(jié)點(diǎn)t76針對(duì)上述兩種情況，還有鏡像情況，即pu是gu的右子女時(shí)，當(dāng)u是pu的右子女則做左單旋轉(zhuǎn)，當(dāng)u是pu的左子女則做先右后左的雙旋轉(zhuǎn)。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)。else//s與它的前驅(qū)p,g是異構(gòu)形狀A(yù)SLunsucc=1/4*1+1/4*3*2+1/4*2=9/4。(a)(b)(c)u是pu的右子女，pu是gu的左子女。在左子樹D上插入新結(jié)點(diǎn)使其高度增1，導(dǎo)致結(jié)點(diǎn)A的平衡因子增到-2，造成了不平衡。一次旋轉(zhuǎn)的目的是通過調(diào)整結(jié)點(diǎn)s與它的父結(jié)點(diǎn)p和祖父結(jié)點(diǎn)g之間位置，把它上移到樹的更高層。(3)由(2)可得r≤log2(n+1)，結(jié)合(1)，有ASLunsucc=1/4*2*4=8/4。根據(jù)r的顏色，分兩種情況：1,p[3]=0.28-5(a)Adding70tothetreeinFig.h≤2log2(n+1)。伸展樹的調(diào)整與結(jié)點(diǎn)被訪問（包括搜索、插入、刪除）的頻率有關(guān)，能夠進(jìn)行更合理的調(diào)整。特性2：從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的途中沒有連續(xù)兩個(gè)結(jié)點(diǎn)的顏色是紅色。課本397頁圖10.為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3個(gè)結(jié)點(diǎn)A、B和D，它們處于一條方向?yàn)椤?”的直線上，需要做右單旋轉(zhuǎn)。特性1'：從內(nèi)部結(jié)點(diǎn)指向外部結(jié)點(diǎn)的指針是黑色的。首先在伸展樹中搜索70，搜索過程與二叉搜索樹完全一樣，一旦搜索成功，就執(zhí)行“展開”過程將該結(jié)點(diǎn)上移到根結(jié)點(diǎn)位置。gvuuLuR

sRvLsrsLtRttLgvuuLuR

sRvLsrsLtRttLgvuuLuR

sRvLsrsLtRttL針對(duì)上述兩種情況，還有鏡像情況，即pu是gu的右子女時(shí)，當(dāng)u77若結(jié)點(diǎn)t為黑色結(jié)點(diǎn)，以v為旋轉(zhuǎn)軸，做一次右單旋轉(zhuǎn)，并改變v和r的顏色，即可消除結(jié)點(diǎn)u的雙重黑色，恢復(fù)紅黑樹的特色。gvuuLuR

sRvLsrsLtRttLgvuuLuR

sRvLsrsLtRttL若結(jié)點(diǎn)t為黑色結(jié)點(diǎn)，以v為旋轉(zhuǎn)軸，做一次右單旋轉(zhuǎn)，并改變v和78當(dāng)刪除結(jié)點(diǎn)p之后結(jié)點(diǎn)u成為結(jié)點(diǎn)g的左子女，這種情況與上面討論的情況是鏡像的，只要左、右指針互換就可以了。

當(dāng)刪除結(jié)點(diǎn)p之后結(jié)點(diǎn)u成為結(jié)點(diǎn)g的左子女，這種情況與上面討論79高度平衡的二叉樹高度平衡的二叉樹80

二叉搜索樹性能分析對(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二叉搜索樹性能分析對(duì)于有n個(gè)關(guān)鍵碼的集合，其關(guān)鍵81同樣3個(gè)數(shù)據(jù){1,2,3}，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。如果輸入序列選得不好，會(huì)建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大。用樹的搜索效率來評(píng)價(jià)這些二叉搜索樹。為此，在二叉搜索樹中加入外結(jié)點(diǎn)，形成判定樹。外結(jié)點(diǎn)表示失敗結(jié)點(diǎn)，內(nèi)結(jié)點(diǎn)表示搜索樹中已有的數(shù)據(jù)。這樣的判定樹即為擴(kuò)充的二叉搜索樹。同樣3個(gè)數(shù)據(jù){1,2,3}，輸入順序不同，建立起82舉例說明。已知關(guān)鍵碼集合

{a1,a2,a3}=

{do,if,to}，對(duì)應(yīng)搜索概率p1,p2,p3,在各搜索不成功間隔內(nèi)搜索概率分別為q0,q1,q2,q3?？赡艿亩嫠阉鳂淙缦滤尽oiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)舉例說明。已知關(guān)鍵碼集合{a1,a2,a3}={d83判定樹doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)判定樹doiftoq0q1p1q2p2q3p3doiftoq84在判定樹中

○表示內(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)上的搜索概率p[i]與搜索該結(jié)點(diǎn)時(shí)所需的關(guān)鍵碼比較次數(shù)c[i](=l[i],即結(jié)點(diǎn)所在層次)乘積之和：在判定樹中85設(shè)各關(guān)鍵碼的搜索概率相等：p[i]=1/n搜索不成功的平均搜索長(zhǎng)度ASLunsucc為樹中所有外部結(jié)點(diǎn)上搜索概率q[j]與到達(dá)外部結(jié)點(diǎn)所需關(guān)鍵碼比較次數(shù)c'[j](=l'[j])乘積之和：設(shè)外部結(jié)點(diǎn)搜索概率相等：q[j]=1/(n+1)：設(shè)各關(guān)鍵碼的搜索概率相等：p[i]=1/n86設(shè)樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率都相等：

p[i]=1/3,1≤i≤3,q[j]=1/4,0≤

j≤3

圖(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+1/3*3+1/3*1=6/3,

ASLunsucc=1/4*2+1/4*3*2+1/4*1=9/4。(1)相等搜索概率的情形設(shè)樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率都相等：(1)相等搜索概率87

圖(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)度最小。 圖(e):ASLsucc=1/3*1+1/3*3+188設(shè)二叉搜索樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率互不相等。

p[1]=0.5,p[2]=0.1,p[3]=0.05

q[0]=0.15,q[1]=0.1,q[2]=0.05,q[3]=0.05分別計(jì)算各個(gè)可能的擴(kuò)充二叉搜索樹的搜索性能，判斷哪些擴(kuò)充二叉搜索樹的平均搜索長(zhǎng)度最小。(2)不相等搜索概率的情形設(shè)二叉搜索樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率互不相等。

89doiftodoiftoq0=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，

ASLunsucc=(0.15+0.1+0.05+0.05)*2=0.7。doiftodoiftoq0=0.15q1=0.1p1=0.90doifto

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=0.15*2+0.1*3+0.05*3+0.05*1=0.8.doiftoq0=q1=0.1p1=0.5q2=0.0591由此可知，圖(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;由此可知，圖(c)和圖(e)的情形下樹的平均搜索長(zhǎng)度達(dá)到最小92一般把平均搜索長(zhǎng)度達(dá)到最小的擴(kuò)充的二叉搜索樹稱作最優(yōu)二叉搜索樹。等概率條件下，最優(yōu)二叉搜索樹的最短內(nèi)部路徑長(zhǎng)度與最短外部路徑長(zhǎng)度,課本383頁:高度平衡的二叉樹優(yōu)質(zhì)精選課件93?一、什么是平衡二叉樹二、失衡二叉排序樹的分析與調(diào)整

平衡二叉樹?一、什么是平衡二叉樹平衡二叉樹94平衡二叉樹又稱為AVL樹。

一棵平衡二叉樹或者是空樹，或者是具有下列性質(zhì)的二叉排序樹：

①

左子樹與右子樹的高度之差的絕對(duì)值小于等于1；②左子樹和右子樹也是平衡二叉排序樹。平衡二叉樹又稱為AVL樹。95結(jié)論2設(shè)h是一棵紅黑樹的高度(不包括外部結(jié)點(diǎn))，n是樹中內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)，r是根結(jié)點(diǎn)的黑高度，則以下關(guān)系式成立：當(dāng)m≥n時(shí)，所有m個(gè)操作總共需要O(mlog2n)時(shí)間，從而使每次訪問操作的所花費(fèi)的平均時(shí)間達(dá)到O(log2n)，從整體上保持較高的時(shí)間性能。28-7(ctd.由特性1‘可知，每條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑中最后一個(gè)指針為黑色；(1)h≤2r如果插入前是空樹，則那么新元素將成為根結(jié)點(diǎn)，根據(jù)特征1，根結(jié)點(diǎn)必須染成黑色。設(shè)新插入的結(jié)點(diǎn)為u，它的父結(jié)點(diǎn)和祖父結(jié)點(diǎn)分別是pu和gu，現(xiàn)在來考查不平衡的類型。0.紅黑樹的黑高度定義為其根結(jié)點(diǎn)的黑高度。(2)n≥2r-1可能的二叉搜索樹如下所示。一棵判定樹上的搜索成功的平均搜索長(zhǎng)度ASLsucc可以定義為該樹所有內(nèi)部結(jié)點(diǎn)上的搜索概率p[i]與搜索該結(jié)點(diǎn)時(shí)所需的關(guān)鍵碼比較次數(shù)c[i](=l[i],即結(jié)點(diǎn)所在層次)乘積之和：{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}p[i]=1/3,1≤i≤3,q[j]=1/4,0≤j≤3特性2：從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的途中沒有連續(xù)兩個(gè)結(jié)點(diǎn)的顏色是紅色。伸展樹、AVL樹、并查集的用雙親表示的樹，都屬于自調(diào)整數(shù)據(jù)結(jié)構(gòu)（self-adjustingdatastructure）。(3)由(2)可得r≤log2(n+1)，結(jié)合(1)，有根據(jù)紅黑樹的特性2，r一定是黑色結(jié)點(diǎn)。從父結(jié)點(diǎn)到黑色子女結(jié)點(diǎn)的指針為黑色的，從父結(jié)點(diǎn)到紅色子女結(jié)點(diǎn)的指針為紅色的。如果插入前樹非空，若新結(jié)點(diǎn)被染成黑色，將違反紅黑樹的特性3，所有從根到外部結(jié)點(diǎn)的路徑上的黑色結(jié)點(diǎn)個(gè)數(shù)不等。例：平衡二叉樹40247053452860引入平衡二叉樹的目的是為了提高查找效率，使其平均查找長(zhǎng)度為O(log2n)。402470532860結(jié)論2設(shè)h是一棵紅黑樹的高度(不包括外部結(jié)點(diǎn))，96根據(jù)平衡二叉樹的定義，平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只能是-1、0，或1。當(dāng)我們?cè)谝粋€(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)的平衡因子。根據(jù)平衡二叉樹的定義，平衡二叉樹上所有結(jié)點(diǎn)的平9740247053452860402470532860例：下圖對(duì)平衡二叉樹和失去平衡的二叉排序樹分別標(biāo)注了平衡因子。01-1-100-110-1-20-140247053452860402470532860例：下圖98一、什么是平衡二叉樹

?二、失衡二叉排序樹的分析與調(diào)整

平衡二叉樹一、什么是平衡二叉樹平衡二叉樹99如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須重新調(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)如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成100若在A的左子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）1）LL平衡旋轉(zhuǎn)：ABCABC若在A的左子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增101右單旋轉(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)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)。h000-1-1-2右單旋轉(zhuǎn)(RotateRight)hhhACEBD(a)102

左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹上進(jìn)行的調(diào)整）