双数组ppt课件

1、数据构造一、二康维鹏2019-10-245 5阶阶B-B-树例如树例如 【例】以下图给出了一棵包含【例】以下图给出了一棵包含2424个英文字母的个英文字母的5 5阶阶B-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)是孩子指针

2、。对于叶结点，每个Pi为空指针。keys(P0)K1keys(P1)K2KiMin，那么只需删去K及其右指针(*x是叶子，K的右指针为空)即可使删除操作终了。B-树的实现删除关键值情形二：假设x-keynum=Min，该叶子中的关键字个数已是最小值，删K及其右指针后会破坏B-树的性质(3)。假设*x的左(或右)邻兄弟结点*y中的关键字数目大于Min，那么将*y中的最大(或最小)关键字上移至双亲结点*parent中，而将*parent中相应的关键字下移至x中。显然这种挪动使得双亲中关键字数目不变；*y被移出一个关键字，故其keynum减1，因它原大于Min，故减少1个关键字后keynum仍大于等

3、于Min；而*x中已移入一个关键字，故删K后*x中仍有Min个关键字。涉及挪动关键字的三个结点均满足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树检索速度的前提下，提高空间利用率而提出的一种数据构造，本质上是一个确定有限自动机(determinis

5、tic finite automaton，简称DFA)。 双数组Double Array Trie DAT是采用两个线性数组(base和check)，base和check数组拥有一致的下标，下标即DFA中的每一个形状，也即TRIE树中所说的节点，base数组用于确定形状的转移，check数组用于检验转移的正确性。从形状s输入c到形状t的一个转移必需满足如下条件： bases + c = t ，用于确定转移 checkbases + c = s，用于检验前一形状双数组的一个实例“北京、“北京大学、北京市“、 “市区、“大学、“北京市区、“北大、 “市大学 “、 “大北京“北=1， 京=2，大=3

6、，学=4，市=5，区=6下标下标0 01 12 23 34 45 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=

7、abs(base1)+idx(1)=7Check7=1next=abs(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)依次扫描排序队列，计算更新队

8、列中各形状的base数组和check数组，并更新队列，直到队列为空。保管形状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 =b

9、asecurrState+idx(w1) ; ramainContent= ramainContent.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 0

10、0 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北大市(北)京(北)京大学(北)京市(北)京市区(北)大(大)学(大)北京(市)区(市)大学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

11、(市)=5，idx(区)=6queue ： 1-京, 1-京大学, 1-京市, 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

12、，check5+2=1，check5+3=1同理，得到base3=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北京北大大北大学市大市区(北京)(北京)大学(北京)市(北京)市区(北大)(大北)京(大学)(市区)北京(北)京

13、(北)京大学(北)京市(北)京市区(北)大大更新后的queue为：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，id

14、x(大)=3，idx(学)=4，idx(市)=5，idx(区)=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-区第四次遍历后：

15、下标下标0 01 12 23 34 45 56 67 78 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 9101011111212131314141515161617171818baseba

16、se0 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北京北大大北京大学市区市大学北京市北京市区北京大学Queue为空，步骤(4)终了Thank youTrie树的另一种变形AC自动机AC自动机分为3步：构造一棵Trie树，构造失败指针和方式匹配过程。AC自动机是用来处置多串匹配问题的，即给他很多字串，再给他一篇文章，让他在文章中找这些串能否出现过，在哪出现。它是结合了trie树与KMP算法思想。classTrieNodeintlen;/表示单词长度booleanisword;/能否为该单词的最后一个节点TrieNodefail;/失败指针Trie