【正文】 況下 ， 設(shè)在插入結(jié)點(diǎn)的過(guò)程中使二叉檢索樹(shù)失去平衡的最小子樹(shù)的根結(jié)點(diǎn)為 a， 即 a為離插入結(jié)點(diǎn)最近且平衡因子絕對(duì)值超過(guò) 1的祖先結(jié)點(diǎn)； ?因插入結(jié)點(diǎn)的位置不同而失去平衡需要調(diào)整的規(guī)律可歸納為如下四種情況： ?LL型平衡旋轉(zhuǎn) （ 右單旋型 ） ?RR型平衡旋轉(zhuǎn) （ 左單旋型 ） ?LR型平衡旋轉(zhuǎn) （ 先左后右雙旋型 ） ?RL型平衡旋轉(zhuǎn) （ 先右后左雙旋型 ） （右單旋型） ?這種失衡是由于在結(jié)點(diǎn) a的左孩子 b的左子樹(shù)上插入結(jié)點(diǎn) ，使結(jié)點(diǎn) a的平衡因子由 1增至 2而造成的 。 ?其 調(diào)整策略 是以 a的左孩子 b為軸心順時(shí)針旋轉(zhuǎn) （ 即向右旋轉(zhuǎn) ） 一次；使結(jié)點(diǎn) a成為其左孩子 b的右孩子 ， 而 b的右子樹(shù)成為 a的左子樹(shù) ， 如下圖所示 。 這種調(diào)整策略既使結(jié)點(diǎn)的平衡因子滿足 AVL樹(shù)的要求 ， 又保持了二叉檢索樹(shù)的特性 （ 即中序遍歷次序?yàn)樯仙蛄?） 。 （左單旋型） ?這種失衡是由于在結(jié)點(diǎn) a的右孩子 b的左子樹(shù)上插入結(jié)點(diǎn) ，使 a的平衡因子由 1變成 2而造成的； ?其 調(diào)整策略 是以 a的右孩子 b 為軸心逆時(shí)針旋轉(zhuǎn) （ 即向左旋轉(zhuǎn) ） 一次；使 a成為 b的左孩子 ， 而 b的左子樹(shù)成為 a的右子樹(shù) ，如下圖所示 。 3. LR型平衡旋轉(zhuǎn)（先左后右雙旋型） ?這種失衡是由于在結(jié)點(diǎn) a的左孩子 b的右子樹(shù)上插入結(jié)點(diǎn) ， 使a的平衡因子由 1增至 2造成的 。 ?設(shè) c是 b的右孩子 ， 插入結(jié)點(diǎn)的位置有三種可能性： ?c就是插入結(jié)點(diǎn) ， 這是由于插入前 b為葉子結(jié)點(diǎn)且 a無(wú)右孩子而產(chǎn)生的一種可能； ?插入結(jié)點(diǎn)在 c的左子樹(shù)上； ?插入結(jié)點(diǎn)在 c的右子樹(shù)上 。 LR型平衡旋轉(zhuǎn)（續(xù)） ?對(duì)這三種導(dǎo)致 LR型失衡的情況 ， 其 調(diào)整策略 是一致的： ?即以 a的左孩子 b的右孩子 c為軸心 ， 先逆時(shí)針 （ 即向左 ）旋轉(zhuǎn)一次 ， 再順時(shí)針 （ 即向右 ） 旋轉(zhuǎn)一次；使 c的左子樹(shù)成為 b的右子樹(shù) ， c的右子樹(shù)成 a的左子樹(shù) ， b成為 c的左孩子而 a成為 c的右孩子 ， 以 “ 插入在 c的左子樹(shù)上 ” 為例 ， 兩次旋轉(zhuǎn)的調(diào)整過(guò)程如下圖所示 。 4. RL型平衡旋轉(zhuǎn)（先右后左雙旋型） ?這種失衡是由于在結(jié)點(diǎn) a的右孩子 b的左子樹(shù)上插入結(jié)點(diǎn) ， 使 a的平衡因子由 1變成 2造成的 ， 設(shè) c是 b的左孩子 ， 插入結(jié)點(diǎn)位置的三種可能性如下圖所示 ： RL型平衡旋轉(zhuǎn)（續(xù)） ?對(duì)這三種導(dǎo)致 RL型失衡的情況 ， 其 調(diào)整策略 為： ?以 a的右孩子 b的左孩子 c為軸心 ， 先順時(shí)針 （ 即向右 ） 旋轉(zhuǎn)一次 ， 再逆時(shí)針 （ 即向左 ） 旋轉(zhuǎn)一次；使 c的左子樹(shù)成為 a的右子樹(shù) ， c的右子樹(shù)成為 b的左子樹(shù) ， a成為 c的左孩子而 b成為 c的右孩子 。 以 “ 插入在 c的左子樹(shù)上 ” 為例 ，兩次旋轉(zhuǎn)的調(diào)整過(guò)程如下圖所示： 構(gòu)造平衡二叉檢索樹(shù)舉例 ?例如 ， 對(duì)于一組記錄其關(guān)鍵字序列為 （ 18， 5， 10， 15， 12，11， 20） ， 要建立一棵平衡的二叉檢索樹(shù) ， 其構(gòu)造過(guò)程如下圖所示： 構(gòu)造型平二叉檢索樹(shù)的算法 ? 在設(shè)計(jì)構(gòu)造平衡的二叉檢索樹(shù)的算法時(shí) ， 需要先為每個(gè)結(jié)點(diǎn)增加一個(gè)平衡因子域 ， 然后在二叉檢索樹(shù)構(gòu)造算法的基礎(chǔ)上做幾點(diǎn)修改： ? 插入一個(gè)結(jié)點(diǎn)后 ， 要修改樹(shù)中各結(jié)點(diǎn)平衡因子的值； ? 判別是否因插入結(jié)點(diǎn)產(chǎn)生失衡 ， 在失衡時(shí)找到失衡的最小子樹(shù)； ? 判別失衡類型并做相應(yīng)的調(diào)整處理 。 ?在平衡的二叉檢索樹(shù)上進(jìn)行檢索的過(guò)程 ， 和在二叉檢索樹(shù)上的檢索過(guò)程一致 ， 在檢索過(guò)程中和給定值比較的次數(shù)不會(huì)超過(guò)樹(shù)的深度 ， 而含有 n個(gè)結(jié)點(diǎn)的平衡二叉檢索樹(shù)的最大深度為 ， 其中 。 樹(shù)表的檢索 二叉檢索樹(shù) 二叉檢索樹(shù)的平衡性調(diào)整 B樹(shù)和 B+樹(shù) B樹(shù) ? B樹(shù) 是一種平衡的多路檢索樹(shù) ， 是文件系統(tǒng) （ 包括大型數(shù)據(jù)庫(kù)文件系統(tǒng) ） 中的一種重要的數(shù)據(jù)組織結(jié)構(gòu) 。 ? 一棵 m階 B樹(shù) ， 或者為空樹(shù) ， 或者為滿足下列特性的 m叉樹(shù)： ⑴ 樹(shù)中每個(gè)結(jié)點(diǎn)至多有 m棵子樹(shù) （ 即至多有 m1個(gè)關(guān)鍵字 ） ； ⑵ 除非根結(jié)點(diǎn)為葉子結(jié)點(diǎn) ， 否則至少有兩棵子樹(shù) （ 即至少有一個(gè)關(guān)鍵字 ） ； ⑶ 除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有棵子樹(shù)； B樹(shù)（續(xù)） ⑷ 所有的非終端結(jié)點(diǎn)中包含以下信息： （ n， A0， k1， A1， k2， … ， kn， An ） ?其中： ① n（ n≤m1） 為關(guān)鍵字的個(gè)數(shù) ， 即子樹(shù)個(gè)數(shù)為 n+1； ② ki（ 1≤i≤n） 為關(guān)鍵字 ， 且 kiki+1（ 1≤in） ； ? ③ Ai（ 0≤i≤n） 為指向其子樹(shù)的根結(jié)點(diǎn)的指針 ， 且 Ai（ 0≤in） 所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字值都小于 ki+1， An所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字值都大于 kn； ⑸ 所有葉子結(jié)點(diǎn)在同一個(gè)層次上 ， 且不含有任何信息 （ 可以看作是外部結(jié)點(diǎn)或檢索失敗的結(jié)點(diǎn)；實(shí)際上這些結(jié)點(diǎn)不存在 ， 指向這些結(jié)點(diǎn)的指針為NULL） 。 B樹(shù)示全例 ?下圖給出了一棵 4階 B樹(shù)的示例： B樹(shù)的插入操作 ?在 B樹(shù)上插入一個(gè)關(guān)鍵字 ， 不是象在二叉檢索樹(shù)中那樣添加一個(gè)葉子結(jié)點(diǎn) ， 而是在 B樹(shù)的最底層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字 。 ?若該結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)小于 m1個(gè)則插入完成；否則添加后關(guān)鍵字個(gè)數(shù)由 m1個(gè)變?yōu)?m個(gè)與 B樹(shù)定義不符 ， 需要進(jìn)行結(jié)點(diǎn)的 “ 分裂 ” 以滿足 B樹(shù)定義 。 ?結(jié)點(diǎn)的分裂方法為 ， 把中間一個(gè)關(guān)鍵字拿出來(lái)插入到該結(jié)點(diǎn)的雙親結(jié)點(diǎn)上 ， 前后兩部分各自形成一個(gè)結(jié)點(diǎn)；雙親結(jié)點(diǎn)中也可能有 m個(gè)關(guān)鍵字 ， 就需要繼續(xù)分裂結(jié)點(diǎn) ， 直到插入到某個(gè)關(guān)鍵字個(gè)數(shù)小于 m1的祖先結(jié)點(diǎn) 。 ?由這種分裂過(guò)程可見(jiàn) ， B樹(shù)是由底向上生長(zhǎng)的 。 B樹(shù)的插入操作舉例 ?B樹(shù)的插入過(guò)程如下圖所示 ， 圖中只畫出了非終端結(jié)點(diǎn) ， 省去了最底層的葉子結(jié)點(diǎn) 。 B樹(shù)的刪除操作 ? 在 B樹(shù)上刪除一個(gè)關(guān)鍵字和插入關(guān)鍵字類似也是由底向上的調(diào)整過(guò)程 ， ?先找到該關(guān)鍵字所在的結(jié)點(diǎn)并刪除這個(gè)關(guān)鍵字 。 ?若找到的結(jié)點(diǎn)是最底層的非終端結(jié)點(diǎn) ， 當(dāng)關(guān)鍵字個(gè)數(shù)大于則刪除完成 ， 否則刪除后關(guān)鍵字個(gè)數(shù)由個(gè)變?yōu)閭€(gè)與 B樹(shù)定義不符 ， 需要進(jìn)行結(jié)點(diǎn)的 “ 合并 ” 以滿足 B樹(shù)定義 。 ?合并的方法是把刪除了關(guān)鍵字的結(jié)點(diǎn)同其左兄弟結(jié)點(diǎn)（ 或右兄弟結(jié)點(diǎn) ） 合并 ， 連同它們的雙親結(jié)點(diǎn)中的相關(guān)關(guān)鍵字項(xiàng)一塊合并重新分配 ， 在其雙親結(jié)點(diǎn)不滿足 B樹(shù)定義時(shí)繼續(xù)向上調(diào)整直到根結(jié)點(diǎn) 。 ?若找到的待刪除關(guān)鍵字所在結(jié)點(diǎn)不是底層非終端結(jié)點(diǎn) ，則是將該關(guān)鍵字用其 B樹(shù)中的后繼替代 ， 而刪除其后繼的信息 。 B樹(shù)的刪除操作舉例 ?B樹(shù)的刪除過(guò)程如下圖所示： B樹(shù)的檢索操作 ?在 B樹(shù)中進(jìn)行檢索的過(guò)程是： ?首先在根結(jié)點(diǎn)中所包含的關(guān)鍵字中檢索給定的關(guān)鍵字 ，若找到則檢索成功 ， 否則確定待檢索關(guān)鍵字所在的子樹(shù) ，并在該子樹(shù)中繼續(xù)檢索 ， 直到檢索成功或指針為空時(shí)檢索失敗 。 ?例如 ， 在前例中的一棵 4階 B樹(shù)中檢索關(guān)鍵字值為 61的記錄 ，因根結(jié)點(diǎn)中不存在此關(guān)鍵字 ， 則到大于 39的子樹(shù)中檢索；又因?yàn)樽訕?shù)的根結(jié)點(diǎn)中沒(méi)有此關(guān)鍵字 ， 而 506180， 故再到 s所指子樹(shù)中檢索 ， 在這個(gè)結(jié)點(diǎn)中含有 61的關(guān)鍵字值則檢索成功 。 ?又如在此 4階 B樹(shù)中檢索關(guān)鍵字值為 75的記錄 ， 也是沿前面的這一條路線檢索 ， 由于 s所指結(jié)點(diǎn)中沒(méi)有值為 75的關(guān)鍵字而檢索失敗 。 B樹(shù)的檢索操作（續(xù)） ? B樹(shù)的檢索是在 B 樹(shù)上找結(jié)點(diǎn)和在結(jié)點(diǎn)中找關(guān)鍵字兩個(gè)基本操作的交叉進(jìn)行過(guò)程 ， 待查關(guān)鍵字所在結(jié)點(diǎn)在 B樹(shù)中的層次是決定 B樹(shù)檢索效率的首要因素 ，最壞的情況下是含 n個(gè)關(guān)鍵字的 m階 B樹(shù)的最大深度 。 ?由 B樹(shù)定義 ， 第一層至少有 1個(gè)結(jié)點(diǎn) ， 第二層至少有2個(gè)結(jié)點(diǎn)；由于除根結(jié)點(diǎn)外的每個(gè)非終端結(jié)點(diǎn)至少有 棵子樹(shù) ， 則第三層至少有 2（ ） 個(gè)結(jié)點(diǎn)； …… ；依此類推 ， 第 h+1層至少有 個(gè)結(jié)點(diǎn)；而 h+1層為葉子結(jié)點(diǎn) 。 若 m階 B樹(shù)有 n個(gè)關(guān)鍵字 ，則葉子結(jié)點(diǎn)即查找不成功的結(jié)點(diǎn)數(shù)為 n+1， 由此有 B+樹(shù) ?B+樹(shù)是應(yīng)用于文件系統(tǒng)中的 B樹(shù)的一種變形樹(shù) ， 它與 B樹(shù)的差異主要在于： ⑴ 有 n棵子樹(shù)的結(jié)點(diǎn)中含有 n個(gè)關(guān)鍵字； ⑵ 所有葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息及指向相應(yīng)記錄的指針 ， 且葉子結(jié)點(diǎn)以關(guān)鍵字遞增順序鏈接； ⑶ 所有的非終端結(jié)點(diǎn)可以看成是索引部分 ，結(jié)點(diǎn)中僅含有其子樹(shù)中的最大 （ 或最小 ） 關(guān)鍵字 。 B+樹(shù)舉例 ?如下圖給出了一棵 3階 B+樹(shù) 。 ?通常 B+樹(shù)上有兩個(gè)指針 ， 一個(gè)指向根結(jié)點(diǎn) ， 一個(gè)指向關(guān)鍵字值最小的葉子結(jié)點(diǎn) 。 ?因此 ， 對(duì)于 B+樹(shù)既可從根結(jié)點(diǎn)開(kāi)始多級(jí)索引順序檢索 ， 又可以從最小關(guān)鍵字開(kāi)始順序檢索 。 B+樹(shù)的操作 ?在 B+樹(shù)上進(jìn)行插入 、 刪除和檢索的過(guò)程與 B樹(shù)基本相似 。 ?在檢索過(guò)程中在非終端結(jié)點(diǎn)上找到給定值后并不終止 ，而是繼續(xù)向下直到葉子結(jié)點(diǎn)；因而無(wú)論是檢索成功還是檢索失敗 ， 每次檢索都是走了一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑 。 ?B+樹(shù)的插入僅在葉子結(jié)點(diǎn)上進(jìn)行 ， 當(dāng)葉子結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)大于 m時(shí)也要分裂成兩個(gè)結(jié)點(diǎn) ， 并且其雙親結(jié)點(diǎn)中同時(shí)也包含這兩個(gè)結(jié)點(diǎn)的關(guān)鍵字最大值 。 ?B+樹(shù)的刪除也在葉子結(jié)點(diǎn)中進(jìn)行 ， 其在非終端結(jié)點(diǎn)中的值可以作為分界關(guān)鍵字存在；當(dāng)然在刪除后若使結(jié)點(diǎn)中關(guān)鍵個(gè)數(shù)小于 時(shí)也要進(jìn)行結(jié)點(diǎn)的合并操作 。 第 7章 檢索及基本算法 檢索的概念 線性表的檢索 樹(shù)表的檢索 哈希檢索 哈希檢索 ?在前兩節(jié)介紹的線性表檢索和樹(shù)表檢索方法后 ， 由于記錄在檢索表中的位置是隨機(jī)的或按關(guān)鍵字值大小次序排列的 ， 記錄的存儲(chǔ)位置和其關(guān)鍵字值之間不存在某種確定的關(guān)系 ， 存儲(chǔ)位置依賴于關(guān)鍵字的初始隨機(jī)序列或在檢索表中其它關(guān)鍵字值的大小 。 ?所以在檢索時(shí)需要進(jìn)行一系列的關(guān)鍵字值與給定值之間的比較 ， 其檢索效率和檢索過(guò)程中進(jìn)行的比較次數(shù)有關(guān) 。 ?本節(jié)介紹一種直接利用關(guān)鍵字值計(jì)算記錄在檢索表中的存儲(chǔ)位置來(lái)進(jìn)行檢索的方法 —— 哈希 （ Hash）檢索技術(shù) 。 哈希檢索 哈希檢索與哈希表 哈希函數(shù)的構(gòu)造方法 地址沖突的消解策略 哈希表的檢索算法及性能分析 哈希檢索與哈希表 ?哈希檢索技術(shù)的初衷是組織理想狀態(tài)的檢索表 。 ?檢索表的理想狀態(tài)是：把記錄的關(guān)鍵字值與記錄在檢索表中的存儲(chǔ)位置建立起某種一對(duì)一的關(guān)系 ， 這種一對(duì)一的關(guān)系可以用關(guān)于關(guān)鍵字的一個(gè) 函數(shù) h(key)來(lái)表示 ， 這樣就可以不必進(jìn)行關(guān)鍵字與給定值的比較 ， 而是直接依據(jù)給定的關(guān)鍵字值來(lái)直接計(jì)算得到記錄在檢索表中的存儲(chǔ)地址 。 哈希檢索與哈希表舉例 ?例如 ， 對(duì)于一組關(guān)鍵字序列 （ 25， 74， 36， 15， 40， 29， 82，19， 65， 33， 57， 47， 50） ， 選取函數(shù) h(key)＝ key%13建立記錄與其在檢索表中存儲(chǔ)位置之間的關(guān)系 ， 可得到如下表所示的一張檢索表： ?當(dāng)對(duì)該表檢索時(shí) ， 只需用給定關(guān)鍵字值 k通過(guò)這個(gè)函數(shù)計(jì)算出地址 ， 以該地址從檢索表的對(duì)應(yīng)位置取出記錄的有關(guān)信息即可 ， 不需要進(jìn)行關(guān)鍵字值的比較操作 。 ?如檢索 key=57的記錄 ， 通過(guò) h(57)=57%13=5知關(guān)鍵字值為 57的記錄在檢索表的存儲(chǔ)位置 5處 ， 從而得到關(guān)鍵字值為 57的記錄的有關(guān)信息 。 哈希檢索與哈希表（續(xù)） ? 我們把這種反映關(guān)鍵字值與存儲(chǔ)位置的一對(duì)一關(guān)系的函數(shù) h(key)稱作 哈希函數(shù) ， 也稱作 散列函數(shù) 或 雜湊函數(shù) ； ?利用哈希函數(shù)來(lái)實(shí)現(xiàn)從記錄的關(guān)鍵字值到該記錄在檢索表中存儲(chǔ)位置地址的計(jì)算 ， 哈希函數(shù) h(key)的值稱作 哈希地址 ， 也稱作 散列地址 或 雜湊地址 ； ?把利用哈希函數(shù) h(key)組織檢索表并利用 h(key)進(jìn)行檢索的這種方法稱作 哈希方法 ， 也稱作 散列法 或 雜湊法 ； ?把用這種思想方法 （ 即哈希方法 ） 組織起來(lái)的檢索表稱作 哈希表 ， 也稱作 散列表 或 雜湊表 。 哈希檢索與哈希表（續(xù)） ?對(duì)于 n個(gè)記錄的關(guān)鍵字集合 ， 我們總能找到其關(guān)鍵字值與存儲(chǔ)地址之間的一對(duì)一函數(shù) 。 ?若最大關(guān)鍵字值為 m， 可以分配 m個(gè)記錄空間組織哈希表 ， 選取哈希函數(shù) h(key)＝ key即可 。 然而 ， 這樣會(huì)造成存儲(chǔ)空間的大量浪費(fèi) ， 甚至不可能分配有這么大的存儲(chǔ)空間 。 ?在實(shí)際應(yīng)用中 ， 通常關(guān)鍵字的