11-數(shù)據(jù)結(jié)構(gòu)與算法-北京大學(xué)2008-張銘-索引技術(shù)

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

第11章索引技術(shù)

本章由張銘主寫http:///mzhang/DS/http:///pkujpk/course/sjjg

張銘，王騰蛟，趙海燕高等教育出版社，2008.

6?！笆晃濉眹壹壱?guī)劃教材主要內(nèi)容基本概念11.1線性索引11.2靜態(tài)索引11.3倒排索引11.4動態(tài)索引11.4.4動態(tài)、靜態(tài)索引性能的比較11.5位索引技術(shù)11.6紅黑樹基本概念輸入順序文件主碼與輔碼索引與索引文件稠密索引與稀疏索引輸入順序文件輸入順序文件(entry-sequencedfile)按照記錄進入系統(tǒng)的順序存儲記錄一般說來，輸入順序文件的結(jié)構(gòu)相當(dāng)于一個磁盤中未排序的線性表因此不支持高效率的檢索主碼主碼(primarykey)是數(shù)據(jù)庫中的每條記錄的唯一標識例如，公司職員信息的記錄的主碼可以是職員的身份證號碼

如果只有主碼，不便于各種靈活檢索輔碼輔碼(secondarykey)是數(shù)據(jù)庫中可以出現(xiàn)重復(fù)值的碼輔碼索引把一個輔碼值與具有這個輔碼值的每一條記錄的主碼值關(guān)聯(lián)起來大多數(shù)檢索都是利用輔碼索引來完成的索引索引(indexing)是把一個關(guān)鍵碼與它對應(yīng)的數(shù)據(jù)記錄的位置相關(guān)聯(lián)的過程(關(guān)鍵碼，指針)對，即(key,pointer)指針指向主要數(shù)據(jù)庫文件（也稱為“主文件”）中的完整記錄索引文件(indexfile)是用于記錄這種聯(lián)系的文件組織結(jié)構(gòu)索引技術(shù)是組織大型數(shù)據(jù)庫的一種重要技術(shù)高效率的檢索插入、更新、刪除索引文件一個主文件可能有多個相關(guān)索引文件每個索引文件往往支持一個關(guān)鍵碼字段不需要重新排列重排主文件可以通過該索引文件高效訪問記錄中該關(guān)鍵碼值稠密索引vs

稀疏索引稠密索引：對每個記錄建立一個索引項主文件不按照關(guān)鍵碼的順序排列稀疏索引：對一組記錄建立一個索引記錄按照關(guān)鍵碼的順序存放可以把記錄分成多個組（塊）索引指針指向的這一組記錄在磁盤中的起始位置11.1線性索引基本概念線性索引的優(yōu)點線性索引的問題二級線性索引線性索引文件按照關(guān)鍵碼的順序進行排序文件中的指針指向存儲在磁盤上的文件記錄起始位置或者主索引中主碼的起始位置92733755數(shù)據(jù)庫記錄線形索引文件Go線性索引的優(yōu)點對變長的數(shù)據(jù)庫記錄的訪問可以對數(shù)據(jù)進行高效檢索二分檢索

順序處理比較操作批處理的操作節(jié)省空間

(相對其它索引結(jié)構(gòu))線性索引的問題線性索引太大，存儲在磁盤中在一次檢索過程中可能多次訪問磁盤，從而影響檢索的效率使用二級線性索引更新線性索引在數(shù)據(jù)庫中插入或者刪除記錄時二級線性索引例如，磁盤塊的大小是1024字節(jié)，每對

(關(guān)鍵碼，指針)索引對需要8個字節(jié)1024/8=128每磁盤塊可以存儲128條這樣的索引對假設(shè)數(shù)據(jù)文件包含10000條記錄稠密一級線性索引中包含10000條記錄10000/128=78.1那么一級線性索引占用79個磁盤塊相應(yīng)地，二級線性索引文件中有79項索引對這個二級線性索引文件可以在一個磁盤塊二級線性索引的例子關(guān)鍵碼與相應(yīng)磁盤塊中第一條記錄的關(guān)鍵碼的值相同指針指向相應(yīng)磁盤塊的起始位置

一級索引二級索引例如：檢索關(guān)鍵碼為2555的記錄1.二級線性索引文件讀入內(nèi)存2.二分法找關(guān)鍵碼的值小于等于2555的最大關(guān)鍵碼所在一級索引磁盤塊地址——關(guān)鍵碼為2003的記錄3.根據(jù)記錄2003中的地址指針找到其對應(yīng)的一級線性索引文件的磁盤塊，并把該塊讀入內(nèi)存4.按照二分法對該塊進行檢索，找到所需要的記錄在磁盤上的位置5.最后把所需記錄讀入，完成檢索操作11.2靜態(tài)索引基本概念多分樹ISAM基本概念靜態(tài)索引索引結(jié)構(gòu)在文件創(chuàng)建、初始裝入記錄時生成一旦生成就固定下來，在系統(tǒng)運行(例如插入和刪除記錄)過程中索引結(jié)構(gòu)并不改變只有當(dāng)文件再組織時才允許改變索引結(jié)構(gòu)

多分樹組織索引一般不用二叉樹而采用多分樹大大減少訪問外存的次數(shù)

二叉樹轉(zhuǎn)換成多分樹632次訪問索引塊1次訪問外存數(shù)據(jù)塊ISAMISAM是解決需要頻繁更新的大型數(shù)據(jù)庫的一個早期嘗試在采用基于B+樹的VSAM技術(shù)之前，IBM公司曾經(jīng)廣泛地采用ISAM技術(shù)多分樹的應(yīng)用

為磁盤存取而設(shè)計

結(jié)構(gòu)采用多級索引主索引柱面索引磁道索引

11.3倒排索引基本概念11.3.1基于屬性的倒排11.3.2對正文文件的倒排基本概念基于屬性的檢索要求檢索結(jié)構(gòu)中某個或若干個屬性滿足一定條件的結(jié)點不是按關(guān)鍵碼的值檢索教師數(shù)據(jù)庫主表EMP#NAMEDepartmentProfessionSpecialtyAddress0155李宇數(shù)學(xué)教授代數(shù)C1050421劉陽

外語

助教英語E3100208趙亮

物理

助教力學(xué)C2110211張偉

物理

講師原子物理D5080132王亮

數(shù)學(xué)

助教幾何E2200119王卓

數(shù)學(xué)

講師代數(shù)B1020330孫麗

計算機

教授軟件A1080455劉珍

外語

講師法語A2250310周兵

計算機

講師英語B4230341何江

計算機

助教計算機F406……

11.3.1基于屬性的倒排對某屬性按屬性值建立索引表，稱倒排表(attr,ptrList)（屬性值，具有該屬性值的各記錄指針）記錄指針可以是關(guān)鍵碼，或該記錄的主文件地址顛覆主文件的順序，因而稱為倒排索引屬性往往是離散型的對于連續(xù)型的索引，往往用B樹倒排文件：帶有倒排索引的文件教師數(shù)據(jù)庫倒排表DepartmentlistEMP#數(shù)學(xué)物理計算機外語0155,0132, 01190208,02110330,0310, 03410421,0455ProfessionlistEMP#教授講師助教0155,03300211,0119, 0455,03100421,0208, 0132,0341SpecialtylistEMP#代數(shù)幾何力學(xué)原子物理軟件英語法語0155,01190132020802110330,03410421,03100455優(yōu)缺點優(yōu)點：能夠?qū)τ诨趯傩缘臋z索進行較高效率的處理缺點：花費了保存倒排表的存儲代價降低了更新運算的效率11.3.2對正文文件的倒排正文索引(TextIndexing)處理的就是“建立一個數(shù)據(jù)結(jié)構(gòu)以提供對文本內(nèi)容的快速檢索”。方法詞索引(wordindex)全文索引(full-textindex)詞索引基本思想：把正文看作由符號和詞所組成的集合，從正文中抽取出關(guān)鍵詞，然后用這些關(guān)鍵詞組成一些適合快速檢索的數(shù)據(jù)結(jié)構(gòu)。適用于多種文本類型，特別是那些可以很容易就解析成一組詞的集合的文本適用于英文中文等東方文字要經(jīng)過“切詞”處理全文索引基本思想：把正文看作一個長的字符串在數(shù)據(jù)結(jié)構(gòu)中記錄的是子字符串的開始位置查詢就可以針對正文中的任何子字符串可以對每一個字符建立索引，從而使查詢詞不再限于關(guān)鍵詞需要更大的空間倒排文件使用最廣泛的是詞索引詞索引使用最廣泛一個已經(jīng)排過序的關(guān)鍵詞的列表其中每個關(guān)鍵詞指向一個倒排表（postinglist）指向該關(guān)鍵詞出現(xiàn)文檔集合在文檔中的位置倒排索引建立示例正文文件：由6個文檔組成，每個文檔都是長字符串Peaseporridgehot,pleaseporridgecold,文檔編號文本內(nèi)容1Peaseporridgeinthepot,Ninedaysold.Somelikeithot,somelikeitcold,Somelikeitinthepot,Ninedaysold.23456倒排索引12345678910111213編號詞語（文檔編號，位置）colddayshotinlikenine

oldpeaseporridgeitpotsomethe(1,1)(1,2)(1,3)(1,4)(1,5)(1,6)類似處理1中的其他詞語同理，處理2中的詞語（2,1）依次處理所有文檔建立正文倒排文件1.對文檔集中的所有文件都進行分割處理，把正文分成多條記錄文檔切分正文記錄取決于程序的需要定長的塊、段落、章節(jié)，甚至一組文檔建立正文倒排文件（續(xù)1）2.給每條記錄賦一組關(guān)鍵詞以人工或者自動的方式從記錄中抽取關(guān)鍵詞停用詞(Stopword)抽詞干(Stemming)切詞（segmentation）建立正文倒排文件（續(xù)2）3.建立正文倒排表、倒排文件得到各個關(guān)鍵詞的集合對于每一個關(guān)鍵詞得到其倒排表然后把所有的倒排表存入文件記錄在每個倒排表在索引文件中開始的位置以及每個表的大小（也可以記錄每個關(guān)鍵詞的出現(xiàn)次數(shù)）對關(guān)鍵詞的檢索第一步，在倒排文件中檢索關(guān)鍵詞第二步，如果找到了關(guān)鍵詞，那么獲取文件中的對應(yīng)的倒排表，并獲取倒排表中的記錄通常使用另一個索引結(jié)構(gòu)（字典）進一步對關(guān)鍵詞表進行有效索引Trie散列倒排文件優(yōu)劣高效檢索，用于文本數(shù)據(jù)庫系統(tǒng)支持的檢索類型有限檢索詞有限只能用索引文件中的關(guān)鍵詞倒排文件中的索引效率可能不高需要的空間代價往往很高11.4動態(tài)索引基本概念11.4.1B樹11.4.2B+樹VSAM11.4.3B樹的性能分析11.4.4動態(tài)索引和靜態(tài)索引性能的比較基本概念動態(tài)索引結(jié)構(gòu)索引結(jié)構(gòu)本身也可能發(fā)生改變在系統(tǒng)運行過程中插入或刪除記錄時目的保持較好的性能例如較高的檢索效率11.4.1B樹一種平衡的多分樹

(BalancedTree)

3階B樹2-3樹B樹隱含指針(18,a1)(33,a2)(10,a7)(15,a8)(20,a9)(21,a10)(24,a11)(31,a12)(45,a13)(47,a14)(50,a5)(52,a16)(12,a3)(23,a4)(30,a5)(48,a6)關(guān)鍵碼文件頁內(nèi)地址主文件m階B樹的結(jié)構(gòu)定義(1)每個結(jié)點至多有m個子結(jié)點；(2)除根結(jié)點和葉結(jié)點外，其它每個結(jié)點至少有個子結(jié)點；(3)根結(jié)點至少有兩個子結(jié)點唯一例外的是根結(jié)點就是葉結(jié)點時沒有子結(jié)點此時B樹只包含一個結(jié)點(4)所有的葉結(jié)點在同一層；(5)有k個子結(jié)點的非根結(jié)點恰好包含k-1個關(guān)鍵碼。

B樹的性質(zhì)(1)樹高平衡，所有葉結(jié)點都在同一層；(2)關(guān)鍵碼沒有重復(fù)，父結(jié)點中的關(guān)鍵碼是其子結(jié)點的分界；(4)B樹把（值接近）相關(guān)記錄放在同一個磁盤頁中，從而利用了訪問局部性原理；(5)B樹保證樹中至少有一定比例的結(jié)點是滿的這樣能夠改進空間的利用率減少檢索和更新操作的磁盤讀取數(shù)目B樹的結(jié)點結(jié)構(gòu)B樹的一個包含j個關(guān)鍵碼，j+1個指針的結(jié)點的一般形式為：其中Ki是關(guān)鍵碼值，K1<K2<…<Kj，Pi是指向包括Ki到Ki+1之間的關(guān)鍵碼的子樹的指針。還有指針嗎？2-3樹=3階B樹18331223304810152021243145475052B樹的查找交替的兩步過程1.把根結(jié)點讀出來，在根結(jié)點所包含的關(guān)鍵碼K1，…，Kj中查找給定的關(guān)鍵碼值找到則檢索成功2.否則，確定要查的關(guān)鍵碼值是在某個Ki和Ki+1之間，于是取pi所指向的結(jié)點繼續(xù)查找如果pi指向外部空結(jié)點，表示檢索失敗

B樹檢索長度設(shè)B樹的高度為h獨根樹高為1在自頂向下檢索到葉結(jié)點的過程中可能需要進行h次讀盤

B樹插入注意保持性質(zhì)，特別是等高和階的限制

1)找到最底層，插入

2)若溢出，則結(jié)點分裂，中間關(guān)鍵碼連同新指針插入父結(jié)點

3)若父結(jié)點也溢出，則繼續(xù)分裂分裂過程可能傳達到根結(jié)點(則樹升高一層)B樹的插入外部空結(jié)點（即失敗檢索）處在第I層的B樹，插入的關(guān)鍵碼總是在第I-1層插入143階B樹18331223304810

20212431454750521514m=3，插入5518331223304810152021243145475052插入55505255

m=3，葉結(jié)點分裂，把52提升到父結(jié)點

結(jié)點分裂1833122330481015202124314547505255525055插入引起3階B樹根結(jié)點分裂的例子插入191833122330481015202124314547505219192021

m=3葉結(jié)點分裂18331223304810152431454750521920211921

233020

m=3第二層結(jié)點分裂192118331248101524314547505220

233030

20183323

m=3根結(jié)點分裂3019211248101524314547505220

23

1833訪外次數(shù)上述插入過程有10次對B樹的訪外操作其中讀盤3次（a、c、g）寫盤7次（g、g’、c、c’、a、a’、t）這里不考慮對主數(shù)據(jù)文件的訪外操作，也不考慮申請新磁盤塊的開銷B樹操作的訪外次數(shù)假設(shè)內(nèi)存工作區(qū)足夠大，使得在向下檢索時讀入的結(jié)點在插入后向上分裂時不必再從磁盤讀入讀盤次數(shù)與查找相同最少寫盤次數(shù)：一次不分裂，寫出這個關(guān)鍵碼所插入到的結(jié)點一次插入操作最多讀寫次數(shù)總共h層，每層都需要分裂（包括根）分裂一個非根結(jié)點要向磁盤寫出2個結(jié)點，分裂根結(jié)點（最后一次）要寫出3個結(jié)點

=找插入結(jié)點向下讀盤次數(shù)++分裂非根結(jié)點時寫盤次數(shù)++分裂根結(jié)點時寫盤次數(shù)

=h+2(h-1)+3=3h+1B樹的刪除刪除的關(guān)鍵碼不在葉結(jié)點層先把此關(guān)鍵碼與它在B樹里的后繼對換位置，然后再刪除該關(guān)鍵碼

B樹的刪除(續(xù))刪除的關(guān)鍵碼在葉結(jié)點層刪除后關(guān)鍵碼個數(shù)不小于直接刪除關(guān)鍵碼個數(shù)小于如果兄弟結(jié)點關(guān)鍵碼個數(shù)不等于從兄弟結(jié)點移若干個關(guān)鍵碼到該結(jié)點中來(父結(jié)點中的一個關(guān)鍵碼要做相應(yīng)變化)如果兄弟結(jié)點關(guān)鍵碼個數(shù)等于合并120150

2550

103

5階B樹刪除示例acedfghbi1115

3543

8195100

108110115118134146

156177

刪除120，先與后繼交換，刪后下溢出，向左鄰借關(guān)鍵碼

150

2550

103

acedfghbi1115

3543

8195100

108110115

146

156177

120

134

與后繼交換刪除120,h溢出向左鄰借關(guān)鍵碼118146

146

134

1182550

103

cedfghbi1115

3543

8195100

108110115

134146

177

156150繼續(xù)刪除150與后繼交換刪除150,i溢出向左鄰借關(guān)鍵碼借不到，h,i合并177

134146

a1182550

103

cedfgh’b1115

3543

8195100

108110115

134146156177h,i合并成為h’c溢出，向左鄰借關(guān)鍵碼借不到，b,c結(jié)點合并1182550

a2550103118

a’11.4.2B+樹是B樹的一種變形在葉結(jié)點上存儲信息的樹所有的關(guān)鍵碼均出現(xiàn)在葉結(jié)點上

各層結(jié)點中的關(guān)鍵碼均是下一層相應(yīng)結(jié)點中最大關(guān)鍵碼（或最小關(guān)鍵碼）的復(fù)寫

B+樹的結(jié)構(gòu)定義m階B+樹的結(jié)構(gòu)定義如下：(1)每個結(jié)點至多有m個子結(jié)點；(2)每個結(jié)點(除根外)至少有個子結(jié)點；(3)根結(jié)點至少有兩個子結(jié)點；(4)有k個子結(jié)點的結(jié)點必有k個關(guān)鍵碼。其實，根可以為空，或者獨根2階B+樹的例子

70

95

10

20

35

40

44

51

65

70

85

91

93

95

20

40

51

70

91

95

40

70

95

B+樹的查找查找應(yīng)該到葉結(jié)點層在上層已找到待查的關(guān)鍵碼，并不停止而是繼續(xù)沿指針向下一直查到葉結(jié)點層的這個關(guān)鍵碼B+樹的葉結(jié)點一般鏈接起來，形成一個雙鏈表

適合順序檢索（范圍檢索）實際應(yīng)用更廣需要的話，每一層結(jié)點也可以順序鏈接B+樹的插入插入——分裂過程和B樹類似注意保證上一層結(jié)點中有這兩個結(jié)點的最大關(guān)鍵碼（或最小關(guān)鍵碼）3階B+樹abefghkldijc506070407090809075808590657055604548503540253015510201020304040在上圖3階B+樹中插入15后，樹增高一層a’befghkldijc50607080907580859065705560454850354025305101520102030402070904090taB+樹的刪除當(dāng)關(guān)鍵碼不滿時，與左右兄弟進行調(diào)整、合并的處理和B樹類似關(guān)鍵碼在葉結(jié)點層刪除后，其在上層的復(fù)本可以保留，做為一個“分界關(guān)鍵碼”存在也可以替換為新的最大關(guān)鍵碼（或最小關(guān)鍵碼）準備在3階B+樹中刪除75沿a、d、k查找，找到葉結(jié)點在k中刪去75，發(fā)生下溢出，剩余關(guān)鍵碼80與右鄰l結(jié)點合并為新k’（80，85，90）父結(jié)點d中原分界碼80刪除d結(jié)點下溢出借左鄰c的關(guān)鍵碼，c和d的關(guān)鍵碼平分父結(jié)點a中的分界碼70修改為60

另一種B+樹葉結(jié)點中關(guān)鍵碼數(shù)目與非葉的不同內(nèi)部非葉結(jié)點構(gòu)成B樹葉的階與B+樹一致例如，葉結(jié)點階5，內(nèi)部階4補充：VSAMVSAM(VirtualStorageAccessMethod)—虛擬存儲存取方法B+樹的應(yīng)用一種索引順序文件的組織方式與存儲設(shè)備無關(guān)，存儲單位是“邏輯”的VSAM的組成索引集順序集（順序集索引）和索引集共同形成了B+樹結(jié)構(gòu)的文件索引數(shù)據(jù)集存放文件記錄記錄可以是變長的11.4.3

B樹的性能分析包含N個關(guān)鍵碼的B樹有N+1個外部空指針假設(shè)外部指針在第k層各層的結(jié)點數(shù)目第0層為根，第一層至少兩個結(jié)點，第二層至少2·個結(jié)點，第k層至少個結(jié)點，N=1,999,998，m=199時k=4一次檢索最多4層結(jié)點分裂次數(shù)設(shè)關(guān)鍵碼數(shù)為N(空指針N+1)，內(nèi)部結(jié)點數(shù)為p即

最差情況下每插入一個結(jié)點都經(jīng)過分裂(除第一個)，即p-1個結(jié)點都是分裂而來的，則每插入一個關(guān)鍵碼平均分裂結(jié)點個數(shù)為存儲效率分析B樹整個樹結(jié)構(gòu)關(guān)鍵碼不重寫，每個關(guān)鍵碼實質(zhì)上是（關(guān)鍵碼，頁塊地址）的二元組其中的記錄地址也稱為“隱含指針”B+樹的存儲效率實際上更高B+樹其實是多級索引形式最下一層是所有關(guān)鍵碼的全集，因此可以把此層形成順序鏈表非葉層結(jié)點中的關(guān)鍵碼不需要帶隱含指針假設(shè)一個主文件有N個記錄，假設(shè)一個頁塊可以存m個(關(guān)鍵碼，子結(jié)點頁塊地址)二元對假設(shè)B+樹平均每個結(jié)點有0.75m個子結(jié)點充盈度為(1+0.5)/2=75％因此B+樹的高度為可以容納m個(關(guān)鍵碼，子結(jié)點頁塊指針)，假設(shè)關(guān)鍵碼所占字節(jié)數(shù)與指針相同可以容納B樹的(關(guān)鍵碼，隱含指針，子結(jié)點頁塊指針)最多為2m/3(B樹為0.67m階)。假設(shè)B樹充盈度也是75％，則B樹結(jié)點有0.5m個子結(jié)點B樹的高度為B+樹應(yīng)用得更為廣泛B+樹的存儲效率更高檢索層次更少（樹較矮）操作更方便插入刪除操作更方便樹型結(jié)構(gòu)隨機存取葉層的拉鏈順序訪問因此，B+樹應(yīng)用得更為廣泛動態(tài)索引的問題要考慮并行策略

輔助索引維護困難

索引層數(shù)多

11.5位索引技術(shù)B樹適合于查找并取回少量記錄的情況對于數(shù)據(jù)倉庫的復(fù)雜交互式查詢，B樹有三個缺點：B樹對唯一值極少的（低基數(shù)）數(shù)據(jù)字段幾乎毫無價值在數(shù)據(jù)倉庫中構(gòu)造和維護索引的代價高對于帶有分組及聚合條件的復(fù)雜查詢無能為力Bit-Map（位圖）索引字段F的一個位圖索引是一個長度為n的位向量的集合（n為文件的記錄數(shù)）對于數(shù)據(jù)庫表的位圖索引state=AKstate=AL…state=NY0001010110010001003/13/13/13/13/13/1323638414346NYALNYAKNYAKAABAAB6951193101010110110datestorestateclasssalesState＝NYClass=A特征文件Signaturefile（也譯為“簽名文件”）倒排表(30,foo),(30,bar),(30,baz)(40,baz),(40,bar),(50,foo)記錄barbaz

foo3040501110110011表示在那個記錄中出現(xiàn)了相應(yīng)的字段值位圖索引特點按“列”為單位存儲數(shù)據(jù)列數(shù)據(jù)比行數(shù)據(jù)更易進行壓縮，可節(jié)省50%的磁盤空間索引空間比B樹小11.6紅黑樹11.6.1紅黑樹定義red-blacktree,簡稱RB-tree11.6.2紅黑樹相關(guān)性質(zhì)11.6.3結(jié)點插入算法11.6.4結(jié)點刪除算法紅黑樹：平衡的擴充二叉搜索樹顏色特征：結(jié)點是“紅色”或“黑色”

；根特征：根結(jié)點永遠是“黑色”的；外部特征：擴充外部葉結(jié)點都是空的“黑色”結(jié)點；內(nèi)部特征：“紅色”結(jié)點的兩個子結(jié)點都是“黑色”的不允許兩個連續(xù)的紅色結(jié)點深度特征：任何結(jié)點到其子孫外部結(jié)點的每條簡單路徑都包含相同數(shù)目的“黑色”結(jié)點91546212721“紅色”“黑色”擴充紅黑樹的階結(jié)點X的階（rank，也稱“黑色高度”）從該結(jié)點到外部結(jié)點的黑色結(jié)點數(shù)量不包括X結(jié)點本身，包括葉結(jié)點外部結(jié)點的階是零根的階稱為該樹的階91546212721rank=2rank=1rank=211.6.2紅黑樹的性質(zhì)(1)紅黑樹是滿二叉樹空葉結(jié)點也看作結(jié)點(2)階為k的紅黑樹路徑長度從根到葉的簡單路徑長度即樹高(3)階為k的紅黑樹的內(nèi)部結(jié)點最少是一棵完全滿二叉樹內(nèi)部結(jié)點數(shù)最少是2k-1915462127最短是k最小是k+1，最長是2k，最高是2k+1692紅黑樹的性質(zhì)(4)n個內(nèi)部結(jié)點的紅黑樹樹高最大是2

log2(n+1)+1證明：設(shè)紅黑樹的階為k，設(shè)紅黑樹的樹高是h。由性質(zhì)（2）得h<=2k+1則k>=(h-1)/2由性質(zhì)（3）得n>=2k–1即n>=2(h-1)/2–1可得出h<=2log2(n+1)+111.6.3插入算法先調(diào)用BST的插入算法把新記錄著色為紅色若父結(jié)點是黑色，則算法結(jié)束否則，雙紅調(diào)整6386384XAAX插入4插入算法調(diào)整1：重構(gòu)情況1：新增結(jié)點X的叔父結(jié)點是黑色每個結(jié)點的階都保持原值，調(diào)整完成Xα以祖結(jié)點為軸旋轉(zhuǎn)父結(jié)點AXBBACCα4種形式的結(jié)構(gòu)調(diào)整原則：保持BST的中序性質(zhì)246624642264264插入算法調(diào)整2：換色情況2：新增結(jié)點X的叔父結(jié)點也是紅色需要繼續(xù)檢查平衡X父祖換色AXBBACC對B繼續(xù)紅紅檢查αα插入4情況2紅紅沖突父和叔父也是紅父祖換色112141157854X插入4情況2紅紅沖突父和叔父也是紅父祖換色112141157854X578插入4情況2紅紅沖突父和叔父也是紅父祖換色情況1紅紅沖突叔父是黑重構(gòu)112141157854X57插入4情況2紅紅沖突父和叔父也是紅父祖換色情況1紅紅沖突叔父是黑重構(gòu)721118545141511.6.4刪除算法先調(diào)用BST的刪除算法待刪除的結(jié)點有一個以上的外部空指針，則直接刪除否則在右子樹中找到其后繼結(jié)點進行值交換（著色不變）刪除

v

是被刪除的內(nèi)結(jié)點,w

是被刪外結(jié)點,X

是w的兄弟如果v或者

X

是紅色,則把X標記為黑色即可否則,X

需要標記為雙黑,根據(jù)其兄弟結(jié)點C進行重構(gòu)調(diào)整6384vXw634X刪除8根據(jù)雙黑X

的兄弟C進行調(diào)整假設(shè)X是左子結(jié)點（若X為右孩子，則對稱）情況1：C是黑色，且子結(jié)點有紅色重構(gòu)，完成操作情況2：C是黑色,且有兩個黑子結(jié)點換色父結(jié)點B原為紅色，可能需要從B繼續(xù)向上調(diào)整情況3：C是紅色轉(zhuǎn)換狀態(tài)C轉(zhuǎn)為父結(jié)點，調(diào)整為情況1或2繼續(xù)處理情況1(a)重構(gòu)：侄子紅結(jié)點八字將兄弟結(jié)點C提上去C