數(shù)據(jù)結構與算法-補充考研內容

11補充考研內容內容提要11.4.1B樹

11.4.2B+樹12.1多維數(shù)組12.2廣義表和存儲管理補充考研內容2/112第11章基本概念11.1線性索引11.2靜態(tài)索引11.3倒排索引11.4動態(tài)索引——B/B+樹11.5位索引技術11.6紅黑樹——以前的錄像補充考研內容3/112索引索引(indexing)——(關鍵碼，指針)指針指向“主文件”中的完整記錄索引文件(indexfile)索引技術是組織大型數(shù)據(jù)庫的一種重要技術高效率的檢索插入、更新、刪除(20,a9)(21,a10)(45,a13)(47,a14)(50,a5)(52,a16)4/112補充考研內容線性索引文件按照關鍵碼的順序進行排序文件中的指針指向存儲在磁盤上的文件記錄起始位置或者主索引中主碼的起始位置92733755數(shù)據(jù)庫記錄線性索引文件5/112補充考研內容基本概念動態(tài)索引結構索引結構本身也可能發(fā)生改變在系統(tǒng)運行過程中插入或刪除記錄時目的保持較好的性能例如較高的檢索效率6/112補充考研內容11.4.1B樹一種平衡的多分樹

(BalancedTree)

3階B樹2-3樹7/112補充考研內容B樹隱含指針8/112補充考研內容(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)關鍵碼文件頁內地址主文件9/112補充考研內容m階B樹的結構定義(1)每個結點至多有m個子結點；(2)除根結點和葉結點外，其它每個結點至少有個子結點；(3)根結點至少有兩個子結點唯一例外的是根結點就是葉結點時沒有子結點此時B樹只包含一個結點(4)所有的葉結點在同一層；(5)有k個子結點的非根結點恰好包含k-1個關鍵碼。

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

14/112補充考研內容B樹檢索長度設B樹的高度為h獨根樹高為1在自頂向下檢索到葉結點的過程中可能需要進行h次讀盤

15/112補充考研內容B樹插入注意保持性質，特別是等高和階的限制

1)找到最底層，插入

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

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

2021243145475052151417/112補充考研內容m=3，插入5518331223304810152021243145475052插入5550525518/112補充考研內容

m=3，葉結點分裂，把52提升到父結點結點分裂183312233048101520212431454750525552505519/112補充考研內容插入引起3階B樹根結點分裂的例子插入19183312233048101520212431454750521919202120/112補充考研內容

m=3葉結點分裂1833122330481015243145475052192021192123302021/112補充考研內容

m=3第二層結點分裂192118331248101524314547505220233030

2018332322/112補充考研內容

m=3根結點分裂3019211248101524314547505220

23

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

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

=h+2(h-1)+3=3h+126/112補充考研內容B樹的刪除刪除的關鍵碼不在葉結點層先把此關鍵碼與它在B樹里的后繼對換位置，然后再刪除該關鍵碼

27/112補充考研內容B樹的刪除(續(xù))刪除的關鍵碼在葉結點層刪除后關鍵碼個數(shù)不小于直接刪除關鍵碼個數(shù)小于如果兄弟結點關鍵碼個數(shù)不等于從兄弟結點移若干個關鍵碼到該結點中來(父結點中的一個關鍵碼要做相應變化)如果兄弟結點關鍵碼個數(shù)等于合并28/112補充考研內容120150

2550

103

5階B樹刪除示例acedfghbi1115

3543

8195100

108110115118134146

156177

29/112補充考研內容

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

150

2550

103

acedfghbi1115

3543

8195100

108110115

146

156177

120

134

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

146

134

30/112補充考研內容1182550

103

cedfghbi1115

3543

8195100

108110115

134146

177

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

134146

a31/112補充考研內容1182550

103

cedfgh’b1115

3543

8195100

108110115

134146156177h,i合并成為h’c溢出，向左鄰借關鍵碼借不到，b,c結點合并1182550

a2550103118

a’32/112補充考研內容11.4.2B+樹是B樹的一種變形在葉結點上存儲信息的樹所有的關鍵碼均出現(xiàn)在葉結點上

各層結點中的關鍵碼均是下一層相應結點中最大關鍵碼（或最小關鍵碼）的復寫

33/112補充考研內容B+樹的結構定義m階B+樹的結構定義如下：(1)每個結點至多有m個子結點；(2)每個結點(除根外)至少有個子結點；(3)根至少有兩個子結點；(4)所有的葉結點在同一層；(5)有k個子結點的結點必有k個關鍵碼。其實，根可以為空，或者獨根34/112補充考研內容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

35/112補充考研內容B+樹的查找查找應該到葉結點層在上層已找到待查的關鍵碼，并不停止而是繼續(xù)沿指針向下一直查到葉結點層的這個關鍵碼B+樹的葉結點一般鏈接起來，形成一個雙鏈表

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

42/112補充考研內容另一種B+樹葉結點中關鍵碼數(shù)目與非葉的不同內部非葉結點構成B樹葉的階與B+樹一致例如，葉結點階5，內部階443/112補充考研內容補充：VSAMVSAM(VirtualStorageAccessMethod)—虛擬存儲存取方法B+樹的應用一種索引順序文件的組織方式與存儲設備無關，存儲單位是“邏輯”的44/112補充考研內容45/112補充考研內容11.4.1B樹

11.4.2B+樹12.1多維數(shù)組12.2廣義表和存儲管理補充考研內容46/112基本概念數(shù)組（Array）是數(shù)量和元素類型固定的有序序列靜態(tài)數(shù)組必須在定義它的時候指定其大小和類型動態(tài)數(shù)組可以在程序運行才分配內存空間47/112補充考研內容基本概念（續(xù)）多維數(shù)組（Multi-array）是向量的擴充向量的向量就組成了多維數(shù)組可以表示為：

ELEMA[c1..d1][c2..d2]…[cn..dn]ci和di是各維下標的下界和上界。所以其元素個數(shù)為：

48/112補充考研內容數(shù)組的空間結構二維數(shù)組三維數(shù)組d1[1..3],d2[1..5],d3[1..5]分別為3個維49/112補充考研內容數(shù)組的存儲內存是一維的，所以數(shù)組的存儲也只能是一維的

以行為主序（也稱為“行優(yōu)先”）以列為主序（也稱為“列優(yōu)先”）50/112補充考研內容Pascal的行優(yōu)先存儲

a11a12a13a14a15…a1nam1am2am3am4am5…amna21a22a23a24a25…a2na31a32a33a34a35…a3na41a42a43a44a45…a4n…………………51/112補充考研內容FORTRAN的列優(yōu)先存儲

am2am3am4am5…amn…a2na32a33a34a35…a3na42a43a44a45…a4nam1a31a41…………………a12a13a14a15…a1na11a22a23a24a25a21next52/112補充考研內容C/C++、Pascal行優(yōu)先先排最右的下標從右向左最后最左的下標例如對于三維數(shù)組a[1..k,1..m,1..n]的元素axyz可以如下排列：53/112補充考研內容Pascal語言的行優(yōu)先存儲

a111a112a113

…a11n

a121a122a123

…a12n

…………

a1m1a1m2a1m3

…a1mn

a211a212a213

…a21n

a221a222a223

…a22n

…………

a2m1a2m2a2m3

…a2mn

┇

ak11ak12ak13

…ak1n

ak21ak22ak23

…ak2n

…………

akm1akm2akm3

…akmn12m

2

2

2

2

2

2

2

2

2

2

2

2

54/112補充考研內容FORTRAN列優(yōu)先先排最左的下標從左向右最后最右的下標例如對于三維數(shù)組a[1..k,1..m,1..n]的元素axyz可以如下排列：55/112補充考研內容FORTRAN的列優(yōu)先存儲

a111a211a311

…ak11a121a221a321

…ak21

…………

a1m1a2m1a3m1

…akm1

a112a212a312

…ak12

a122a222a322

…ak22

…………

a1m2a2m2a3m2

…akm2

┇

a11na21na31n

…ak1n

a12na22na32n

…ak2n

…………

a1mna2mna3mn

…akmn

1

2

3

k

12m

56/112補充考研內容

C++多維數(shù)組ELEMA[d1][d2]…[dn];57/112補充考研內容用數(shù)組表示特殊矩陣三角矩陣：上三角、下三角對稱矩陣對角矩陣稀疏矩陣58/112補充考研內容下三角矩陣圖例一維數(shù)組list[0..(n2+n)/2-1]矩陣元素ai,j與線性表相應元素的對應位置為

list[(i2+i)/2+j]（i>=j）59/112補充考研內容對稱矩陣元素滿足性質ai,j=aj,i，0<=（i,j）<n例如無向圖的相鄰矩陣存儲其下三角的值，對稱關系映射

存儲于一維數(shù)組sa[0..n(n+1)/2-1]

sa[k]和矩陣元ai,j之間存在著一一對應的關系：60/112補充考研內容對角矩陣對角矩陣是指所有的非零元素都集中在主對角線及以它為中心的其他對角線上。如果

|i-j|>1，那么數(shù)組元素a[i][j]=0。下面是一個3對角矩陣：a0,0a1,1a0,1a1,0an-1,n-2an-1,n-1an-2,n-1a1,200………………61/112補充考研內容稀疏矩陣非零元素非常少，且分布不規(guī)律的矩陣62/112補充考研內容稀疏因子在m×n的矩陣中，有t個非零元素，則稀疏因子為:當這個值小于0.05時，可以認為是稀疏矩陣三元組(i,j,aij)：輸入/輸出常用i是該元素的行號j是該元素的列號aij是該元素的值63/112補充考研內容稀疏矩陣的十字鏈表十字鏈表有兩組鏈表組成行和列的指針序列每個結點都包含兩個指針：同一行的后繼，同一列的后繼030056200

013

115

202

列鏈表頭指針

行

鏈表頭指針

126

∧

∧

∧

∧

∧

∧

64/112補充考研內容經典矩陣乘法A[c1..d1][c3..d3]，B[c3..d3][c2..d2],C[c1..d1][c2..d2]。

d3

C＝A×B(Cij＝∑Aik·Bkj)

k=c3

for(i=c1;i<=d1;i++)

for(j=c2;j<=d2;j++){

sum=0;

for(k=c3;k<=d3;k++)

sum=sum+A[i,k]*B[k,j];

C[i，j]=sum;

}65/112補充考研內容p=d1-c1+1，m=d3-c3+1，n=d2-c2+1；A為p×m的矩陣，B為m×n的矩陣，乘得的結果C為p×n的矩陣經典矩陣乘法所需要的時間代價為O(p×m×n)66/112補充考研內容稀疏矩陣乘法

=012

101

02-2

214

∧∧∧∧∧06-1004é?êù?ú6列鏈表頭指針

行

鏈表頭指針

003

035

∧∧11-1

022

∧∧∧∧-14finish67/112補充考研內容稀疏矩陣乘法時間代價A為p×m的矩陣，B為m×n的矩陣，乘得的結果C為p×n的矩陣若矩陣A中行向量的非零元素個數(shù)最多為ta矩陣B中列向量的非零元素個數(shù)最多為tb總執(zhí)行時間降低為O((ta+tb)×p×n)經典矩陣乘法所需要的時間代價為O(p×m×n)68/112補充考研內容稀疏矩陣的應用一元多項式69/112補充考研內容12.2廣義表和存儲管理廣義表儲存管理70/112補充考研內容12.2.1廣義表基本概念廣義表的各種類型廣義表的存儲廣義表的周游算法71/112補充考研內容基本概念

回顧線性表由n（n≥0）個數(shù)據(jù)元素組成的有限有序序列線性表的每個元素都具有相同的數(shù)據(jù)類型如果一個線性表中還包括一個或者多個子表，那就稱之為廣義表（GeneralizedLists，也稱Multi-list）一般記作：L＝（x0，x1，…，xi，…，xn-1）72/112補充考研內容L＝（x0，x1，…，xi，…，xn-1）L是廣義表的名稱n為長度每個xi（0≤i≤n-1）是L的成員可以是單個元素，即原子（atom)也可以是一個廣義表，即子表（sublist）廣義表的深度：表中元素都化解為原子后的括號層數(shù)73/112補充考研內容L＝（x0，x1，…，xi，…，xn-1）表頭head=x0表尾tail=（x1，…，xn-1）規(guī)模更小的表有利于存儲和實現(xiàn)74/112補充考研內容

廣義表的各種類型純表（purelist）

從根結點到任何葉結點只有一條路徑也就是說任何一個元素（原子、子表）只能在廣義表中出現(xiàn)一次

(x1,(y1,(a1,a2),y3),x3,(z1,z2))x1y1

a1

a2

y3z1z2

x3

75/112補充考研內容廣義表的各種類型（續(xù)）可重入表其元素(包括原子和子表)可能會在表中多次出現(xiàn)如果沒有回路圖示對應于一個DAG對子表和原子標號(L1:(a,b),(L1,c,L2:(d)),(L2,e,L3:(f,g)),L3)

(((a,b)),((a,b),c,d),(d,e,f,g),(f,g))

L1

L2

L3

a

b

d

e

f

g

c

特例：循環(huán)表（即遞歸表）76/112補充考研內容廣義表的各種類型（續(xù)）循環(huán)表包含回路

循環(huán)表的深度為無窮大

(L1:(L2:(L1,a)),(L2,L3:(b)),(L3,c),L4:(d,L4))L1

L2

L3

abcL4

d

77/112補充考研內容78/112補充考研內容圖

再入表

純表(樹)

線性表

廣義表是線性與樹形結構的推廣遞歸表是有回路的再入表廣義表應用函數(shù)的調用關系內存空間的引用關系LISP語言79/112補充考研內容廣義表存儲ADTtypedefenum{ATOM,LIST}TAG;//ATOM=0：單元素；LIST=1：子表typedefstructGLNode{

TAGtag;

union{

ElemTypedata; GLNode*sublist;//子表的頭指針

};

GLNode*next;//后繼結點

};80/112補充考研內容廣義表存儲ADT（續(xù)）不帶頭結點的廣義表鏈在刪除結點的時候會出現(xiàn)問題

刪除結點data就必須進行鏈調整

1

1

1∧

data

0

head

D1

0∧

D2

0∧

finishdata81/112補充考研內容增加頭指針，簡化刪除、插入操作重入表，尤其是循環(huán)表mark標志位——圖的因素

-1

1

-1

1∧

data

0

head(ref=0)

D1

0∧

head(ref=1)

1

-1

head(ref=2)

D2

0

∧

廣義表存儲ADT（續(xù)）82/112補充考研內容帶表頭結點的循環(huán)廣義表83/112補充考研內容(L1:(L2:(a)),L184/112補充考研內容finish(L1:(L2:(a,L1))Lx:L3,L2,:(b)),Ly:(L3,c),L4:(d,))L4(next85/112補充考研內容12.2.2存儲管理技術內存管理存在的問題可利用空間表存儲的動態(tài)分配和回收伙伴系統(tǒng)失敗處理策略和無用單元回收86/112補充考研內容動態(tài)內存分配new和delete內存管理技術鏈表、廣義表87/112補充考研內容分配與回收

內存管理最基本的問題分配存儲空間回收被“釋放”的存儲空間碎片問題存儲的壓縮

無用單元收集無用單元：可以回收而沒有回收的空間

內存泄漏(memoryleak)

程序員忘記delete已經不再使用的指針88/112補充考研內容虛擬存儲：內存溢出的管理溢出發(fā)生后，把內存中某些數(shù)據(jù)暫存到外存選擇最近不使用的那些結點0-4k4k-8k8k-12k12k-16k16k-20k0-4k4k-8k8k-12k12k-16k16k-20k20k-24k24k-28k28k-32k32k-36k36k-40k虛擬地址空間物理內存地址1304289/112補充考研內容可利用空間表把存儲器看成一組變長塊數(shù)組一些塊是已分配的鏈接空閑塊，形成可利用空間表(freelist)存儲分配和回收newp從可利用空間分配deletep把p指向的數(shù)據(jù)塊返回可利用空間表空間不夠，則求助于失敗策略

90/112補充考研內容91/112補充考研內容可利用空間表的函數(shù)重載

template<classElem>classLinkNode{ private: staticLinkNode*avail; //可利用空間表頭指針

public: Elemvalue; //結點值

LinkNode*next; //指向下一結點的指針

LinkNode(constElem&val,LinkNode*p); LinkNode(LinkNode*p=NULL); //構造函數(shù)

void*operatornew(size_t); //重載new運算符

voidoperatordelete(void*p);//重載delete運算符};92/112補充考研內容//重載new運算符實現(xiàn)template<classElem>void*LinkNode<Elem>::operatornew(size_t){ if(avail==NULL) //可利用空間表為空

return::newLinkNode; //利用系統(tǒng)的new分配空間

LinkNode<Elem>*temp=avail;//從可利用空間表中分配

avail=avail->next; returntemp;}93/112補充考研內容//重載delete運算符實現(xiàn)template<classElem>voidLinkNode<Elem>::operatordelete(void*p){ ((LinkNode<Elem>*)p)->next=avail; avail=(LinkNode<Elem>*)p;}94/112補充考研內容可利用空間表：單鏈表棧new即棧的刪除操作delete即棧的插入操作直接引用系統(tǒng)的new和delete操作符，需要強制用“::n