數(shù)據(jù)結構課件：第8章 查找

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

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

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

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

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

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

7、6和58時進行二分查找。查找k=96時二分查找過程(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時二分查找過程(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、對半查找算法描述算法B ( N，R，K . i ) /*給定關鍵詞在遞增次序下（即K1 K2 KN）包含N個記錄R1, R2, , RN 的表，查找給定變元K . 用兩個指針s和e分別指向當前被查找文件之最左邊和最右邊記錄的下標。*/B1. 初始化 置s 1

9、 . e N .B2. 取中點 如果e s，則該算法以失敗告終；否則，置i (s + e) /2。B3. 比較 如果K Ki，則轉步驟B5；如果K = Ki，則算法成功結束。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. 取中點 如果e s，則該算法以失敗告終；否則， 置i (s + e) /2。B3. 比較 如果K Ki， 則轉步驟B5；如果K = Ki，則算法成功結束。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. 取中點 如果e s，則該算法以失敗告終；否則， 置i (s + e) /2。B3. 比較 如果K Ki， 則轉步驟B5；如果K = Ki，則算法成功結束。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)當e-s+10時，T（s，e）為空樹； (2)當e-s+10時，二叉判定樹的根結點是有序表中序

12、號為(e+s)/2的記錄，根結點的左子樹是與有序表Rs，Rs+1，R(e+s)/2 -1相對應的二叉判定樹，根結點的右子樹是與有序表R(e+s)/2+1，R(e+s)/2+2，Re相對應的二叉判定樹。 3、對半查找算法分析 對半查找 判定樹每個圓圈結點表示關鍵詞比較 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)查找成功的平均查找長度4528136971054758296231226603768ASLSUCC (1*1+2*2+3*4+4*3)/10 29/10 2.9查找失敗的平均查找長度： ASLUNSUCC En/(n+1) (3*5+4*6)/11 39/114528136971054758296231226603768 I表示增長樹的內(nèi)路徑長度 E表示增長樹的外路徑長度 n是二叉樹中結點數(shù)，則有: E=I+2n 例 I=19,E=39,n=1045281369710547582962312266037684、二分查找總結: 優(yōu)點

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

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

16、1個記錄間隔(或者稱外結點，即KiKKi+1的情形)。35612OEAUI42、二叉查找樹的插入(動態(tài)樹) 35612OEAUI436712OEAUI5H446712OEAUI3K5二叉查找樹的插入算法算法T ( root, K . p) /* 給定一棵以二叉查找樹形式存儲的記錄表，本算法查找一給定變元K . 如果K不在表中，則在樹的適當位置插入包含K的一個新結點。空子樹以空指針表示，變量root指向此樹的根。*/T1. 初始化 置p root . / 指針p將沿樹下移T2. 比 較 如果K key(p)，則轉到T4；如果K key (p)，則查找成功結束.T3. 左 移 如果llink (p

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

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

19、應該用以結點r為根的子樹形去取代q . 即 LLINK(r)LLINK(q) . qLLINK(q)RLINK(q)sRLINK(s)rsr RLINK(q)且LLINK（RLINK(q)） 在這種情況下，應不斷地取LLINK(RLINK(q)的LLINK域值，即取(LLINK(RLINK(q)，直到找到為止. 然后用LLINK字段為的那個RLINK(q)的左后代s來取代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有左兒子，以該左兒子為根的子樹的最左下結點s取代q，同時將s的父結點指向原s的右子樹。 (例如刪除25)二叉查找樹的刪除（情況三）372375124860826896算法D ( q，a. )/*刪除二叉查找樹中的結點q,指針a指向結點q的父親。*/D1. rlink (q) t q . 若rlink (t) ，則t llink (t) ，并轉到步驟D4 . / t指向取代q位置的結點D2. llink(rlink(q) r rlink (t) . 若llink (r) ，則llink (r) llink

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

37、含全部關鍵詞及指向相應記錄的指針，而且葉子結點按關鍵詞自小而大的順序鏈接；6) 所有分支結點（可看成是索引的索引）中僅包含它的各個子結點（下級索引的索引塊）中最大關鍵詞及指向子結點的指針。 一棵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棵子樹的結點中含有n個關鍵詞；B樹中，每個結點（根結點和葉結點除外）中的關鍵詞個數(shù)n的取值范圍是m/2nm，根結點關鍵詞個數(shù)n的取值范圍是2nm；而B樹中，它們的取值范圍分別是m/2

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

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

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

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

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

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

44、 . R是一個輔助變量，用于找到空的空間；R有初始值，R = M +1. */ 例關鍵字序列為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 為空，則轉到步驟C6.C3.比較 若K = KEYi，則本算法以成功告終.C4.查下一個若LINKi ，則置i LINKi 并返回步驟C3.R23 120 168 -101 119 1214 1384 -113119101287653421TABLEM C5.找空結點 (已查完由TABLEh(K)+1開始的鏈表，檢索不成功，故應該插入K，所以需要在表中找一個空位置)令R減1（R初值為M +1），進行此操作一次或多次直到TABLER是空為止若R = 0（表明已經(jīng)沒有剩余的空結點），則本算法以溢出告終；否則，置LINKi R，i R.C6.插入K 標記TABLEi為已占用，置KEYi K，LINKi ，算法以插入成