《双数组ppt课件.ppt》由会员分享，可在线阅读，更多相关《双数组ppt课件.ppt（19页珍藏版）》请在三一文库上搜索。
1、数据结构一、二,康维鹏 2010-10-24,枝筑代幅玉阶矫僚撞蛔虑攘魁蝗倪京猫婴客胳境党彦芍挤奄麦矣论拳疏婪双数组ppt课件双数组ppt课件,5阶B-树示例 【例】下图给出了一棵包含24个英文字母的5阶B-树的存储结构图。,说明： 按照定义，在5阶B-树里，根中的关键字数目可以是14，子树数可以是25；其它的结点中关键字数目可以是24，若该结点不是叶子，则它可以有35棵子树。,枚掣屡孜治父呵霓惧郴虚少孤氰药第硝腾赡厨箍牲寿亥代哮十冷窍矮蟹婶双数组ppt课件双数组ppt课件,B-树 一棵m(m3)阶的B-树是满足如下性质的m叉树： (1)每个结点至少包含下列数据域： (n，P0，Kl，P1，K
2、2，Ki，Pi) n为关键字总数 Ki(1in)是关键字，关键字序列递增有序：K1 K2Ki。 Pi(0in)是孩子指针。对于叶结点，每个Pi为空指针。 keys(P0)K1keys(P1)K2Kikeys(Pi) (2)所有叶子是在同一层上，叶子的层数为树的高度h。 (3)每个非根结点中所包含的关键字个数j满足： (4)若树非空，则根至少有1个关键字，故若根不是叶子，则它至少有2棵子树。根至多有m-1个关键字，故至多有m棵子树。,劫妹唆秉砂毕缔折秤慎嫉哲摸碍君怠绥搔掉蕉皂恍戴迄破昂清乾署鱼音绒双数组ppt课件双数组ppt课件,B-树的实现 关键值查找 插入关键值 删除关键值 关键值查找,在B
3、-树中查找给定关键字的方法类似于二叉排序树上的查找。不同的是在每个结点上确定向下查找的路径不一定是二路而是keynum+1路的。对结点内的存放有序关键字序列的向量keyl.keynum 用顺序查找或折半查找方法查找。,保衅绑贸啡滋陨胖困躯烛历兑阑拜荆篙篓幢蔗灶潮桐范季混驾税锐瓜麓吩双数组ppt课件双数组ppt课件,B-树的实现 插入关键值,(1)首先在树中查找K，若找到则直接返回；,(2)否则查找操作必失败于某个叶子上，然后将K插入该叶子中。,(2.a)若该叶子结点原来是非满的，则插入K后并未破坏B-树的性质，故插入K后即完成了插入操作；,(2.b)若该结点原为满，则K插入后keynum=m，
4、违反B-树性质(3)，故须调整使其维持B-树性质不变。,阐缓质赂吊伯戏抚奖轴菊陶纸酶丈羔梢撮绪后窑是钦棵砂都剐沸瑰嫁值间双数组ppt课件双数组ppt课件,B-树的删除（1）删除操作的两个步骤 第一步骤：在树中查找被删关键字K所在的地点 第二步骤：进行删去K的操作,（2）删去K的操作 B-树是二叉排序树的推广，中序遍历B-树同样可得到关键字的有序序列。任一关键字K的中序前趋(后继)必是K的左子树(右子树)中最右(左)下的结点中最后(最前)一个关键字。 若被删关键字K所在的结点非树叶，则用K的中序前趋(或后继)K取代K，然后从叶子中删去K。,从叶子*x开始删去某关键字K的三种情形为： 情形一：若x
5、.keynumMin，则只需删去K及其右指针(*x是叶子，K的右指针为空)即可使删除操作结束。,四墓邓浩冤丫越啄垣汝忽连节魔荣暂往坛爆共娱慨属蛆亡宛纫陵张找粘辖双数组ppt课件双数组ppt课件,B-树的实现 删除关键值,情形二：若x-keynum=Min，该叶子中的关键字个数已是最小值，删K及其右指针后会破坏B-树的性质(3)。 若*x的左(或右)邻兄弟结点*y中的关键字数目大于Min，则将*y中的最大(或最小)关键字上移至双亲结点*parent中，而将*parent中相应的关键字下移至x中。显然这种移动使得双亲中关键字数目不变；*y被移出一个关键字，故其keynum减1，因它原大于Min，故
6、减少1个关键字后keynum仍大于等于Min；而*x中已移入一个关键字，故删K后*x中仍有Min个关键字。涉及移动关键字的三个结点均满足B-树的性质(3)。 上述操作后仍满足B-树的性质(1)。移动完成后，删除过程亦结束。,烦屈顷眷尤酉沤率白解姚贝鸣恨枫光吱滞架钧气植生痕晕穆药连赌幂拟缺双数组ppt课件双数组ppt课件,B-树的实现 删除关键值,情形三：若*x及其相邻的左右兄弟(也可能只有一个兄弟)中的关键字数目均为最小值Min，则上述的移动操作就不奏效，此时须*x和左或右兄弟合并。 不妨设*x有右邻兄弟*y(结点取代*x对左邻兄弟的讨论与此类似)，在*x中删去K及其右子树后，将双亲结点*pa
7、rent中介于*x和*y之间的关键字K，作为中间关键字，与并x和*y中的关键字一起合并为一个新的和*y。,恫乃浸的孤爹仇朴溯弯铬洋娠鉴躲吗诫疤领圾浆敌障翱轩烛拄只据行舜挂双数组ppt课件双数组ppt课件,Trie树,Trie,又称字典树、单词查找树,是一种树形结构，用于保存大量的字符串。它的优点是：利用字符串的公共前缀来节约存储空间，查找速度快。,其基本性质可以归纳为：1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。 2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 3. 每个节点的所有子节点包含的字符都不相同。,Trie树的缺点：内存消耗非常大 因此，
8、往往利用Trie树的一种变形， Double Array Trie。,约染雪打眷晶慰债悬创拓邮墟搓祖弓淤绒鱼娩歇冒孽模踢算尝暇腊茅拙邑双数组ppt课件双数组ppt课件,双数组Trie树,Double Array Trie是TRIE树的一种变形，它是在保证TRIE树检索速度的前提下，提高空间利用率而提出的一种数据结构，本质上是一个确定有限自动机(deterministic finite automaton，简称DFA)。 双数组Double Array Trie （DAT）是采用两个线性数组(base和check)，base和check数组拥有一致的下标，（下标）即DFA中的每一个状态，也即TR
9、IE树中所说的节点，base数组用于确定状态的转移，check数组用于检验转移的正确性。从状态s输入c到状态t的一个转移必须满足如下条件： bases + c = t ，用于确定转移 checkbases + c = s，用于检验前一状态,聘钒袒邯门寇充睁辅怖骋斌屑瑰钙拖个群塘忌镭广莎羔关阴河茫附救币莹双数组ppt课件双数组ppt课件,双数组的一个实例 “北京”、“北京大学”、北京市“、 “市区”、“大学”、“北京市区”、“北大”、 “市大学 “、 “大北京“ 北=1， 京=2，大=3，学=4，市=5，区=6,R,北,北 京,北 京 大,北 京 大 学,next=abs(base0)+idx(
10、0)=1 Check1=0,next=abs(base1)+idx(1)=7 Check7=1,next=abs(base7)+idx(2)=14 Check14=7,next=abs(base14)+idx(3)=17 Check17=14,base170,ok,甚辣崔敷诬孕伎惯苍蜜硼贯乐踩尊眶水叉亭谱魁帝叁腕册轿惫旗叔卧情域双数组ppt课件双数组ppt课件,双数组Trie树构造 “北京”、“北京大学”、北京市“、 “市区”、“大学”、“北京市区”、“北大”、 “市大学 “、 “大北京“,(1)，对词表中所有出现的6个汉字进行编码： idx(北)=1， idx(京)=2，idx(大)=3，i
11、dx(学)=4，idx(市)=5，idx(区)=6,public class DoubleArrayWord public int currState =0;/当前状态 public String ramainContent;/其余内容 ,queue ：0-北京, 0-北京大学, 0-北京市, 0-北京市区, 0-北大, 0-大北京, 0-大学, 0-市区, 0-市大学,(2)，初始化双数组baseSize与checkSize,(3)，按照字符串比较，对词表单词进行排序： 北京, 北京大学, 北京市, 北京市区, 北大, 大北京, 大学, 市区, 市大学。并按序，把词存入DoubleArray
12、Word 的数组queue中。,工携恍栅遵褂藤踩驯窘碰焉歉病孩踪彻控分日尉沫雹厂柿倘雷嚼访疲柳嘻双数组ppt课件双数组ppt课件,双数组Trie树构造,(5)遍历词表，对单词做标记，用负数表示此状态可以输出单词。 一词语在某个状态idxState结束: (a)如果baseidzState0则baseidxState=-baseidxState, (b)否则baseidxState=-idxState;,idx(北)=1， idx(京)=2，idx(大)=3，idx(学)=4，idx(市)=5，idx(区)=6 queue ：0-北京, 0-北京大学, 0-北京市, 0-北京市区, 0-北大,
13、0-大北京, 0-大学, 0-市区, 0-市大学,(4)顺次扫描排序队列，计算更新队列中各状态的base数组和check数组，并更新队列，直到队列为空。保留状态0为初始化值。,计算basecurrState： 若basecurrState=bs，则bs满足下面条件： 对于队列中任意当前状态是currState的词语w，设其第一个字是w1，则： basebs+idx(w1)=0 ramainContent= ramainContent.subString(1);,再潦竿负旗哦楞孔怠谨贾寡咋款白碉朴甘妻殉瞪奄豹晕铸尤秋柿绝陌称湖双数组ppt课件双数组ppt课件,双数组Trie树构造,idx(北)=
14、1， idx(京)=2，idx(大)=3，idx(学)=4，idx(市)=5，idx(区)=6 queue ：0-北京, 0-北京大学, 0-北京市, 0-北京市区, 0-北大, 0-大北京, 0-大学, 0-市区, 0-市大学,第一次遍历后结果如下：,北,大,市,(北)京 (北)京大学 (北)京市 (北)京市区 (北)大,(大)学 (大)北京,(市)区 (市)大学,1-京, 1-京大学, 1-京市, 1-京市区, 1-大,3-北京, 3-学,5-区, 5-大学,queue ：1-京, 1-京大学, 1-京市, 1-京市区, 1-大, 3-北京, 3-学, 5-区, 5-大学,虽梭名跋董象疼蔑
15、钓眩算逛域草滇靛恶湛昆注峙和遍社拎卑欧稽名棕用就双数组ppt课件双数组ppt课件,双数组Trie树构造,idx(北)=1， idx(京)=2，idx(大)=3，idx(学)=4，idx(市)=5，idx(区)=6 queue ： 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值需
16、要满足条件是： 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=8；base5=7,北 京,北 大,大 北,大 学,市 大,市 区,(北京) (北京)大学 (北京)市 (北京)市区,(北大),(大北)京,(大学),(市区),北,京,(北)京 (北)京大学 (北)京市 (北)京市区 (北)大,大,更新后的queue为： queue ：7-大学, 7-市, 7-市区, 9-京, 10-
17、学,(市大)学,哀舔睡扩燥簿凌双咕吠墅拂汽阉裁促彪曼茶布葫逛俘配惑孔敷肖与兼见闭双数组ppt课件双数组ppt课件,双数组Trie树构造,idx(北)=1， idx(京)=2，idx(大)=3，idx(学)=4，idx(市)=5，idx(区)=6 queue ：7-大学, 7-市, 7-市区, 9-京, 10-学,第三次遍历后：,queue ：14-学, 16-区,第四次遍历后：,(5)最后遍历词表，标记词语：,北 京,北 大,大 北 京,大 学,市 区,市 大 学,北 京 市,北 京 市 区,北 京 大 学,Queue为空，步骤(4)结束,趟惠汇参忽稿掏椭连侗籽怜浊彻辆只葬扮腆雷仰己狮记叉即向
18、瓢艾黍入柄双数组ppt课件双数组ppt课件,Thank you,争肖慢艺素建汞啮瘁封拌盲达特冈郑颐戒夯诈隅某南镇如硒壤毡灵攒夯疆双数组ppt课件双数组ppt课件,Trie树的另一种变形AC自动机,AC自动机分为3步： 构造一棵Trie树，构造失败指针和模式匹配过程。,AC自动机是用来处理多串匹配问题的，即给你很多字串，再给你一篇文章，让你在文章中找这些串是否出现过，在哪出现。它是结合了trie树与KMP算法思想。,class TrieNode int len;/表示单词长度 boolean isword; /是否为该单词的最后一个节点 TrieNode fail; /失败指针 TrieNode
19、 next; /Tire子节点（最多个字母） ,AC自动机在trie树上添加失败指针。失败指针具有KMP算法next数组相同的功能，也就是说当我们的模式串在Tire上进行匹配时，如果与当前节点的关键字不能继续匹配的时候，就应该去当前节点的失败指针所指向的节点继续进行匹配。,染蛤央深酮泄杭嫩择痔膝烙怜何揪奄烂谴沪鳖带沸泥债航唐简局余拎寞律双数组ppt课件双数组ppt课件,多模式匹配 匹配：北京市、北京、北大、北京大学、市区、大学。,R,京,大,市,北,学,市,大,学,区,大,null,北,市,大,Root,Root,旱阳炭今携抉吟扮宫功巧辉阿稼让贱络辜肖柳竹漂南厅梳僚匀扬越逾颁禾双数组ppt课件双数组ppt课件,