第八章二叉搜索樹

1、第八章第八章 二叉搜索樹二叉搜索樹 理解以有序集為基礎(chǔ)的抽象數(shù)據(jù)類型字典。理解以有序集為基礎(chǔ)的抽象數(shù)據(jù)類型字典。 理解用數(shù)組實(shí)現(xiàn)字典的方法。理解用數(shù)組實(shí)現(xiàn)字典的方法。 理解二叉搜索樹的概念和實(shí)現(xiàn)方法。理解二叉搜索樹的概念和實(shí)現(xiàn)方法。 掌握用二叉搜索樹實(shí)現(xiàn)字典的方法。掌握用二叉搜索樹實(shí)現(xiàn)字典的方法。 理解理解AVLAVL樹的定義和性質(zhì)。樹的定義和性質(zhì)。 掌握二叉搜索樹的結(jié)點(diǎn)旋轉(zhuǎn)變換及實(shí)現(xiàn)方法。掌握二叉搜索樹的結(jié)點(diǎn)旋轉(zhuǎn)變換及實(shí)現(xiàn)方法。 掌握掌握AVLAVL樹的插入重新平衡運(yùn)算及實(shí)現(xiàn)方法。樹的插入重新平衡運(yùn)算及實(shí)現(xiàn)方法。 掌握掌握AVLAVL樹的刪除重新平衡運(yùn)算及實(shí)現(xiàn)方法。樹的刪除重新平衡運(yùn)算及實(shí)現(xiàn)

2、方法。8.1 8.1 字典的定義字典的定義 字典是以有序集為基礎(chǔ)的抽象數(shù)據(jù)類型。字典是以有序集為基礎(chǔ)的抽象數(shù)據(jù)類型。 它支持以下運(yùn)算：它支持以下運(yùn)算： (1)Member(x)(1)Member(x)，成員運(yùn)算。，成員運(yùn)算。 (2)Insert(x)(2)Insert(x)，插入運(yùn)算：將元素，插入運(yùn)算：將元素x x插入集合。插入集合。 (3)Delete(x)(3)Delete(x)，刪除運(yùn)算：將元素，刪除運(yùn)算：將元素x x從從當(dāng)前當(dāng)前集合中刪去。集合中刪去。 (4)Predecessor(x)(4)Predecessor(x)，前驅(qū)運(yùn)算：返回集合中小于，前驅(qū)運(yùn)算：返回集合中小于x x的最大元

3、的最大元素。素。 (5)Successor(x)(5)Successor(x)，后繼運(yùn)算：返回集合中大于，后繼運(yùn)算：返回集合中大于x x的最小元素。的最小元素。 (6)Range(x(6)Range(x，y)y)，區(qū)間查詢運(yùn)算：返回集合中界于，區(qū)間查詢運(yùn)算：返回集合中界于x x和和y y之間，之間，即即x xz zy y的所有元素的所有元素z z組成的集合。組成的集合。 (7)Min( )(7)Min( )，最小元運(yùn)算：返回當(dāng)前集合中依線性序最小的，最小元運(yùn)算：返回當(dāng)前集合中依線性序最小的元素。元素。 2第八章第八章 二叉搜索樹二叉搜索樹 8.2 8.2 用數(shù)組實(shí)現(xiàn)字典用數(shù)組實(shí)現(xiàn)字典 用數(shù)組實(shí)

4、現(xiàn)字典與用數(shù)組實(shí)現(xiàn)字典的不同之處：用數(shù)組實(shí)現(xiàn)字典與用數(shù)組實(shí)現(xiàn)字典的不同之處： 可以利用線性序?qū)⒆值渲械脑貜男〉酱笠佬虼鎯?chǔ)在數(shù)組中，可以利用線性序?qū)⒆值渲械脑貜男〉酱笠佬虼鎯?chǔ)在數(shù)組中，通過數(shù)組下標(biāo)來反映字典元素之間的序關(guān)系。通過數(shù)組下標(biāo)來反映字典元素之間的序關(guān)系。 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 可用可用二分法二分法高效地實(shí)現(xiàn)與線性序有關(guān)的一些運(yùn)算。如：高效地實(shí)現(xiàn)與線性序有關(guān)的一些運(yùn)算。如：Member(x) Member(x) ，Predecessor(x)Predecessor(x)和和 Successor(x)Successor(x)可在時(shí)間可在時(shí)間O(logn)O(logn)內(nèi)實(shí)現(xiàn)。內(nèi)實(shí)現(xiàn)。 缺點(diǎn)：缺

5、點(diǎn)： 插入和刪除運(yùn)算的效率較低。插入和刪除運(yùn)算的效率較低。 每執(zhí)行一次每執(zhí)行一次InsertInsert或或DeleteDelete運(yùn)算，需要移動(dòng)部分?jǐn)?shù)組元素，從而導(dǎo)致運(yùn)算，需要移動(dòng)部分?jǐn)?shù)組元素，從而導(dǎo)致它們?cè)谧顗那闆r下的計(jì)算時(shí)間為它們?cè)谧顗那闆r下的計(jì)算時(shí)間為O(n)O(n)。 考慮：能否用鏈表來實(shí)現(xiàn)字典？考慮：能否用鏈表來實(shí)現(xiàn)字典？ MemberMember運(yùn)算需要運(yùn)算需要O(n)O(n)時(shí)間，時(shí)間，一旦找到元素在鏈表中插入或刪除的位置一旦找到元素在鏈表中插入或刪除的位置后，只要用后，只要用O(1)O(1)時(shí)間就可完成插入或刪除操作。時(shí)間就可完成插入或刪除操作。 兩種實(shí)現(xiàn)方式均不可??！兩種實(shí)

6、現(xiàn)方式均不可?。〉诎苏碌诎苏?二叉搜索樹二叉搜索樹 8.3 8.3 用二叉搜索樹實(shí)現(xiàn)字典用二叉搜索樹實(shí)現(xiàn)字典8.3.1 8.3.1 基本思想：基本思想： 用二叉樹來存儲(chǔ)有序集，每一個(gè)結(jié)點(diǎn)存儲(chǔ)一個(gè)元素。用二叉樹來存儲(chǔ)有序集，每一個(gè)結(jié)點(diǎn)存儲(chǔ)一個(gè)元素。 滿足：滿足：存存儲(chǔ)儲(chǔ)于每個(gè)結(jié)點(diǎn)中的元素于每個(gè)結(jié)點(diǎn)中的元素x x大于其左子樹中任一結(jié)點(diǎn)大于其左子樹中任一結(jié)點(diǎn)中所存中所存儲(chǔ)儲(chǔ)的元素，小于其右子樹中任一結(jié)點(diǎn)中所存的元素，小于其右子樹中任一結(jié)點(diǎn)中所存儲(chǔ)儲(chǔ)的元素的元素。4第八章第八章 二叉搜索樹二叉搜索樹 例例 10， 18， 3， 8， 12， 2， 7， 410101810183101838101838

7、12210183812710183812247101838122二叉搜索樹的建立過程：二叉搜索樹的建立過程：運(yùn)算運(yùn)算Insert(const T& x)Insert(const T& x)的實(shí)現(xiàn)：的實(shí)現(xiàn)：templatetemplateBinaryTreeNodeBinaryTreeNode* * BSTree:Insert(const T& x) BSTree:Insert(const T& x)BinaryTreeNode BinaryTreeNode * *p = root, p = root, * *pp = 0; pp = 0; /從根開始檢測(cè)從根開始

8、檢測(cè)插入位置插入位置, , * *pppp記錄記錄插入插入結(jié)點(diǎn)結(jié)點(diǎn)的父結(jié)的父結(jié)點(diǎn)點(diǎn) while (p) /pwhile (p) /p非空，選擇其左或右子樹進(jìn)行插入非空，選擇其左或右子樹進(jìn)行插入 pp = p;pp = p; if (x data) if (x data) p = p-LeftChild;p = p-LeftChild; else if (x p-data)else if (x p-data)p = p-RightChild;p = p-RightChild; else else return 0 ; return 0 ; /表明表明x x在樹中，無需插入在樹中，無需插入 Bin

9、aryTreeNode BinaryTreeNode * *r = new BinaryTreeNode (x);r = new BinaryTreeNode (x);if (root) /if (root) /當(dāng)前樹非空當(dāng)前樹非空 /確定確定x x作為作為* *pppp的左兒子還是右兒子的左兒子還是右兒子 if (x data)if (x data)pp-LeftChild = r;pp-LeftChild = r; else else pp-RightChild = r;pp-RightChild = r; r-Parent = pp; r-Parent = pp; else else r

10、oot = r;root = r;return r;return r; / / Insert(x)Insert(x)運(yùn)算結(jié)束運(yùn)算結(jié)束運(yùn)算運(yùn)算Insert(const T& x)Insert(const T& x)的實(shí)現(xiàn)：的實(shí)現(xiàn)：運(yùn)算運(yùn)算Search(const T& x) Search(const T& x) 的實(shí)現(xiàn)的實(shí)現(xiàn)templatetemplateBinaryTreeNodeBinaryTreeNode* * BSTree:Search(const T& x) BSTree:Search(const T& x) constconst / /

11、找指向找指向x x所在的結(jié)點(diǎn)的指針?biāo)诘慕Y(jié)點(diǎn)的指針 BinaryTreeNode BinaryTreeNode * *p = root;p = root; while (p) /while (p) /* *p p中有元素中有元素if (x data) if (x data) p = p-LeftChild;p = p-LeftChild; else if (x p-data) else if (x p-data) p = p-RightChild;p = p-RightChild; else else break; /break; /找到找到x x所在的結(jié)點(diǎn)所在的結(jié)點(diǎn)* *p p return

12、 p; /return p; /當(dāng)當(dāng)x x不在樹中時(shí)不在樹中時(shí)p p為空為空 刪除刪除508060120110150557053刪除刪除6080551201101505370805012060110150557053刪除刪除43例例80501206011015055705343運(yùn)算運(yùn)算Delete(const T& x)的實(shí)現(xiàn)的實(shí)現(xiàn)運(yùn)算運(yùn)算Delete(const T& x)的實(shí)現(xiàn)（續(xù)）的實(shí)現(xiàn)（續(xù)）設(shè)要?jiǎng)h除二叉搜索樹中的設(shè)要?jiǎng)h除二叉搜索樹中的結(jié)點(diǎn)結(jié)點(diǎn)p p ，分三種情況：，分三種情況：p p為葉結(jié)點(diǎn)為葉結(jié)點(diǎn) 直接刪除節(jié)點(diǎn)直接刪除節(jié)點(diǎn)p pp p只有左子樹或右子樹只有左子樹或右子

13、樹p p只有左子樹只有左子樹 用用p p的左兒子代替的左兒子代替p p p p只有右子樹只有右子樹 用用p p的右兒子代替的右兒子代替p pp p左、右子樹均非空左、右子樹均非空找找p p的的左子樹的最大元素結(jié)點(diǎn)（即左子樹的最大元素結(jié)點(diǎn)（即p的前驅(qū)結(jié)的前驅(qū)結(jié)點(diǎn)），用該結(jié)點(diǎn)代替結(jié)點(diǎn)點(diǎn)），用該結(jié)點(diǎn)代替結(jié)點(diǎn)p，然后刪除該結(jié)點(diǎn)。，然后刪除該結(jié)點(diǎn)。運(yùn)算運(yùn)算Delete(const T& x)Delete(const T& x)的實(shí)現(xiàn)（續(xù)）的實(shí)現(xiàn)（續(xù)）templatetemplateBinaryTreeNodeBinaryTreeNode* * BSTree:Delete(const T&

14、amp; x) BSTree:Delete(const T& x)BinaryTreeNode BinaryTreeNode * *p = root, p = root, * *pp = 0; pp = 0; / /從根開始搜索值為從根開始搜索值為x x的結(jié)點(diǎn)的結(jié)點(diǎn), ,* *pppp記該結(jié)點(diǎn)記該結(jié)點(diǎn)的父的父結(jié)點(diǎn)結(jié)點(diǎn)while(p&p-data !=x)while(p&p-data !=x) pp = p;pp = p; if (x data)if (x data)p = p-LeftChild;p = p-LeftChild; elseelsep = p-RightC

15、hild;p = p-RightChild; if (!p)if (!p)return 0; /xreturn 0; /x不在樹中不在樹中, ,無需刪除無需刪除 if (p-LeftChild&p-RightChild) /pif (p-LeftChild&p-RightChild) /p有有2 2個(gè)兒子結(jié)點(diǎn)個(gè)兒子結(jié)點(diǎn) / / 找真正要?jiǎng)h除的結(jié)點(diǎn)找真正要?jiǎng)h除的結(jié)點(diǎn): :左子樹的最大元素左子樹的最大元素結(jié)點(diǎn)結(jié)點(diǎn)BinaryTreeNode BinaryTreeNode * *s = p-LeftChild,s = p-LeftChild, * *ps = p; ps = p; w

16、hile(s-RightChild)while(s-RightChild) ps=s;ps=s;s = s-RightChild;s = s-RightChild; p-data=s-data; / p-data=s-data; / 實(shí)現(xiàn)實(shí)現(xiàn)x x的刪除（替代）的刪除（替代） p = s;p = s;pp = pspp = ps / / 此時(shí)此時(shí)p p 最多只有最多只有1 1個(gè)兒子結(jié)點(diǎn)個(gè)兒子結(jié)點(diǎn), ,正是要?jiǎng)h除的結(jié)點(diǎn)正是要?jiǎng)h除的結(jié)點(diǎn)BinaryTreeNode BinaryTreeNode * *c; c; if (p-LeftChild)if (p-LeftChild) c = p-Left

17、Child; /cc = p-LeftChild; /c保存保存p p唯一唯一的左兒子的左兒子else else c = p-RightChild;c = p-RightChild;/ c/ c保存保存p p唯一唯一的右兒子的右兒子if (p = root)if (p = root) root = c;root = c;if (c) c-Parent = 0; if (c) c-Parent = 0; elseelse / / 確定確定p p是其父結(jié)點(diǎn)的左兒子還是右兒子是其父結(jié)點(diǎn)的左兒子還是右兒子if (p = pp-LeftChild)if (p = pp-LeftChild) pp-Lef

18、tChild = c; pp-LeftChild = c;elseelse pp-RightChild = c; pp-RightChild = c; if (c) if (c) c-Parent = p-Parent; c-Parent = p-Parent; delete p;delete p;return c; return c; /Delete(x) /Delete(x)運(yùn)算結(jié)束運(yùn)算結(jié)束 用二叉搜索樹實(shí)現(xiàn)字典用二叉搜索樹實(shí)現(xiàn)字典時(shí)間復(fù)雜性分析時(shí)間復(fù)雜性分析 最壞最壞情況分析情況分析member,insert,deletemember,insert,delete都需要都需要O(n)O(n

19、) 平均情況分析平均情況分析引入記號(hào)引入記號(hào): :記：記：p(n)p(n)為含有為含有n n個(gè)結(jié)點(diǎn)的二叉搜索樹的平均查找長(zhǎng)度。個(gè)結(jié)點(diǎn)的二叉搜索樹的平均查找長(zhǎng)度。顯然顯然p(0)=0,p(1)=1;p(0)=0,p(1)=1; 若設(shè)某二叉搜索樹的左子樹有若設(shè)某二叉搜索樹的左子樹有i i個(gè)結(jié)點(diǎn)，則：個(gè)結(jié)點(diǎn)，則：p(i)+1p(i)+1為查找左子樹中每個(gè)結(jié)點(diǎn)的平均查找長(zhǎng)度為查找左子樹中每個(gè)結(jié)點(diǎn)的平均查找長(zhǎng)度; ;p(n-i-1)+1p(n-i-1)+1為查找右子樹中每個(gè)結(jié)點(diǎn)的平均查找長(zhǎng)度；為查找右子樹中每個(gè)結(jié)點(diǎn)的平均查找長(zhǎng)度；由此構(gòu)造而得的二叉搜索樹在由此構(gòu)造而得的二叉搜索樹在n n個(gè)結(jié)點(diǎn)的查找概率

20、相等的個(gè)結(jié)點(diǎn)的查找概率相等的情況下，其平均查找長(zhǎng)度為：情況下，其平均查找長(zhǎng)度為： ) 1(111)(11),(inpinipininq) 1) 1()(1() 1)(1 (1(1) ),(1)(1010niniinpinipinninqnnp102)1()1()(11niinpiniipn對(duì)對(duì)n用數(shù)學(xué)歸納法可以證明用數(shù)學(xué)歸納法可以證明:nnplog41)(又假設(shè)又假設(shè)當(dāng)前的二叉搜索樹有當(dāng)前的二叉搜索樹有n個(gè)結(jié)點(diǎn)，而它是從空樹開始反復(fù)個(gè)結(jié)點(diǎn)，而它是從空樹開始反復(fù)調(diào)用調(diào)用n次的次的Insert運(yùn)算得到的，且被插入的運(yùn)算得到的，且被插入的n個(gè)元素的所有可能個(gè)元素的所有可能的順序是等概率的。則：的順序

21、是等概率的。則：102)(21niiipniiplog41)(當(dāng)當(dāng)n=1時(shí)顯然成立。若設(shè)時(shí)顯然成立。若設(shè)in時(shí)有時(shí)有 ，則，則112)log41(21)(niiinnp平均情況下的時(shí)間復(fù)雜度為：平均情況下的時(shí)間復(fù)雜度為：)(log nO1121122log421niniiniin112log82niiin)log)2/log(8212/12/12nninininin)log83)2/log(8(82222nnnnn)8log2(82222nnnnnlog41 運(yùn)算運(yùn)算Predecessor(x)Predecessor(x)和和Successor(x)Successor(x)的實(shí)現(xiàn)：的實(shí)現(xiàn)： 類

22、似于類似于Search(x)Search(x)算法算法 運(yùn)算運(yùn)算Range(y, z)Range(y, z)的實(shí)現(xiàn)：可借助于的實(shí)現(xiàn)：可借助于Search(y)Search(y)和和Successor(y)Successor(y)運(yùn)算運(yùn)算 首先，用首先，用Search(y)Search(y)檢測(cè)檢測(cè)y y是否在二叉搜索樹中，是是否在二叉搜索樹中，是則輸出則輸出y y，否則不輸出，否則不輸出y y； 然后，從然后，從y y開始，不斷地用開始，不斷地用SuccessorSuccessor找當(dāng)前元素在找當(dāng)前元素在二叉搜索樹中的后繼元素。當(dāng)找出的后繼元素二叉搜索樹中的后繼元素。當(dāng)找出的后繼元素x x滿滿

23、足足x x z z時(shí)，就輸出時(shí)，就輸出x x，并將，并將x x作為當(dāng)前元素。重復(fù)作為當(dāng)前元素。重復(fù)這個(gè)過程，直到找出的當(dāng)前元素的后繼元素大于這個(gè)過程，直到找出的當(dāng)前元素的后繼元素大于z z，或二叉搜索樹中已沒有后繼元素為止。或二叉搜索樹中已沒有后繼元素為止。 時(shí)間復(fù)雜度：若二叉樹搜索樹中有時(shí)間復(fù)雜度：若二叉樹搜索樹中有r r個(gè)元素個(gè)元素x x滿足滿足y y x x z z，則在最壞情況下用，則在最壞情況下用 時(shí)間，在時(shí)間，在平均情況下用平均情況下用 時(shí)間可實(shí)現(xiàn)時(shí)間可實(shí)現(xiàn)RangeRange運(yùn)算。運(yùn)算。 )(rnO)log(nrO 運(yùn)算運(yùn)算Range(y,z)Range(y,z)的改進(jìn)：的改進(jìn)：

24、考慮半無限查詢區(qū)域考慮半無限查詢區(qū)域 , 即找出二叉搜索樹中滿足即找出二叉搜索樹中滿足y x的所有元素的所有元素x。 ),y當(dāng)當(dāng)y不在二叉搜索樹中時(shí)，不在二叉搜索樹中時(shí)，產(chǎn)生一條從根到葉的路徑。產(chǎn)生一條從根到葉的路徑。如下圖如下圖(a) 當(dāng)當(dāng)y在二叉搜索樹中時(shí)，產(chǎn)在二叉搜索樹中時(shí)，產(chǎn)生一條從根到存儲(chǔ)元素生一條從根到存儲(chǔ)元素y的的結(jié)點(diǎn)的路徑。如下圖結(jié)點(diǎn)的路徑。如下圖(b) 在找到的搜索路徑上的所有結(jié)點(diǎn)可分為以下在找到的搜索路徑上的所有結(jié)點(diǎn)可分為以下3 3種情況，如下圖種情況，如下圖 ： 運(yùn)算運(yùn)算Range(y,z)Range(y,z)的實(shí)現(xiàn)：的實(shí)現(xiàn)： 可用類似于可用類似于Range(y,Rang

25、e(y,) )算法算法 從二叉搜索樹的根結(jié)點(diǎn)開始，同時(shí)與從二叉搜索樹的根結(jié)點(diǎn)開始，同時(shí)與y y和和z z比較比較, ,此時(shí)此時(shí), ,結(jié)點(diǎn)分類結(jié)點(diǎn)分類的情況可能有（見下圖）的情況可能有（見下圖） ： 運(yùn)算運(yùn)算Range(y,z)Range(y,z)的搜索路徑如下圖：的搜索路徑如下圖： 8.4 AVL樹8.4.0 8.4.0 引言引言AVLAVL樹產(chǎn)生的背景樹產(chǎn)生的背景 問題的提出問題的提出: :用二叉搜索樹實(shí)現(xiàn)有序字典在用二叉搜索樹實(shí)現(xiàn)有序字典在最壞情況下最壞情況下 member,insert,delete member,insert,delete都都需要需要O(n);O(n);平均情況下需要平

26、均情況下需要O(log n )O(log n )。 問在最壞情況下能降到問在最壞情況下能降到O(log n )O(log n )嗎？嗎？8.4 AVL樹8.4.0 8.4.0 引言引言AVLAVL樹產(chǎn)生的背景樹產(chǎn)生的背景( (續(xù)續(xù)) ) 解決問題的設(shè)想解決問題的設(shè)想: : n n個(gè)結(jié)點(diǎn)的二叉樹最矮是近似滿二叉樹個(gè)結(jié)點(diǎn)的二叉樹最矮是近似滿二叉樹, ,其高為其高為log n log n 。若放寬此限制為每一個(gè)結(jié)點(diǎn)的左子樹與右子樹高度差的絕對(duì)若放寬此限制為每一個(gè)結(jié)點(diǎn)的左子樹與右子樹高度差的絕對(duì)值不超過值不超過1 1，則二叉樹當(dāng)然就達(dá)不到最矮，則二叉樹當(dāng)然就達(dá)不到最矮, ,卻可望接近最矮卻可望接近最矮

27、, ,而不超過而不超過O(log n),O(log n),目的就達(dá)到了。這正是目的就達(dá)到了。這正是AVLAVL樹樹。剩下的問。剩下的問題是設(shè)法找一種在題是設(shè)法找一種在insertinsert和和deletedelete后只需后只需O(log n)O(log n)時(shí)間的時(shí)間的維護(hù)算法。維護(hù)算法。 設(shè)想的證實(shí)設(shè)想的證實(shí): : (1) (1) n n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的AVLAVL樹樹的高度的高度為為O(log n );O(log n );(2) insert(2) insert和和deletedelete后的后的維護(hù)算法在最壞的情況下只需維護(hù)算法在最壞的情況下只需O(logn )O(logn )的時(shí)間

28、。的時(shí)間。8.4 AVL8.4 AVL樹樹8.4.1 8.4.1 AVLAVL樹的定義和性質(zhì)樹的定義和性質(zhì) 遞歸定義遞歸定義: : 空的和單結(jié)點(diǎn)的二叉搜索樹都是空的和單結(jié)點(diǎn)的二叉搜索樹都是AVLAVL樹樹; ; 結(jié)點(diǎn)數(shù)大于結(jié)點(diǎn)數(shù)大于1 1的的二叉搜索樹二叉搜索樹, ,若滿足左子樹和右子樹都是若滿足左子樹和右子樹都是AVLAVL樹且左、右樹且左、右子樹高度之差的絕對(duì)值不超過子樹高度之差的絕對(duì)值不超過1,1,那么那么, ,它是它是AVLAVL樹。樹。 性質(zhì)性質(zhì): : (1)AVL (1)AVL樹樹T T的結(jié)點(diǎn)數(shù)的結(jié)點(diǎn)數(shù)n n與高度與高度h h的關(guān)系。的關(guān)系。 設(shè)高度設(shè)高度h h的的AVLAVL樹的

29、最少結(jié)點(diǎn)數(shù)樹的最少結(jié)點(diǎn)數(shù)N(h)N(h)。N(h)N(h)一定出現(xiàn)在樹一定出現(xiàn)在樹的左、右子樹中一棵高為的左、右子樹中一棵高為h-1,h-1,而另一棵高為而另一棵高為h-2h-2時(shí)。則時(shí)。則N(h)N(h)滿足如下遞歸方程：滿足如下遞歸方程： 11)2() 1(1201)(hhNhNhhhN8.4 AVL8.4 AVL樹樹15/2/ ) 51 (2/ ) 51 (1) 2()(22hhhFhN15/515/2/ )51 (2/ )51 (222hhh25/2/ ) 51 ()(2hhNn5log)2(log2251251nh328. 0)2log(4404. 125log)2(log25125

30、1nnh 解上面的遞歸方程得：解上面的遞歸方程得：由于由于因此因此8.4 AVL8.4 AVL樹樹8.4.2 8.4.2 旋轉(zhuǎn)變換旋轉(zhuǎn)變換 旋轉(zhuǎn)變換的目的：是調(diào)整結(jié)點(diǎn)的子樹高度，并維持旋轉(zhuǎn)變換的目的：是調(diào)整結(jié)點(diǎn)的子樹高度，并維持二叉搜索樹性質(zhì)，即結(jié)點(diǎn)中元素的中序性質(zhì)。二叉搜索樹性質(zhì)，即結(jié)點(diǎn)中元素的中序性質(zhì)。 旋轉(zhuǎn)變換分為單旋轉(zhuǎn)變換和雙旋轉(zhuǎn)變換旋轉(zhuǎn)變換分為單旋轉(zhuǎn)變換和雙旋轉(zhuǎn)變換2 2種類型。種類型。 單旋轉(zhuǎn)變換又分為右單旋轉(zhuǎn)變換和左單旋轉(zhuǎn)變換。單旋轉(zhuǎn)變換又分為右單旋轉(zhuǎn)變換和左單旋轉(zhuǎn)變換。雙旋轉(zhuǎn)變換又分為先左后右雙旋轉(zhuǎn)變換和先右后左雙旋轉(zhuǎn)變換又分為先左后右雙旋轉(zhuǎn)變換和先右后左雙旋轉(zhuǎn)變換。雙旋轉(zhuǎn)變換

31、。1、左單旋的情況、左單旋的情況原來的原來的AVL樹樹插入一結(jié)點(diǎn)，插入一結(jié)點(diǎn)，A點(diǎn)不平衡點(diǎn)不平衡左單旋的結(jié)果左單旋的結(jié)果2.右單旋的情況右單旋的情況原來的原來的AVL樹樹插入一結(jié)點(diǎn)，插入一結(jié)點(diǎn)，A點(diǎn)不平衡點(diǎn)不平衡右單旋的結(jié)果右單旋的結(jié)果原來的原來的AVL樹樹插入一結(jié)點(diǎn)，插入一結(jié)點(diǎn)，A點(diǎn)不平衡點(diǎn)不平衡先左旋先左旋再右旋再右旋3.先左后右雙旋的情況先左后右雙旋的情況4.先右后左雙旋的情況先右后左雙旋的情況原來的原來的AVL樹樹插入一結(jié)點(diǎn)，插入一結(jié)點(diǎn)，A點(diǎn)不平衡點(diǎn)不平衡先右旋先右旋再左旋再左旋8.4 AVL8.4 AVL樹樹8.4.3 AVL8.4.3 AVL樹的插入運(yùn)算樹的插入運(yùn)算 AVLAVL樹

32、與二叉搜索樹的插入運(yùn)算是類似的。惟一的不樹與二叉搜索樹的插入運(yùn)算是類似的。惟一的不同之處是，在同之處是，在AVLAVL樹中執(zhí)行樹中執(zhí)行1 1次二叉搜索樹的插入運(yùn)次二叉搜索樹的插入運(yùn)算，可能會(huì)破壞算，可能會(huì)破壞AVLAVL樹的高度平衡性質(zhì)，因此需要重樹的高度平衡性質(zhì)，因此需要重新平衡。新平衡。設(shè)新插入的結(jié)點(diǎn)為設(shè)新插入的結(jié)點(diǎn)為v v。從根結(jié)點(diǎn)到結(jié)點(diǎn)。從根結(jié)點(diǎn)到結(jié)點(diǎn)v v的路徑上，的路徑上，每個(gè)結(jié)點(diǎn)處插入運(yùn)算所進(jìn)入的子樹高度可能增每個(gè)結(jié)點(diǎn)處插入運(yùn)算所進(jìn)入的子樹高度可能增1 1。因。因此在執(zhí)行此在執(zhí)行1 1次二叉搜索樹的插入運(yùn)算后，需從新插入次二叉搜索樹的插入運(yùn)算后，需從新插入的結(jié)點(diǎn)的結(jié)點(diǎn)v v開始，

33、沿此插入路徑向根結(jié)點(diǎn)回溯，修正平開始，沿此插入路徑向根結(jié)點(diǎn)回溯，修正平衡因子，調(diào)整子樹高度，恢復(fù)被破壞的平衡性質(zhì)。衡因子，調(diào)整子樹高度，恢復(fù)被破壞的平衡性質(zhì)。 8.4 AVL8.4 AVL樹樹8.4.3 AVL8.4.3 AVL樹的插入運(yùn)算樹的插入運(yùn)算 新結(jié)點(diǎn)新結(jié)點(diǎn)v v的平衡因子為的平衡因子為0 0。現(xiàn)考察?，F(xiàn)考察v v的父結(jié)點(diǎn)的父結(jié)點(diǎn)u u。若。若v v是是u u的左的左兒子結(jié)點(diǎn)，則兒子結(jié)點(diǎn)，則bal(u)bal(u)應(yīng)當(dāng)減應(yīng)當(dāng)減1 1，否則，否則bal(u)bal(u)應(yīng)當(dāng)增應(yīng)當(dāng)增1 1。根據(jù)。根據(jù)修正后的修正后的bal(u)bal(u)的值分以下的值分以下3 3種情形討論。種情形討論。

34、 情形情形1 1：bal(u)=0bal(u)=0。此時(shí)以結(jié)點(diǎn)。此時(shí)以結(jié)點(diǎn)u u為根的子樹平衡，且其高為根的子樹平衡，且其高度不變。因此從根結(jié)點(diǎn)到結(jié)點(diǎn)度不變。因此從根結(jié)點(diǎn)到結(jié)點(diǎn)u u的路徑上各結(jié)點(diǎn)子樹高度不的路徑上各結(jié)點(diǎn)子樹高度不變，從而各結(jié)點(diǎn)的平衡因子不變。此時(shí)可結(jié)束重新平衡過變，從而各結(jié)點(diǎn)的平衡因子不變。此時(shí)可結(jié)束重新平衡過程。程。 情形情形2 2：| bal(u) | = 1| bal(u) | = 1。此時(shí)以結(jié)點(diǎn)。此時(shí)以結(jié)點(diǎn)u u為根的子樹滿足平為根的子樹滿足平衡條件，但其高度增衡條件，但其高度增1 1。此時(shí)將當(dāng)前結(jié)點(diǎn)向根結(jié)點(diǎn)方向上移，。此時(shí)將當(dāng)前結(jié)點(diǎn)向根結(jié)點(diǎn)方向上移，繼續(xù)考察結(jié)點(diǎn)繼續(xù)

35、考察結(jié)點(diǎn)u u的父結(jié)點(diǎn)的平衡狀態(tài)。的父結(jié)點(diǎn)的平衡狀態(tài)。8.4 AVL8.4 AVL樹樹 情形情形3 3：| bal(u) | = 2| bal(u) | = 2。 先討論先討論bal(u)=-2bal(u)=-2的情的情形。易知，此時(shí)結(jié)點(diǎn)形。易知，此時(shí)結(jié)點(diǎn)v v是結(jié)點(diǎn)是結(jié)點(diǎn)u u的左兒子結(jié)點(diǎn)，且的左兒子結(jié)點(diǎn)，且bal(v)bal(v) 0 0。又可分為。又可分為2 2種情形。種情形。 情形情形3.13.1：bal(v)=-1bal(v)=-1。此時(shí)作。此時(shí)作1 1次右單旋轉(zhuǎn)變換后，結(jié)次右單旋轉(zhuǎn)變換后，結(jié)束重新平衡過程。束重新平衡過程。 情形情形3.23.2：bal(v)=1bal(v)=1。此

36、時(shí)結(jié)點(diǎn)。此時(shí)結(jié)點(diǎn)v v的右兒子結(jié)點(diǎn)的右兒子結(jié)點(diǎn)x x非空。非空。根據(jù)根據(jù)bal(x)bal(x)的值，又分為的值，又分為bal(x)=0bal(x)=0、bal(x)=-1bal(x)=-1和和bal(x)=1bal(x)=1的的3 3種情形。在這種情形。在這3 3種情形下，分別作種情形下，分別作1 1次雙旋次雙旋轉(zhuǎn)變換后，結(jié)束重新平衡過程。轉(zhuǎn)變換后，結(jié)束重新平衡過程。情形情形3.1： 情形情形3.2 ： bal(x)=0情形情形3.2 ： bal(x)=-1情形情形3.2 ： bal(x)=18.4 AVL8.4 AVL樹樹8.4.4 AVL8.4.4 AVL樹的刪除運(yùn)算樹的刪除運(yùn)算 AVL

37、AVL樹與二叉搜索樹的刪除運(yùn)算是類似的。惟一的不同之樹與二叉搜索樹的刪除運(yùn)算是類似的。惟一的不同之處是，在處是，在AVLAVL樹中執(zhí)行樹中執(zhí)行1 1次二叉搜索樹的刪除運(yùn)算，可能會(huì)次二叉搜索樹的刪除運(yùn)算，可能會(huì)破壞破壞AVLAVL樹的高度平衡性質(zhì)，因此需要重新平衡。樹的高度平衡性質(zhì)，因此需要重新平衡。設(shè)被刪除結(jié)點(diǎn)為設(shè)被刪除結(jié)點(diǎn)為p p，其惟一的兒子結(jié)點(diǎn)為，其惟一的兒子結(jié)點(diǎn)為v v。結(jié)點(diǎn)。結(jié)點(diǎn)p p被刪除被刪除后，結(jié)點(diǎn)后，結(jié)點(diǎn)v v取代了它的位置。從根結(jié)點(diǎn)到結(jié)點(diǎn)取代了它的位置。從根結(jié)點(diǎn)到結(jié)點(diǎn)v v的路徑上，的路徑上，每個(gè)結(jié)點(diǎn)處刪除運(yùn)算所進(jìn)入的子樹高度可能減每個(gè)結(jié)點(diǎn)處刪除運(yùn)算所進(jìn)入的子樹高度可能減1 1。因此在。因此在執(zhí)行執(zhí)行1 1次二叉搜索樹的刪除運(yùn)算后，需從結(jié)點(diǎn)次二叉搜索樹的刪除運(yùn)算后，需從結(jié)點(diǎn)v v開始，沿此開始，沿此刪除路徑向根結(jié)點(diǎn)回溯，修正平衡因子，調(diào)整子樹高度，刪除路徑向根結(jié)點(diǎn)回溯，修正平衡因子，調(diào)整子樹高度，恢復(fù)被破壞的平衡性質(zhì)?；謴?fù)