1、數據結構一、二康維鵬2010-10-245 5階階b-b-樹示例樹示例 【例】下圖給出了一棵包含24個英文字母的5階b-樹的存儲結構圖。 說明：按照定義，在5階b-樹里，根中的關鍵字數目可以是14，子樹數可以是25；其它的結點中關鍵字數目可以是24，若該結點不是葉子，則它可以有35棵子樹。b-樹一棵m(m3)階的b-樹是滿足如下性質的m叉樹：(1)每個結點至少包含下列數據域： (n，p0，kl，p1，k2，ki，pi) n為關鍵字總數 ki(1in)是關鍵字，關鍵字序列遞增有序：k1 k2ki。 pi(0in)是孩子指針。對于葉結點，每個pi為空指針。keys(p0)k1keys(p1)k2k

2、imin，則只需刪去k及其右指針(*x是葉子，k的右指針為空)即可使刪除操作結束。b-樹的實現刪除關鍵值情形二：若x-keynum=min，該葉子中的關鍵字個數已是最小值，刪k及其右指針后會破壞b-樹的性質(3)。若*x的左(或右)鄰兄弟結點*y中的關鍵字數目大于min，則將*y中的最大(或最小)關鍵字上移至雙親結點*parent中，而將*parent中相應的關鍵字下移至x中。顯然這種移動使得雙親中關鍵字數目不變；*y被移出一個關鍵字，故其keynum減1，因它原大于min，故減少1個關鍵字后keynum仍大于等于min；而*x中已移入一個關鍵字，故刪k后*x中仍有min個關鍵字。涉及移動關鍵

3、字的三個結點均滿足b-樹的性質(3)。上述操作后仍滿足b-樹的性質(1)。移動完成后，刪除過程亦結束。b-樹的實現刪除關鍵值情形三：若*x及其相鄰的左右兄弟(也可能只有一個兄弟)中的關鍵字數目均為最小值min，則上述的移動操作就不奏效，此時須*x和左或右兄弟合并。不妨設*x有右鄰兄弟*y(結點取代*x對左鄰兄弟的討論與此類似)，在*x中刪去k及其右子樹后，將雙親結點*parent中介于*x和*y之間的關鍵字k，作為中間關鍵字，與并x和*y中的關鍵字一起合并為一個新的和*y。trie樹trie,又稱字典樹、單詞查找樹,是一種樹形結構，用于保存大量的字符串。它的優點是：利用字符串的公共前綴來節約存

4、儲空間，查找速度快。其基本性質可以歸納為：1.根節點不包含字符，除根節點外每一個節點都只包含一個字符。2.從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串。3.每個節點的所有子節點包含的字符都不相同。trie樹的缺點：內存消耗非常大因此，往往利用trie樹的一種變形，doublearraytrie。雙數組trie樹double array trie是trie樹的一種變形，它是在保證trie樹檢索速度的前提下，提高空間利用率而提出的一種數據結構，本質上是一個確定有限自動機(deterministic finite automaton，簡稱dfa)。 雙數組double arra

5、y trie （dat）是采用兩個線性數組(base和check)，base和check數組擁有一致的下標，（下標）即dfa中的每一個狀態，也即trie樹中所說的節點，base數組用于確定狀態的轉移，check數組用于檢驗轉移的正確性。從狀態s輸入c到狀態t的一個轉移必須滿足如下條件： bases + c = t ，用于確定轉移 checkbases + c = s，用于檢驗前一狀態雙數組的一個實例“北京”、“北京大學”、北京市“、 “市區”、“大學”、“北京市區”、“北大”、 “市大學 “、 “大北京“北=1， 京=2，大=3，學=4，市=5，區=6下標下標0 01 12 23 34 45

6、56 67 78 89 9101011111212131314141515161617171818basebase0 05 50 08 80 07 70 0-11-11-8-89 91111-11-11-12-12-13-131313-15-15-12-12-17-17-18-18checkcheck0 00 00 00 00 00 00 01 11 13 35 59 93 35 57 710107 714141616北北京京大大學學r北北京北京大北京大學next=abs(base0)+idx(0)=1check1=0next=abs(base1)+idx(1)=7check7=1next=a

7、bs(base7)+idx(2)=14check14=7next=abs(base14)+idx(3)=17check17=14base170則baseidxstate=-baseidxstate,(b)否則baseidxstate=-idxstate; idx(北)=1， idx(京)=2，idx(大)=3，idx(學)=4，idx(市)=5，idx(區)=6queue：0-北京, 0-北京大學, 0-北京市, 0-北京市區, 0-北大, 0-大北京, 0-大學, 0-市區, 0-市大學(4)順次掃描排序隊列，計算更新隊列中各狀態的base數組和check數組，并更新隊列，直到隊列為空。保留

8、狀態0為初始化值。計算basecurrstate：若basecurrstate=bs，則bs滿足下面條件：對于隊列中任意當前狀態是currstate的詞語w，設其第一個字是w1，則：basebs+idx(w1)=0 & checkbs+idx(w1)=0更新base數組和check數組：更新basecurrstate=bs，checkbs+idx(w1)= currstate 。更新隊列：按隊列順序，依次去掉各個單詞的首個字w1，保留單詞剩余部分，并且記錄按照w1跳轉到的下一個狀態： currstate =basecurrstate+idx(w1) ; ramaincontent= ramai

9、ncontent.substring(1);雙數組trie樹構造 idx(北)=1， idx(京)=2，idx(大)=3，idx(學)=4，idx(市)=5，idx(區)=6queue：0-北京, 0-北京大學, 0-北京市, 0-北京市區, 0-北大, 0-大北京, 0-大學, 0-市區, 0-市大學第一次遍歷后結果如下：下標下標0 01 12 23 34 45 56 67 78 89 9101011111212131314141515161617171818basebase0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0ch

10、eckcheck0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0北大市(北)京(北)京大學(北)京市(北)京市區(北)大(大)學(大)北京(市)區(市)大學1-京, 1-京大學, 1-京市, 1-京市區, 1-大3-北京, 3-學5-區, 5-大學queue：1-京, 1-京大學, 1-京市, 1-京市區, 1-大, 3-北京, 3-學, 5-區, 5-大學雙數組trie樹構造 idx(北)=1， idx(京)=2，idx(大)=3，idx(學)=4，idx(市)=5，idx(區)=6queue： 1-京, 1-京大學, 1-京

11、市, 1-京市區, 1-大, 3-北京, 3-學, 5-區, 5-大學第二次遍歷，需要計算狀態1、3、5的值。例如，計算base1的bs值。首先，查看那些單詞的currstate=1，得到1-京, 1-京大學, 1-京市, 1-京市區, 1-大其次，這些單詞的第一個字的不同下標有：idx(京)=2，idx(大)=3因此，bs值需要滿足條件是：basebs+2=0，basebs+3=0，checkbs+2=0，checkbs+3=0，bs+26一個滿足條件的值，為bs=5。更新狀態1的base與check數組。得到，base1=5，check5+2=1，check5+3=1同理，得到base3=

12、8；base5=7下標下標0 01 12 23 34 45 56 67 78 89 9101011111212131314141515161617171818basebase0 05 50 08 80 07 70 00 00 00 00 00 00 00 00 00 00 00 00 0checkcheck0 00 00 00 00 00 00 01 11 13 35 50 03 35 50 00 00 00 00 0北京北大大北大學市大市區(北京)(北京)大學(北京)市(北京)市區(北大)(大北)京(大學)(市區)北京(北)京(北)京大學(北)京市(北)京市區(北)大大更新后的queue為：

13、queue：7-大學, 7-市, 7-市區, 9-京, 10-學(市大)學下標下標0 01 12 23 34 45 56 67 78 89 9101011111212131314141515161617171818basebase0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0checkcheck0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0雙數組trie樹構造 idx(北)=1， idx(京)=2，idx(大)=3，idx(學)=4，idx(市)=5，idx(

14、區)=6queue：7-大學, 7-市, 7-市區, 9-京, 10-學下標下標0 01 12 23 34 45 56 67 78 89 9101011111212131314141515161617171818basebase0 05 50 08 80 07 70 011110 09 911110 00 00 00 00 00 00 00 0checkcheck0 00 00 00 00 00 00 01 11 13 35 59 93 35 57 710107 70 00 0第三次遍歷后：queue：14-學, 16-區第四次遍歷后：下標下標0 01 12 23 34 45 56 67 78

15、 89 9101011111212131314141515161617171818basebase0 05 50 08 80 07 70 011110 09 911110 00 00 013130 012120 00 0checkcheck0 00 00 00 00 00 00 01 11 13 35 59 93 35 57 710107 714141616(5)最后遍歷詞表，標記詞語：下標下標0 01 12 23 34 45 56 67 78 89 9101011111212131314141515161617171818basebase0 05 50 08 80 07 70 0-11-11

16、-8-89 91111-11-11-12-12-13-131313-15-15-12-12-17-17-18-18checkcheck0 00 00 00 00 00 00 01 11 13 35 59 93 35 57 710107 714141616北京北大大北京大學市區市大學北京市北京市區北京大學queue為空，步驟(4)結束thank youtrie樹的另一種變形ac自動機ac自動機分為3步：構造一棵trie樹，構造失敗指針和模式匹配過程。ac自動機是用來處理多串匹配問題的，即給你很多字串，再給你一篇文章，讓你在文章中找這些串是否出現過，在哪出現。它是結合了trie樹與kmp算法思想。classtrienodeintlen;/表示單詞長度booleanisword;/是否為該單詞的最后一個節點trienodefail;/失敗指針trienode