數(shù)據(jù)結(jié)構(gòu)與算法--查找(2)

1、主講教師：章 英數(shù)據(jù)結(jié)構(gòu)與算法 2第19講 動態(tài)查找（2）本講知識點：本講知識點： (1)掌握平衡二叉樹的相關(guān)基礎(chǔ)知識掌握平衡二叉樹的相關(guān)基礎(chǔ)知識 (2)了解了解B樹的簡單操作樹的簡單操作 (3)了解了解B+樹的簡單操作樹的簡單操作難點：難點：平衡二叉樹平衡二叉樹3二叉排序樹回顧創(chuàng)建、插入、刪除三種操作10318287124谷歌工程師秀強悍搜索技術(shù)谷歌工程師秀強悍搜索技術(shù)引子5知識延伸云計算云計算框計算框計算強調(diào)后臺資源的整合，為客戶提供低強調(diào)后臺資源的整合，為客戶提供低成本的成本的ITIT基礎(chǔ)設(shè)施的配置基礎(chǔ)設(shè)施的配置強調(diào)前端用戶需求的研究和響應(yīng)，強調(diào)前端用戶需求的研究和響應(yīng)，為用戶提供一站式

2、的互聯(lián)網(wǎng)服務(wù)為用戶提供一站式的互聯(lián)網(wǎng)服務(wù)聽起來讓人覺得聽起來讓人覺得開心的開心的MP3MP3華中農(nóng)大飯菜可華中農(nóng)大飯菜可口又便宜的食堂口又便宜的食堂現(xiàn)在是否是向老現(xiàn)在是否是向老板提出加薪的最板提出加薪的最好時機好時機6n 查找的基本概念查找的基本概念n 查找分類查找分類n 穿插進(jìn)行實例研究穿插進(jìn)行實例研究查查找找n 靜態(tài)表的查找靜態(tài)表的查找n 動態(tài)查找表動態(tài)查找表n 哈希表哈希表順序查找順序查找有序表的查找有序表的查找二叉排序樹二叉排序樹二叉平衡樹二叉平衡樹B B樹樹B+B+樹樹查找知識體系結(jié)構(gòu)7AVL樹樹 Balanced Binary Tree一、平衡二叉樹一、平衡二叉樹平衡因子平衡因子B

3、F（Balance Factor 平衡度）平衡度）：結(jié)點：結(jié)點的平衡度是結(jié)點的左子樹的高度右子樹的高度。的平衡度是結(jié)點的左子樹的高度右子樹的高度。平衡二叉樹：平衡二叉樹：每個結(jié)點的平衡因子都為每個結(jié)點的平衡因子都為 1、1、0 的二叉樹?；蛘哒f每個結(jié)點的左右子樹的高的二叉樹?；蛘哒f每個結(jié)點的左右子樹的高度最多差一的二叉樹。度最多差一的二叉樹。注意：注意：完全二叉樹必為平衡樹，平衡樹不一定完全二叉樹必為平衡樹，平衡樹不一定是完全二叉樹。是完全二叉樹。8548254821是平衡樹是平衡樹 非平衡樹非平衡樹在平衡樹中，結(jié)點的平衡因子可以是在平衡樹中，結(jié)點的平衡因子可以是1，0，-1。結(jié)點的平衡因子結(jié)

4、點的平衡因子HL-HR一、平衡二叉樹一、平衡二叉樹9在左圖所示的平衡樹中插入數(shù)據(jù)域為在左圖所示的平衡樹中插入數(shù)據(jù)域為2的結(jié)點。的結(jié)點。 插入之后仍應(yīng)保持平衡二叉樹的性質(zhì)不變。插入之后仍應(yīng)保持平衡二叉樹的性質(zhì)不變。141253928635360501718730+1+1-1-1-100000000平衡樹平衡樹141253928635360501718730+1+1-1-1-1000000002+1+1原平衡原平衡度為度為 0危機結(jié)點危機結(jié)點如何用最簡單、最有效的辦法保持如何用最簡單、最有效的辦法保持平衡二叉樹的性質(zhì)不變？平衡二叉樹的性質(zhì)不變？10最小不平衡子樹：最小不平衡子樹：在平衡二叉樹的構(gòu)造

5、過程中，以距在平衡二叉樹的構(gòu)造過程中，以距離離插入結(jié)點插入結(jié)點最近的、且平衡因子的絕對值大于最近的、且平衡因子的絕對值大于1 1的結(jié)的結(jié)點為點為根根的子樹。的子樹。 542814一、平衡二叉樹一、平衡二叉樹11基本思想：基本思想：在構(gòu)造二叉排序樹的過程中，每插入在構(gòu)造二叉排序樹的過程中，每插入一個結(jié)點時，首先檢查是否因插入而破壞了樹的一個結(jié)點時，首先檢查是否因插入而破壞了樹的平衡性，若是，則找出最小不平衡子樹，在保持平衡性，若是，則找出最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整二叉排序樹特性的前提下，調(diào)整最小不平衡子樹最小不平衡子樹中各結(jié)點之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使中各結(jié)點之間

6、的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。之成為新的平衡子樹。AVL樹的構(gòu)造樹的構(gòu)造12例：設(shè)序列例：設(shè)序列20，35，40，15，30，25 ，構(gòu)造平衡樹。構(gòu)造平衡樹。203540352040153015AVL樹的構(gòu)造樹的構(gòu)造13352040153025202515354030354030202515AVL樹的構(gòu)造樹的構(gòu)造例：設(shè)序列例：設(shè)序列20，35，40，15，30，25 ，構(gòu)造平衡樹。構(gòu)造平衡樹。14設(shè)結(jié)點設(shè)結(jié)點A為為最小不平衡子樹最小不平衡子樹的根結(jié)點，對該子樹進(jìn)行的根結(jié)點，對該子樹進(jìn)行平衡調(diào)整歸納起來有以下四種情況：平衡調(diào)整歸納起來有以下四種情況： 1. LL型型 2. R

7、R型型 3. LR型型 4. RL型型平衡化旋轉(zhuǎn)有兩類：平衡化旋轉(zhuǎn)有兩類： 單旋轉(zhuǎn)單旋轉(zhuǎn) (左旋和右旋左旋和右旋) 雙旋轉(zhuǎn)雙旋轉(zhuǎn) (左旋加右旋和右旋加左旋左旋加右旋和右旋加左旋)AVL樹的平衡調(diào)整樹的平衡調(diào)整15 左改組左改組（新插入結(jié)點出現(xiàn)在危機結(jié)點的左子樹上（新插入結(jié)點出現(xiàn)在危機結(jié)點的左子樹上進(jìn)行的調(diào)整）進(jìn)行的調(diào)整）的情況分析的情況分析：1、LL 情況：（情況：（LL：表示新插入結(jié)點在危機結(jié)點的表示新插入結(jié)點在危機結(jié)點的 左子樹左子樹的的左子樹上左子樹上）AB+1h-10+2+1hh-1h-1LL 改組改組BLBRARBA0h0h-1h-1BLBRAR危機結(jié)點危機結(jié)點改組前：高度為改組前：

8、高度為 h + 1 中序序列：中序序列：ABBLBRAR改組后：高度為改組后：高度為 h + 1 中序序列：中序序列：ABBLBRAR注意：改組后注意：改組后 平衡度為平衡度為 0AB16旋轉(zhuǎn)：扁擔(dān)原理；沖突：旋轉(zhuǎn)優(yōu)先旋轉(zhuǎn)：扁擔(dān)原理；沖突：旋轉(zhuǎn)優(yōu)先61層層2層層例例:LL型型 單右旋轉(zhuǎn)平衡處理單右旋轉(zhuǎn)平衡處理 108791291012876172、LR 情況：（情況：（LR：表示新插入結(jié)點在危機結(jié)點的表示新插入結(jié)點在危機結(jié)點的 左子樹左子樹的的右子樹上右子樹上） 情況情況A：AB+1h-10+2-1h-1LR 改組改組BLAR危機結(jié)點危機結(jié)點改組前：改組前： 高度為高度為 h + 1 中序序列

9、：中序序列：注意：改組后注意：改組后 平衡度為平衡度為 0,0,-1CBCCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR改組后：改組后： 高度為高度為 h + 1 中序序列：中序序列：ABBLARCCLCRA18AB+1h-10+2-1h-1LR 改組改組BLAR危機結(jié)點危機結(jié)點改組前：改組前： 高度為高度為 h + 1 中序序列：中序序列：注意：改組后注意：改組后 平衡度為平衡度為 +1,0,0CBCCRCLh-1h-2h-20-1CB0h-1h-1BLARACLh-1CRh-2+10ABBLARCCRCL改組后：改組后： 高度為

10、高度為 h + 1 中序序列：中序序列：AABBLARCCRCL2、LR 情況：（情況：（LR：表示新插入結(jié)點在危機結(jié)點的表示新插入結(jié)點在危機結(jié)點的 左子樹左子樹的的右子樹上右子樹上） 情況情況B：192、LR 情況：（情況：（LR：表示新插入結(jié)點在危機結(jié)點的表示新插入結(jié)點在危機結(jié)點的 左子樹左子樹的的右子樹上右子樹上） 情況情況C：AB+10+2-1LR 改組改組危機結(jié)點危機結(jié)點改組前：改組前： 高度為高度為 2 中序序列：中序序列：注意：改組后注意：改組后 平衡度為平衡度為 0,0,0CBC0ABCA新插入結(jié)點新插入結(jié)點ABC改組后：改組后： 高度為高度為 2 中序序列：中序序列：CB0A

11、00 四種情況的區(qū)分：四種情況的區(qū)分： 如果如果 的平衡度為的平衡度為1 則為則為 LL型改組；型改組； 否則為否則為 LR型改組：若型改組：若 的平衡度為的平衡度為1、1 、0 ；則分別為；則分別為 LRA、LRB、LRC型改組。型改組。BC20804080206010305070859545例例:LR型型 先左旋再右旋平衡處理先左旋再右旋平衡處理 P264 218040802060103050708595452280408020601030507085954523右改組右改組（新插入結(jié)點出現(xiàn)在危機結(jié)點的右子樹上（新插入結(jié)點出現(xiàn)在危機結(jié)點的右子樹上進(jìn)行的調(diào)整）進(jìn)行的調(diào)整） 的情況分析：的情況

12、分析：1、RR 情況：情況：（RR：表示新插入結(jié)點在危機結(jié)點的表示新插入結(jié)點在危機結(jié)點的 右子樹右子樹的的右子樹上右子樹上） 處理圖形和處理圖形和 LL 鏡象相似鏡象相似2、RL 情況：情況：（RL：表示新插入結(jié)點在危機結(jié)點的表示新插入結(jié)點在危機結(jié)點的 右子樹右子樹的的左子樹上左子樹上） A、處理圖形和處理圖形和 LRA 鏡象相似鏡象相似 B、處理圖形和處理圖形和 LRB 鏡象相似鏡象相似 C、處理圖形和處理圖形和 LRC 鏡象相似鏡象相似245424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)設(shè)有關(guān)鍵碼序列設(shè)有關(guān)鍵碼序列5, 4, 2, 8, 6, 9，構(gòu)造平衡樹，構(gòu)造平衡樹LL型型R

13、L型型實戰(zhàn)實戰(zhàn)25426589642895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字繼續(xù)插入關(guān)鍵字 9RR型型26在平衡樹上查找過程中和給定值進(jìn)行比較的在平衡樹上查找過程中和給定值進(jìn)行比較的關(guān)鍵字個數(shù)不超過樹的深度。關(guān)鍵字個數(shù)不超過樹的深度。時間復(fù)雜度：時間復(fù)雜度： O(logn)性能分析性能分析27 內(nèi)查找內(nèi)查找前面介紹的查找方法，均適用于前面介紹的查找方法，均適用于查找存儲在內(nèi)存中的數(shù)據(jù)，統(tǒng)稱為內(nèi)查找方查找存儲在內(nèi)存中的數(shù)據(jù)，統(tǒng)稱為內(nèi)查找方法，它們適用于較小的表，而對較大的、存法，它們適用于較小的表，而對較大的、存儲在外存儲器上的文件就不合適了。儲在外存儲器上的文件就不合適了。 B樹樹是一種是一種多路平衡

14、多路平衡查找樹，這是一種適用查找樹，這是一種適用于于外查找外查找的方法的數(shù)據(jù)結(jié)構(gòu)。的方法的數(shù)據(jù)結(jié)構(gòu)。二、二、B樹樹28 B樹的定義：樹的定義：一棵一棵m階的階的B樹，或者為空樹，樹，或者為空樹，或者是滿足如下條件的或者是滿足如下條件的m叉樹：叉樹： （1）樹中每個結(jié)點至多有）樹中每個結(jié)點至多有m棵子樹；棵子樹； （2）若根結(jié)點不是葉子結(jié)點，則至少有）若根結(jié)點不是葉子結(jié)點，則至少有2棵棵子樹；子樹； （3）除根之外的所有非終端結(jié)點至少有）除根之外的所有非終端結(jié)點至少有m/2棵子樹；棵子樹； 即每個非根結(jié)點至少應(yīng)有即每個非根結(jié)點至少應(yīng)有m/2-1個關(guān)鍵字，個關(guān)鍵字，至多有至多有m-1個關(guān)鍵字。個關(guān)

15、鍵字。 二、二、B樹樹29 B樹的定義：樹的定義： （4）所有的非終端結(jié)點至少包含以下數(shù)據(jù)項：）所有的非終端結(jié)點至少包含以下數(shù)據(jù)項： （n,A0,K1,A1,K2,Kn,An），），其中，其中，n為關(guān)為關(guān)鍵字總數(shù)，鍵字總數(shù)，Ki（1in）是關(guān)鍵字，是關(guān)鍵字，Ai是指向子樹根是指向子樹根結(jié)點的指針。關(guān)鍵字是遞增有序的：結(jié)點的指針。關(guān)鍵字是遞增有序的：K1K2Kn，且且Ai(0in)所指子樹中所有結(jié)點的關(guān)鍵字均小于所指子樹中所有結(jié)點的關(guān)鍵字均小于Ki+1，An所指子樹中所有結(jié)點的關(guān)鍵字均大于所指子樹中所有結(jié)點的關(guān)鍵字均大于Kn。 （5）所有的葉子結(jié)點都在同一層上，并且不帶）所有的葉子結(jié)點都在同一層

16、上，并且不帶信息信息（可以看作是外部結(jié)點或查找失敗的結(jié)點，實際上（可以看作是外部結(jié)點或查找失敗的結(jié)點，實際上這些結(jié)點不存在，指向這些結(jié)點的指針為空）。這些結(jié)點不存在，指向這些結(jié)點的指針為空）。二、二、B樹樹30 nA0K1A1KnAnn+1n+1個分支個分支135118111127139347536419924378例如：一棵例如：一棵4階的階的B樹樹最多最多4棵子樹，則最多棵子樹，則最多3個關(guān)鍵字個關(guān)鍵字31 在在B樹上進(jìn)行查找的過程是一個順指針查找結(jié)樹上進(jìn)行查找的過程是一個順指針查找結(jié)點和在結(jié)點的關(guān)鍵字中進(jìn)行查找，交叉進(jìn)行的過點和在結(jié)點的關(guān)鍵字中進(jìn)行查找，交叉進(jìn)行的過程。程。 （1）在）在

17、B樹中找結(jié)點；樹中找結(jié)點； （2）在結(jié)點中找關(guān)鍵字。）在結(jié)點中找關(guān)鍵字。B樹的查找樹的查找32 要查找關(guān)鍵字要查找關(guān)鍵字k的記錄，首先從根結(jié)點開始，的記錄，首先從根結(jié)點開始，若找到則找所對應(yīng)的記錄，否則沿若找到則找所對應(yīng)的記錄，否則沿P所指的子所指的子樹繼續(xù)查找，其中樹繼續(xù)查找，其中 P0 K Kn Pi Ki K Min,只需直接刪除即可。只需直接刪除即可。 2、keynum=Min, 且所在結(jié)點的左或右兄弟結(jié)點且所在結(jié)點的左或右兄弟結(jié)點keynumMin 3、keynum=Min,且所在結(jié)點左右兄弟結(jié)點且所在結(jié)點左右兄弟結(jié)點keynum=MinB樹的刪除樹的刪除36jc fm ra bd

18、eg h ik ln ps t u x例如：刪除例如：刪除5階階B樹的樹的h、r、p、d結(jié)點。結(jié)點。第第1步：步：h-keynumMin,只需直接刪除即可。只需直接刪除即可。g i37jc fm ra bd eg ik ln ps t u x第第2步：步： r-keynum=Min，且，且r所在結(jié)點非所在結(jié)點非葉子結(jié)點，葉子結(jié)點，s移動到移動到r的位置的位置mt u xm s例如：刪除例如：刪除5階階B樹的樹的h、r、p、d結(jié)點。結(jié)點。38jc fm sa bd eg ik ln pt u xp-keynum=Min，且，且p所在結(jié)點的右兄弟結(jié)點所在結(jié)點的右兄弟結(jié)點keynumMin，s下移動

19、，下移動，t上移上移第第3步：步：n sm tu x例如：刪除例如：刪除5階階B樹的樹的h、r、p、d結(jié)點。結(jié)點。39jc fm ta bd eg ik ln su xd-keynum=Min，且刪除后，且刪除后，d所在結(jié)點及其所在結(jié)點及其左右兄弟結(jié)點均無多余結(jié)點。左右兄弟結(jié)點均無多余結(jié)點。第第4步：步：e例如：刪除例如：刪除5階階B樹的樹的h、r、p、d結(jié)點。結(jié)點。40jfm ta b c eg ik ln su xf j m tg ik ln su xa b c e例如：刪除例如：刪除5階階B樹的樹的h、r、p、d結(jié)點。結(jié)點。41 含有含有8個關(guān)鍵字的個關(guān)鍵字的3階階B樹，最多有幾個結(jié)樹，

20、最多有幾個結(jié)點，最少有幾個結(jié)點？畫出其形態(tài)。點，最少有幾個結(jié)點？畫出其形態(tài)。* * * * * *實戰(zhàn)實戰(zhàn)42 長度為長度為12的表的表Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec，按此順序建立一棵，按此順序建立一棵3階階B樹，畫出其形樹，畫出其形態(tài)。態(tài)。JanMay NovAugMar OctAprDec FebJul JunSep實戰(zhàn)實戰(zhàn)43 B樹的查找時間主要花費在搜索結(jié)點（訪問外存）樹的查找時間主要花費在搜索結(jié)點（訪問外存）上，即主要取決于上，即主要取決于B樹的深度樹的深度問：含問：含N個關(guān)鍵字的個關(guān)鍵字的m階階B樹的深度樹的深度H為多

21、少？為多少？先推導(dǎo)每一層所含最少結(jié)點數(shù)：先推導(dǎo)每一層所含最少結(jié)點數(shù)：第第1層層 1第第2層層 2第第3層層 2m/2 第第4層層 2 ( m/2 )2第第H+1層層 2 ( m/2 )H-1性能分析性能分析44 假設(shè)假設(shè)m階階B樹的深度為樹的深度為H+1，由于第，由于第H+1層為層為葉子結(jié)點，則有葉子結(jié)點，則有N+1個葉子結(jié)點，個葉子結(jié)點， N+12( m/2 )H-1 則則 H-1log m/2 (N+1)/2) Hlog m/2 (N+1)/2)+1所以，在含所以，在含N個關(guān)鍵字的個關(guān)鍵字的B樹上進(jìn)行一次查找，樹上進(jìn)行一次查找，需訪問的結(jié)點個數(shù)不超過需訪問的結(jié)點個數(shù)不超過log m/2 (N+1)/2)+1性能分析性能分析45 B+樹的定義：樹的定義：B+樹是應(yīng)文件系統(tǒng)所需而出的樹是應(yīng)文件系統(tǒng)所需而出的一種一種B樹的變型樹。樹的變型樹。 一棵一棵m階