數(shù)據(jù)結(jié)構(gòu)課件：第8章 查找

1、第八章 查 找查找-即在某種數(shù)據(jù)結(jié)構(gòu)中找出滿足條件的結(jié)點(diǎn)。查找表：是由同一類型的數(shù)據(jù)元素構(gòu)成的集合。查找結(jié)果：成功、失敗。平均查找長(zhǎng)度查找一個(gè)結(jié)點(diǎn)所作的平均比較次數(shù)（衡量一個(gè)查找算法優(yōu)劣的主要標(biāo)準(zhǔn)）。查找表靜態(tài)查找表( 建表、查找、讀表元素)動(dòng)態(tài)查找表( 建表、查找、讀表元素、 插入、刪除)一、線性表的查找 8.1.1 無(wú)序表的順序查找 8.1.2 有序表的順序查找 8.2.1 對(duì)半查找二、樹形結(jié)構(gòu)的查找三、散列一、線性表的查找8.1.1 無(wú)序表的順序查找現(xiàn)實(shí)生活中順序查找的例子很多。比如，在一個(gè)班級(jí)的名冊(cè)中查找某個(gè)學(xué)生的名字。通常的做法是，順序比較名冊(cè)中的每個(gè)名字。這就是順序查找。順序查找的

2、基本思想：從線性表的起始結(jié)點(diǎn)開始，逐個(gè)檢查每個(gè)結(jié)點(diǎn)，或者找到關(guān)鍵詞 Ki=K，或者以in (i為表中記錄的下標(biāo)，n為線性表的元素個(gè)數(shù))查找失敗告終。 順序查找很簡(jiǎn)單、明顯，該方法是討論查找問題的一個(gè)有用的起點(diǎn)，因?yàn)樵S多錯(cuò)綜復(fù)雜的查找算法都是以它為基礎(chǔ)的。算法S ( N，R，K . i ) /* 給定包含N個(gè)記錄R1，R2，RN，其對(duì)應(yīng)的關(guān)鍵詞分別為K1，K2，KN的一個(gè)表，S查找一個(gè)給定的變?cè)狵 . 這里假定N 1 . */S1. 初始化 置i 1 .S2. 比較關(guān)鍵詞 如果K Ki，則算法成功結(jié)束.S3. 推進(jìn)i 置i i 1 .S4. i N ? 若i N，則返回步驟S2；否則此算法以查找

3、失敗告終 . 算法S ( N，R，K . i ) /* 給定包含N個(gè)記錄R1，R2，RN，其對(duì)應(yīng)的關(guān)鍵詞分別為K1，K2，KN的一個(gè)表，S查找一個(gè)給定的變?cè)狵 . 這里假定N 1 . */ S1 初始化 i1 S2 比較關(guān)鍵詞 WHILE (i N) & (KKi) DO ii+1. 算法Q（R，n，Ki）/* 給定記錄R1，R2，Rn的表，其中Ri 的關(guān)鍵詞為Ki（1in），本算法查找關(guān)鍵詞等于K的記錄*/Q1 初始化 i1 Kn+1K Q2 比較關(guān)鍵詞 WHILE KKi DO ii+1. 從算法S到算法Q利用了一個(gè)重要的“加速原理”: 當(dāng)算法的一個(gè)內(nèi)循環(huán)要測(cè)試兩個(gè)或多個(gè)條件時(shí)，應(yīng)力圖將其

4、減少成一個(gè)條件。算法Q大約比算法S節(jié)省百分之二十的運(yùn)行時(shí)間。算法Q（R，n，Ki）Q1 初始化 i1 Kn+1K Q2 比較關(guān)鍵詞 WHILE KKi DO ii+1. 序號(hào) 元素341527861213212428304224查找24 查找成功的平均查找長(zhǎng)度： E(n)查找失敗的查找長(zhǎng)度：n+1 順序查找的時(shí)間復(fù)雜度：O(n)i=1i=nPi . Cii=1i=nCi 1ni=1i=ni 1n n+12順序查找優(yōu)缺點(diǎn): 優(yōu)點(diǎn): 算法簡(jiǎn)單，且適用面廣。 缺點(diǎn): 平均查找長(zhǎng)度較大，n很大時(shí)查找效率低。一、線性表的查找 8.1.1 無(wú)序表的順序查找 8.1.2 有序表的順序查找 8.2.1 對(duì)半查

5、找 8.1.2 有序表的順序查找算法T（R，n，Ki） /*表R1，R2，Rn按照關(guān)鍵詞遞增有序*/ T1 初始化 i1 Kn+1+ . T2 順序與表中各元素比較 WHILE KKi DO ii+1. T3 若未找到，設(shè)in+1 IF KKi THEN in+1. 算法成功結(jié)束時(shí)1in，否則i=n+1與算法Q相比較，對(duì)于成功的查找，算法T的期望復(fù)雜性為(n+1)/2，與算法Q的期望復(fù)雜性相同；而對(duì)于不成功的查找算法T的期望復(fù)雜性為(n+1)/2，而算法Q為n+1，算法T比算法Q大約快一倍。先將文件排序，再查找，是一個(gè)快速的查找方法。但如果只需對(duì)表查找一次，則進(jìn)行順序查找比對(duì)這個(gè)表進(jìn)行完整排序

6、要快；如果要在同一個(gè)文件中不斷進(jìn)行查找，那么將表按序排列再查找是個(gè)很好的方法。8.1線性表的查找 8.1.1 無(wú)序表的順序查找 8.1.2 有序表的順序查找 8.2.1 對(duì)半查找 8.2.1 對(duì)半（折半，二分）查找1、算法思想：K與待查表的中間記錄的關(guān)鍵詞 Kn/2比較，其結(jié)果有三：KKn/2 ，K= Kn/2 ，KKn/2由情況知查找成功結(jié)束，由情況和能確定下一次應(yīng)到表的哪一半中去查找，即將查找范圍縮小一半；并對(duì)確定的那一半重復(fù)上述過(guò)程，直至找到所查記錄或確定該記錄不在表中。例 假定有序表A中10個(gè)元素的關(guān)鍵詞序列：12，23，26，37，54，60，68，75，82，96 當(dāng)給定值分別為9

7、6和58時(shí)進(jìn)行二分查找。查找k=96時(shí)二分查找過(guò)程(4次比較成功） 1 2 3 4 5 6 7 8 9 1012 23 26 37 54 60 68 75 82 96s=1e=10e=1012 23 26 37 54 60 68 75 82 96s=1i=5e=1012 23 26 37 54 60 68 75 82 96s=6i=812 23 26 37 54 60 68 75 82 96s=e=10i=10e=1012 23 26 37 54 60 68 75 82 96s=9i=9查找k=58時(shí)二分查找過(guò)程(3次比較失敗） 1 2 3 4 5 6 7 8 9 1012 23 26 37

8、54 60 68 75 82 96e=1012 23 26 37 54 60 68 75 82 96s=1i=5e=1012 23 26 37 54 60 68 75 82 96s=6i=812 23 26 37 54 60 68 75 82 96s=6e=512 23 26 37 54 60 68 75 82 96s=6e=7i=6 2、對(duì)半查找算法描述算法B ( N，R，K . i ) /*給定關(guān)鍵詞在遞增次序下（即K1 K2 KN）包含N個(gè)記錄R1, R2, , RN 的表，查找給定變?cè)狵 . 用兩個(gè)指針s和e分別指向當(dāng)前被查找文件之最左邊和最右邊記錄的下標(biāo)。*/B1. 初始化 置s 1

9、 . e N .B2. 取中點(diǎn) 如果e s，則該算法以失敗告終；否則，置i (s + e) /2。B3. 比較 如果K Ki，則轉(zhuǎn)步驟B5；如果K = Ki，則算法成功結(jié)束。B4. 調(diào)整e 置e i 1，并返回B2 .B5. 調(diào)整s 置s i 1，并返回B2 . 算法B ( N，R，K . i ) B1. 初始化 置s 1 . e N .B2. 取中點(diǎn) 如果e s，則該算法以失敗告終；否則， 置i (s + e) /2。B3. 比較 如果K Ki， 則轉(zhuǎn)步驟B5；如果K = Ki，則算法成功結(jié)束。B4. 調(diào)整e 置e i 1，并返回B2 .B5. 調(diào)整s 置s i 1，并返回B2 . 12 2

10、3 26 37 54 60 68 75 82 96s=1e=10i=512 23 26 37 54 60 68 75 82 96s=6e=10i=812 23 26 37 54 60 68 75 82 96s=6e=7i=612 23 26 37 54 60 68 75 82 96s=6e=5算法B ( N，R，K . i ) B1. 初始化 置s 1 . e N .B2. 取中點(diǎn) 如果e s，則該算法以失敗告終；否則， 置i (s + e) /2。B3. 比較 如果K Ki， 則轉(zhuǎn)步驟B5；如果K = Ki，則算法成功結(jié)束。B4. 調(diào)整e 置e i 1，并返回B2 .B5. 調(diào)整s 置s i

11、 1，并返回B2 . 1 2 3 4 5 6 7 8 9 1012 23 26 37 54 60 68 75 82 96s=1e=1012 23 26 37 54 60 68 75 82 96s=1e=10i=512 23 26 37 54 60 68 75 82 96s=6e=10i=812 23 26 37 54 60 68 75 82 96s=9e=10i=912 23 26 37 54 60 68 75 82 96s=e=10i=10二叉判定樹 二叉判定樹，T（s，e）的遞歸定義如下： (1)當(dāng)e-s+10時(shí)，T（s，e）為空樹； (2)當(dāng)e-s+10時(shí)，二叉判定樹的根結(jié)點(diǎn)是有序表中序

12、號(hào)為(e+s)/2的記錄，根結(jié)點(diǎn)的左子樹是與有序表Rs，Rs+1，R(e+s)/2 -1相對(duì)應(yīng)的二叉判定樹，根結(jié)點(diǎn)的右子樹是與有序表R(e+s)/2+1，R(e+s)/2+2，Re相對(duì)應(yīng)的二叉判定樹。 3、對(duì)半查找算法分析 對(duì)半查找 判定樹每個(gè)圓圈結(jié)點(diǎn)表示關(guān)鍵詞比較 K : Ki4528136971054758296231226603768= 1 2 3 4 5 6 7 8 9 1012 23 26 37 54 60 68 75 82 96T（1，10）的二叉判定樹：搜索K=964528136971054758296231226603768452813697105475829623122660

13、3768T（1，10）的二叉判定樹：搜索K=58T(1, 10)查找成功的平均查找長(zhǎng)度4528136971054758296231226603768ASLSUCC (1*1+2*2+3*4+4*3)/10 29/10 2.9查找失敗的平均查找長(zhǎng)度： ASLUNSUCC En/(n+1) (3*5+4*6)/11 39/114528136971054758296231226603768 I表示增長(zhǎng)樹的內(nèi)路徑長(zhǎng)度 E表示增長(zhǎng)樹的外路徑長(zhǎng)度 n是二叉樹中結(jié)點(diǎn)數(shù)，則有: E=I+2n 例 I=19,E=39,n=1045281369710547582962312266037684、二分查找總結(jié): 優(yōu)點(diǎn)

14、:查找效率為O(log2n) /比順序查找高 缺點(diǎn):只適用于有序表，且限于順序存儲(chǔ)結(jié)構(gòu)，對(duì)線性鏈表無(wú)法進(jìn)行二分查找。一、線性表的查找二、樹形結(jié)構(gòu)的查找8.3 二叉查找樹8.5 高度平衡樹8.7 B樹及其變型三、散列8.3.1 二叉查找樹的基本概念和性質(zhì) 定義: 一棵二叉查找樹是一棵可能為空的二叉樹形，并且關(guān)鍵詞各不相同。二叉查找樹中的任一結(jié)點(diǎn)P，它的左子樹中結(jié)點(diǎn)的關(guān)鍵詞都小于KEY(P)，而右子樹中結(jié)點(diǎn)的關(guān)鍵詞都大于KEY(P)，并且結(jié)點(diǎn)P的左右子樹也都是二叉查找樹。1、二叉查找樹的結(jié)點(diǎn)結(jié)構(gòu)： LLINK和RLINK是鏈接字段，KEY為該結(jié)點(diǎn)的關(guān)鍵詞。2、基本操作1）創(chuàng)建2）查找3）插入4）刪

15、除5）排序 LLINKKEYDATARLINK二叉查找樹的創(chuàng)建如何建立一棵二叉查找樹。 例有一數(shù)據(jù)集合53,78,65,17,87,09,81,45,23一棵非空的二叉查找樹中的所有結(jié)點(diǎn)在中根次序下按其關(guān)鍵詞由小到大排序。1、二叉查找樹的查找 算法 BST (T, K . found) BST1 由根結(jié)點(diǎn)開始 PT foundfalse BST2 比較 WHILE Pnull AND NOT(found) DO CASE DO （KKEY（P）：PRLINK（P）. K=KEY（P）：foundtrue） 設(shè)表中元素的關(guān)鍵詞K1K2Kn，則查找成功應(yīng)該終止于Ri(內(nèi)結(jié)點(diǎn))，而查找失敗應(yīng)終止在n

16、1個(gè)記錄間隔(或者稱外結(jié)點(diǎn)，即KiKKi+1的情形)。35612OEAUI42、二叉查找樹的插入(動(dòng)態(tài)樹) 35612OEAUI436712OEAUI5H446712OEAUI3K5二叉查找樹的插入算法算法T ( root, K . p) /* 給定一棵以二叉查找樹形式存儲(chǔ)的記錄表，本算法查找一給定變?cè)狵 . 如果K不在表中，則在樹的適當(dāng)位置插入包含K的一個(gè)新結(jié)點(diǎn)?？兆訕湟钥罩羔槺硎荆兞縭oot指向此樹的根。*/T1. 初始化 置p root . / 指針p將沿樹下移T2. 比 較 如果K key(p)，則轉(zhuǎn)到T4；如果K key (p)，則查找成功結(jié)束.T3. 左 移 如果llink (p

17、) ，則置p llink (p)，并轉(zhuǎn)回T2；否則轉(zhuǎn)到T5 .T4. 右 移 如果rlink (p) ，則置p rlink (p)，并轉(zhuǎn)回T2 .T5. 插入樹形中 置q AVAIL . / q為新結(jié)點(diǎn)的地址 置key (q) K，llink (q) rlink (q) . 若K key (p)，則置llink (p) q，否則置rlink (p) q . 置p q，本算法成功結(jié)束顯然，算法T的查找執(zhí)行時(shí)間與算法B同階（對(duì)隨機(jī)輸入），即為O (log 2 N)4、二叉查找樹的刪除 假定指針q指向二叉查找樹中待刪除的結(jié)點(diǎn)，則刪除q后的樹仍為二叉查找樹。 刪除q后，由q的中根后繼或者中根前驅(qū)結(jié)點(diǎn)代

18、替q，刪除過(guò)程分三種情形: 1) q無(wú)右兒子； 2) q有右兒子r，但r無(wú)左兒子； 3) q的右兒子r有左兒子。二叉查找樹的刪除分三種情況加以討論(刪除q)：（1） RLINK(q) . q無(wú)右兒子，此時(shí)用q的左兒子代替q所指結(jié)點(diǎn)qsRLINK(q) = rsLLINK(q)r二叉查找樹的刪除分三種情況加以討論(刪除q)：（1）LLINK(q)= 此時(shí)用q的右兒子RLINK(q)代替q所指結(jié)點(diǎn). qsLLINK(q) = rsRLINK(q)r RLINK(q)，且LLINK(RLINK(q)= 當(dāng)RLINK(q)，則應(yīng)考慮q的右兒子 r=RLINK(q) 若r的左兒子LLINK(r)=，則

19、應(yīng)該用以結(jié)點(diǎn)r為根的子樹形去取代q . 即 LLINK(r)LLINK(q) . qLLINK(q)RLINK(q)sRLINK(s)rsr RLINK(q)且LLINK（RLINK(q)） 在這種情況下，應(yīng)不斷地取LLINK(RLINK(q)的LLINK域值，即取(LLINK(RLINK(q)，直到找到為止. 然后用LLINK字段為的那個(gè)RLINK(q)的左后代s來(lái)取代q ； r為s的雙親，現(xiàn)在以s的右子樹形（即以RLINK(s)為根的樹形）作為r的左子樹形. sLLINK(s) 原LLINK(q)RLINK(s) 原RLINK(q)LLINK(r) 原RLINK(s)rqsLLINK(q)

20、RLINK(s)RLINK(q)r372523751248608268963) q的右兒子r有左兒子，以該左兒子為根的子樹的最左下結(jié)點(diǎn)s取代q，同時(shí)將s的父結(jié)點(diǎn)指向原s的右子樹。 (例如刪除25)二叉查找樹的刪除（情況三）372375124860826896算法D ( q，a. )/*刪除二叉查找樹中的結(jié)點(diǎn)q,指針a指向結(jié)點(diǎn)q的父親。*/D1. rlink (q) t q . 若rlink (t) ，則t llink (t) ，并轉(zhuǎn)到步驟D4 . / t指向取代q位置的結(jié)點(diǎn)D2. llink(rlink(q) r rlink (t) . 若llink (r) ，則llink (r) llink

21、 (q)，tr，轉(zhuǎn)D4 .152045310697刪除4D3. llink (rlink (q) s llink (r) . 若llink (s) ，則r s并重復(fù)到llink (s) 為止 . 置llink (s) llink (t)，llink (r) rlink (s)，rlink (s) rlink (t)，t s .D4. 接樹與釋放結(jié)點(diǎn)q 若llink (a) q，則llink (a) t；否則rlink (a) t . 然后置AVAIL q . 152045310697刪除4二叉查找樹的簡(jiǎn)單分析由于算法 D 左右兩邊很不對(duì)稱，有理由認(rèn)為一連串的隨機(jī)刪除和插入操作將使樹失去平衡，但

22、事實(shí)上，刪除操作不會(huì)使樹退化。定理 8.3 （T. N. Hibbard，1962）通過(guò)算法 D 從一株隨機(jī)二叉查找樹中刪除一個(gè)隨機(jī)元素之后，得到的樹仍是隨機(jī)的。結(jié)論 : 在隨機(jī)情況下，二叉查找樹操作的平均時(shí)間為O (log2N) 但在特定情況下，會(huì)產(chǎn)生形同線性鏈表的退化的二叉查找樹形，從而使最壞情況查找時(shí)間達(dá)O(N) .二、樹形結(jié)構(gòu)的查找8.3 二叉查找樹8.5 平衡樹8.7 B樹及其變型8.5.1 高度平衡樹定義8.2 ：一棵二叉查找樹稱為高度平衡二叉查找樹（高度平衡樹、平衡樹），當(dāng)且僅當(dāng)或者由單一的外結(jié)點(diǎn)組成，或者由兩個(gè)子樹形Tl和Tr組成，且滿足： (1)| h (Tl) h (Tr)

23、 |1，其中h (T)表示樹T的高度； (2)Tl和Tr都是高度平衡樹. 定義8.3 設(shè)T為增長(zhǎng)二叉樹，q是T之內(nèi)結(jié)點(diǎn)，qL 和qR 是q的左、右子樹，hL和hR 分別是qL和qR 的高度，q的平衡系數(shù)（或曰平衡因子）BF(q)定義為hR hL .高度平衡樹的結(jié)點(diǎn)結(jié)構(gòu)：B為平衡系數(shù)。KEYDATABLLINKRLINK平衡樹 平衡樹 非平衡樹1-10-1100110-2-10平衡二叉查找樹的構(gòu)造 基本思想： 在構(gòu)造二叉查找樹的過(guò)程中，每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否因插入而破壞了樹的平衡性？ 若是，則找出其中最小不平衡子樹，在保持查找樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的連接關(guān)系，

24、以達(dá)到新的平衡。 平衡二叉查找樹的構(gòu)造最小不平衡子樹-以離插入點(diǎn)最近、且平衡因子絕對(duì)值大于1的結(jié)點(diǎn)作根的子樹（設(shè)：二叉查找樹的最小不平衡子樹的根結(jié)點(diǎn)是A）。34852092-21020567480165-10780平衡二叉查找樹的構(gòu)造調(diào)整子樹的規(guī)律分為：LL型調(diào)整RR型調(diào)整LR型調(diào)整RL型調(diào)整LL型調(diào)整 由于在A的左孩子（L）的左子樹（L）上插入結(jié)點(diǎn)，使A的平衡因子由-1變?yōu)?2而失去平衡。A-1B0A-2B-1插入前插入后hh+1LL型調(diào)整調(diào)整規(guī)則：將A的左孩子B提升為新的二叉樹的根；將原來(lái)的根A連同其右子樹向右下旋轉(zhuǎn)，使其成為B的右子樹；而B的右子樹則作為左子樹接到A上。A-2B-1B0A

25、0LL型調(diào)整實(shí)例3048504560-100000插入20調(diào)整5045603048-2-1-1002005045603048-2-1-100200305020600-100004548RR型調(diào)整由于在A的右孩子（R）的右子樹（R）上插入結(jié)點(diǎn)，使A的平衡因子由1變?yōu)?，從而失去平衡。A1B0A2B1插入前插入后hh+1RR型調(diào)整RR型調(diào)整規(guī)則：將A的右孩子B提升為新的二叉樹的根；將原來(lái)的根A連同其左子樹向左下旋轉(zhuǎn)，使其成為B的左子樹；而B的原左子樹則作為右子樹接到A上。B0A0A2B1RR型調(diào)整實(shí)例165555060450000插入70調(diào)整5045603048211002005060456555

26、00700506545700001006055LR型調(diào)整由于在A的左孩子（L）的右子樹（R）上插入結(jié)點(diǎn)，使A的平衡因子由-1變?yōu)?2，從而失去平衡。 /和為h+1層, 和為h層A-1B0C0A-2B1C-1插入前插入后hh+1h+1LR型調(diào)整規(guī)則：將A的LR孫子C提升為新的二叉樹的根；原C的雙親B邊同其左子樹向左下旋轉(zhuǎn)，使其成為新根C的左子樹，而原C的左子樹則成為B的右子樹；原根A連同其右子樹向右下旋轉(zhuǎn)，使其成為新根C的右子樹，而原C的右子樹則成為A的左子樹。C0B0A1A-2B1C-1LR型調(diào)整實(shí)例348520921-10-1056748006500插入前LR型調(diào)整實(shí)例插入78調(diào)整后3485

27、20922-10-20567480-165107803420851-10015674800650078920RL型調(diào)整由于在A的右孩子（R）的左子樹（L）上插入結(jié)點(diǎn)，使A的平衡因子由1變?yōu)?，從而失去平衡，其調(diào)整規(guī)則與LR型對(duì)稱。/和為h+1層, 和為h層A1B0C0A-2B-1C1h+1h插入前插入后RL型調(diào)整C0A0B1A2B-1C-1平衡二叉查找樹構(gòu)造綜合實(shí)例(a)464615(b)201546(c)LR型調(diào)整插入46插入15插入20平衡二叉查找樹構(gòu)造綜合實(shí)例201546(c)LR型調(diào)整35201546(d)28201535(e)LL型調(diào)整46平衡二叉查找樹構(gòu)造綜合實(shí)例28201535(

28、e)LL型調(diào)整4628201535(f)RR型調(diào)整4658平衡二叉查找樹構(gòu)造綜合實(shí)例28201535 (g)46581828201535(h)RL型調(diào)整50581846理想平衡樹的概念 理想平衡樹-在一棵二叉樹中，若除最后一層外，其余各層都是滿的，而最后一層的結(jié)點(diǎn)可以任意分布，則稱此樹為理想平衡樹?；蚍Q理想平衡二叉樹 理想平衡二叉樹包含了完全二叉樹和滿二叉樹。理想平衡二叉樹的深度，與完全二叉樹的深度一樣，即為 log2n+1 。二、樹形結(jié)構(gòu)的查找8.3 二叉查找樹8.5 高度平衡樹8.7 B樹及其變型8.7 B樹及其變形樹 前面介紹的樹形查找方法，主要屬于內(nèi)查找方法，適用于被檢索文件能完整地被

29、放到計(jì)算機(jī)內(nèi)存中的情形。如果文件很大，以至于計(jì)算機(jī)內(nèi)存容納不下時(shí)，則必須放在磁盤等外存儲(chǔ)器上。當(dāng)人們想從一個(gè)存放在磁盤上的大文件中查找某些信息時(shí)，則需要去研究一種新的查找方法外查找。8.7.1 多叉樹 1、基本概念 1970年，拜爾(R. Bayer) 和麥克瑞特(E. McCreight )提出一種新的外查找樹，稱為B樹。這是一種多叉平衡樹形，它在插入或刪除操作中有簡(jiǎn)單的平衡算法。B樹及它的一些改進(jìn)形式已成為索引文件的有效結(jié)構(gòu)，得到了廣泛的應(yīng)用。定義8.7 一個(gè)m階的B樹滿足下述條件： 每個(gè)結(jié)點(diǎn)有 m個(gè)兒子； 除根和葉之外的每個(gè)結(jié)點(diǎn)有 m/2 個(gè)兒子； 根結(jié)點(diǎn)至少要有兩個(gè)兒子（除非它本身又是

30、一個(gè)葉結(jié)點(diǎn)）； 具有 k 個(gè)兒子的非葉結(jié)點(diǎn)包含k1個(gè)關(guān)鍵詞； 所有的葉結(jié)點(diǎn)都出現(xiàn)在同一層上，并且它們都不帶有信息.8.7.2 B樹233449031097137191 011017023041047059067073083103109127149157167179197211227283353401241257269277307313331347367379389419431439499599677773829883919907937947967461467487509523547563571587607617631643653661691709727739751761797811823853

31、859877一個(gè) 7 階B樹，其所有的葉都在第 3 層上葉不帶有信息，可以認(rèn)為它們是外部結(jié)點(diǎn)，實(shí)際上它們不在樹中，所以指向葉的指針為空。031097137191011017023179197211227103109127149157167083073067059047041在前面的 7 階B樹中，每個(gè)結(jié)點(diǎn)(除了根和葉)，有7/2 到7個(gè)兒子，故可有3，4，5 或 6 個(gè)關(guān)鍵詞。根結(jié)點(diǎn)允許有1 至 6 個(gè)關(guān)鍵詞，根結(jié)點(diǎn)包含兩個(gè)關(guān)鍵詞。這個(gè)B樹的所有葉子都在第 3 層上。應(yīng)強(qiáng)調(diào)指出的是： 每個(gè)非葉結(jié)點(diǎn)中的關(guān)鍵詞是按從左到右的遞增順序排列的； 葉子的總數(shù)比關(guān)鍵詞總數(shù)多1； 和兩點(diǎn)表明了B樹是二叉查找

32、樹的一個(gè)自然推廣。很自然，我們對(duì) 1 階和 2 階B樹毫無(wú)興趣，這里只考慮m 3 的情況。階為 3 的B樹，也叫做 2-3 樹。 一個(gè)包含j個(gè)關(guān)鍵詞和j +1個(gè)指針的B樹結(jié)點(diǎn)如圖所示。結(jié)點(diǎn)之關(guān)鍵詞滿足 K1 K2 Kj ，指針Pi 指向一個(gè)其所有關(guān)鍵詞都在K i和Ki+1之間的子樹形。因此，在B樹中進(jìn)行查找是十分簡(jiǎn)單的。P0K1P1K2P2Pj1KjPjB-樹的結(jié)點(diǎn)P在B 樹的每個(gè)結(jié)點(diǎn)包含有一組指針Ti ，指向?qū)嶋H記錄的存放地址。Ki與 Ti 形成索引項(xiàng) (Ki , Ti)，通過(guò) Ki 可找到某個(gè)記錄的存儲(chǔ)地址 Ti 。在討論B樹結(jié)構(gòu)的操作時(shí)先不涉及 Ti ，因此在后續(xù)討論中該指針不出現(xiàn)。B樹

33、的結(jié)點(diǎn)結(jié)構(gòu)進(jìn)一步說(shuō)明nparP0K1P1K2P2K3KnPnKmPm2、查找 假定結(jié)點(diǎn)P已從磁盤讀到內(nèi)存中，可選擇適當(dāng)?shù)膬?nèi)查找方法。當(dāng) j 比較大時(shí)，可選擇對(duì)半查找算法；當(dāng) j 較小時(shí)可采用順序查找方法。設(shè)查找一個(gè)給定的變?cè)猭 ，若k在NODE(P)中，則查找成功。否則必是下述三種情形之一：1) K i k Ki+1(1 i j)，則繼續(xù)到結(jié)點(diǎn)NODE (Pi) 中去查找.2) k Kj ，查找將轉(zhuǎn) NODE (P j) 繼續(xù)查找。3) k K1 ，查找將轉(zhuǎn) NODE (P0) 繼續(xù)查找。如果指向下一個(gè)要查找的結(jié)點(diǎn)的指針Pi = ，則查找以失敗告終，關(guān)鍵詞為 k 的記錄不在樹中。P0K1P1K

34、2P2Pj1KjPjP3、插入（1）若在一個(gè)包含jm1個(gè)關(guān)鍵詞的結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵詞，則插入過(guò)程將局限于該結(jié)點(diǎn)自身（把新關(guān)鍵詞直接插入該結(jié)點(diǎn)中即可）。如在下圖中插入關(guān)鍵詞337，只須改變一個(gè)結(jié)點(diǎn)即可。347337331313307347331313307插入（2）若把一個(gè)新關(guān)鍵詞插入一個(gè)已包含m1個(gè)(m為B樹的階)關(guān)鍵詞的結(jié)點(diǎn)(結(jié)點(diǎn)已滿)，則插入將造成此結(jié)點(diǎn)“分裂”。如插入關(guān)鍵詞071。此時(shí)，把m個(gè)關(guān)鍵詞分成個(gè)數(shù)相等的兩組，第一組從左向右數(shù)，包含m/2個(gè)關(guān)鍵詞，第二組從右向左數(shù)，包含m/2個(gè)關(guān)鍵詞，剩下的中間那個(gè)關(guān)鍵詞將被提升到上一層結(jié)點(diǎn)中，去開始新的插入。“分裂”可能會(huì)向上傳播，在極端情況

35、下，分裂會(huì)一直波及到根結(jié)點(diǎn)，而這恰恰是B樹長(zhǎng)高的唯一方式。031097137191083073067059047041031097137191067041047059071073083例從空樹開始建立3階B樹n=1 加入5353n=2 加入7553 75n=3 加入139751395349 75n=5 加入49,14575139 14549 53n=6 加入36139 1455336在插入時(shí)，需要首先進(jìn)行搜索，然后可能自底向上地分裂結(jié)點(diǎn)最壞情況下從被插關(guān)鍵碼所在葉結(jié)點(diǎn)到根的路徑上的所有結(jié)點(diǎn)都要分裂。設(shè)B 樹高h(yuǎn),則搜索時(shí)最多讀盤h 次。n=7 加入101495336139145101758.7

36、.3 B+ 樹 由于B樹的結(jié)點(diǎn)代表一個(gè)輔存頁(yè)或者是一個(gè)輔存塊，從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)需要費(fèi)時(shí)的頁(yè)切換。所以最好盡可能地少訪問結(jié)點(diǎn)。 如果請(qǐng)求以升序訪問B樹中的結(jié)點(diǎn)，如用中序遍歷，但對(duì)非末端結(jié)點(diǎn)，一次只能顯示一個(gè)關(guān)鍵詞，然后就要訪問其他的頁(yè)。因此，希望增強(qiáng)B樹，能以比中序遍歷快的方式順序訪問數(shù)據(jù)。B+樹提供了一個(gè)解決方案。 B+ 樹是適應(yīng)文件系統(tǒng)的需要而產(chǎn)生的一種B樹的變形樹，一棵m階B+ 樹須滿足下列條件：1) 每個(gè)分支結(jié)點(diǎn)至多有m棵子樹；2) 除根結(jié)點(diǎn)外，其它每個(gè)分支結(jié)點(diǎn)至少有m/2棵子樹；3) 根結(jié)點(diǎn)至少有兩棵子樹，至多有m棵子樹；4) 有n棵子樹的結(jié)點(diǎn)有n個(gè)關(guān)鍵詞；5) 所有的葉子結(jié)點(diǎn)包

37、含全部關(guān)鍵詞及指向相應(yīng)記錄的指針，而且葉子結(jié)點(diǎn)按關(guān)鍵詞自小而大的順序鏈接；6) 所有分支結(jié)點(diǎn)（可看成是索引的索引）中僅包含它的各個(gè)子結(jié)點(diǎn)（下級(jí)索引的索引塊）中最大關(guān)鍵詞及指向子結(jié)點(diǎn)的指針。 一棵4階B+ 樹m = 410 15 18 22 27 34 40 44 47 54 67 72 74 78 81 84 15 34 47 67 78 84 67 84 一棵m階B+ 樹和一棵m階B樹的差異在于 : B樹中，有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵詞；B樹中，每個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)和葉結(jié)點(diǎn)除外）中的關(guān)鍵詞個(gè)數(shù)n的取值范圍是m/2nm，根結(jié)點(diǎn)關(guān)鍵詞個(gè)數(shù)n的取值范圍是2nm；而B樹中，它們的取值范圍分別是m/2

38、1nm1和1nm1；B樹中，所有的葉結(jié)點(diǎn)中包含了全部關(guān)鍵詞，即其它非葉結(jié)點(diǎn)中的關(guān)鍵詞都包含在葉結(jié)點(diǎn)中；而在B樹中，葉子結(jié)點(diǎn)包含的關(guān)鍵詞與其它結(jié)點(diǎn)包含的關(guān)鍵詞是不重復(fù)的；一棵m階B+ 樹和一棵m階B樹的差異在于 :B樹中，非葉結(jié)點(diǎn)僅起索引作用，即結(jié)點(diǎn)中每個(gè)索引項(xiàng)只含有對(duì)應(yīng)子樹的最大關(guān)鍵詞和指向該子樹的指針，不含有該關(guān)鍵詞對(duì)應(yīng)記錄的存儲(chǔ)地址。而B樹中，每個(gè)關(guān)鍵詞對(duì)應(yīng)一個(gè)記錄的存儲(chǔ)地址；通常在B樹上有兩個(gè)頭指針，一個(gè)指向根結(jié)點(diǎn)，另一個(gè)指向最小關(guān)鍵詞的葉子結(jié)點(diǎn)，所有葉子結(jié)點(diǎn)鏈接成一個(gè)不定長(zhǎng)的線性鏈表。 B+ 樹進(jìn)行兩種查找運(yùn)算：一種是從最小關(guān)鍵詞開始進(jìn)行順序查找，另一種是從根結(jié)點(diǎn)開始進(jìn)行隨機(jī)查找。 在

39、B+樹上進(jìn)行隨機(jī)查找、插入和刪除操作的過(guò)程基本上與B樹類似。只是在查找時(shí)，如果非葉結(jié)點(diǎn)上的關(guān)鍵詞等于給定值，并不終止，而是繼續(xù)向下直到葉結(jié)點(diǎn)。因此，在B+樹中，不管查找成功與否，每次查找都是走了一條從根到葉結(jié)點(diǎn)的路徑。一、線性表的查找二、樹形結(jié)構(gòu)的查找三、散列(雜湊)8.9.1 散列表(雜湊表)的定義8.9.2 散列函數(shù)的構(gòu)造8.9.3 沖突調(diào)解雜湊表(散列表)：根據(jù)給定的雜湊函數(shù)Hash (Key)和處理沖突的方法，將一組關(guān)鍵詞映射到一個(gè)有限的連續(xù)的地址區(qū)間上，并以關(guān)鍵詞在地址集上的“映像”作為該記錄在表中的存儲(chǔ)位置，這種表稱為雜湊表或者散列表。這種映射過(guò)程稱為雜湊，所得到的存儲(chǔ)位置稱為雜湊

40、地址或者散列地址。 雜湊技術(shù)避免了關(guān)鍵詞的比較沖突：對(duì)于不同的關(guān)鍵字得到同一雜湊地址的 現(xiàn)象叫沖突。同義詞：雜湊地址相同的不同關(guān)鍵字為同義詞。 雜湊技術(shù)的關(guān)鍵：如何構(gòu)造均勻的雜湊函數(shù)解決沖突的方法一、線性表的查找二、樹形結(jié)構(gòu)的查找三、散列(雜湊)8.9.1 散列表(雜湊表)的定義8.9.2 散列函數(shù)的構(gòu)造8.9.3 沖突調(diào)解2、 雜湊函數(shù)雜湊函數(shù)h與組成關(guān)鍵詞K的符號(hào)有關(guān). 如果K是從關(guān)鍵詞集合中隨機(jī)選取的一個(gè)，則我們希望h(K)以同等概率取區(qū)間0，M-1中的每一個(gè)值. 如果一個(gè)雜湊函數(shù)滿足這一性質(zhì)，則被稱為是均勻的. 構(gòu)造雜湊函數(shù)方法 1. 抽取法 2. 壓縮法 3.除法雜湊函數(shù) 4. 乘法

41、雜湊函數(shù) 3.除法雜湊函數(shù) h(K)=K mod M ，其中K為記錄的關(guān)鍵詞。 例：h(THE)= 10100 01000 00101 mod 31 =2074110 mod 31= 2 注意合理選擇M值，M取小于或等于雜湊表容量的最大質(zhì)數(shù)。 。 一、線性表的查找二、樹形結(jié)構(gòu)的查找三、散列(雜湊)8.9.1 散列表(雜湊表)的定義8.9.2 散列函數(shù)的構(gòu)造8.9.3 沖突調(diào)解3、沖突調(diào)節(jié)沖突調(diào)節(jié)方法 1.拉鏈法 2. 線性探查 1 拉鏈法(開散列表） 拉鏈法 假定表T包含M個(gè)散列地址T0，Tl，TM-l，拉鏈就是令散列地址等于i的記錄組成一個(gè)鏈表，且指針Ti是該單鏈表的頭指針.例關(guān)鍵字序列為1

42、9,14,23,01,68,20,84,27,55,11,10,79 雜湊表長(zhǎng)度為13，雜湊函數(shù)為n(K)=K mod 13。例關(guān)鍵字序列為19,14,23,01,68,20,84,27,55,11,10,79024315671479127810911126855198423102011查找成功的平均查找長(zhǎng)度：ASL=(1*6+2*4+3*1+4*1)/12 = 21/12=1.75例關(guān)鍵字序列為19,14,23,01,68,20,84,27,55,11,10,79024315671479127810911126855198423102011查找失敗的平均查找長(zhǎng)度：ASL=(7*0+1*4+3

43、*2+2*1)/13 = 12/13 為了節(jié)約存儲(chǔ)空間， 改進(jìn)的方法是將每個(gè)Ti分成兩個(gè)域，一個(gè)域存放記錄，另一個(gè)域?yàn)長(zhǎng)INK，存放指針，指向具有相同雜湊地址的下一個(gè)記錄。當(dāng)插入關(guān)鍵詞K時(shí)，如若發(fā)現(xiàn)Th(K)處已包含別的記錄，則沿LINK一直找下去，直到一個(gè)表地址的LINK值為空然后找到一個(gè)空的表地址Tfree，把K存儲(chǔ)在Tfree處，并置最后一個(gè)空LINK域的值為free尋找空地址可由TM-l開始，向T0方向搜索 合并拉鏈法查找與插入算法算法C ( TABLE ，K， M . ) /*對(duì)給定變?cè)狵，本算法檢索M個(gè)結(jié)點(diǎn)的表。若K不在表中且表不滿，則把K插入表中。本算法使用了一個(gè)散列函數(shù)h(K)

44、 . R是一個(gè)輔助變量，用于找到空的空間；R有初始值，R = M +1. */ 例關(guān)鍵字序列為19,14,23,01,68,20,84,27,55,11,10,79C1.散列 置i h (K) +1 （現(xiàn)在1 i M，為檢索K，取K的散列位置i = h (K) +1，去檢索TABLE i ) .C2.有鏈表嗎? 若TABLEi 為空，則轉(zhuǎn)到步驟C6.C3.比較 若K = KEYi，則本算法以成功告終.C4.查下一個(gè)若LINKi ，則置i LINKi 并返回步驟C3.R23 120 168 -101 119 1214 1384 -113119101287653421TABLEM C5.找空結(jié)點(diǎn) (已查完由TABLEh(K)+1開始的鏈表，檢索不成功，故應(yīng)該插入K，所以需要在表中找一個(gè)空位置)令R減1（R初值為M +1），進(jìn)行此操作一次或多次直到TABLER是空為止若R = 0（表明已經(jīng)沒有剩余的空結(jié)點(diǎn)），則本算法以溢出告終；否則，置LINKi R，i R.C6.插入K 標(biāo)記TABLEi為已占用，置KEYi K，LINKi ，算法以插入成