算法合集之《线段跳表-跳表的一个拓展》.ppt

线段跳表 跳表的一个拓展 河北省石家庄二中 李骥扬 内容梗概 跳表 跳表的结构 跳表的字典操作 线段跳表 跳表中的隐式线段树 两类区间信息的维护 优势与效率分析 (ppt中略去 ) 跳表 跳表的结构 跳表的字典操作 跳表的结构 跳表由多条链表 L1 LN以及下行指针构成 每条链表包含元素检索值单调递增，包含两个 特殊节点 -(起始节点 )和 +(终止节点 ) L1包含所有元素，对任意的 i0， Li+1是 Li的 子集，且 Li+1中的每一个节点，有一个下行指 针，指向 Li中与之有相同索引值的节点。 跳表的字典操作 查找 (以查找检索值为 8的节点为例 ) 跳表的字典操作 插入 v=8 先随机化得出插入的节点的高度 h h=1 h=h+1 输出 h p的几率 (1-p)的几率 得到 h=2 跳表的字典操作 插入 v=8 插入前搜索 v，设尝试过但没有走的边为 红色 然后向跳表的 1至 h=2层红色边插入检索值 为 v的节点 Path(v) 跳表的字典操作 删除 v=8 类似插入，先查找 v，标记检索值为 v的节 点为红色 删除红色节点，维护跳表结构 线段跳表 跳表中的隐式线段树 两类区间信息的维护 跳表中的隐式线段树 跳表中的隐式线段树 进一步，将每个节点 v的查找路径 上节点都标记上 v。即可得到： 跳表中的隐式线段树 再进一步，将标记值换成一个左闭右开 的区间。再在第一层之下加入第零层。 向第一层节点添加下行指针。 跳表中的隐式线段树 我将这样包含区间信息的跳表称为 线段跳表 区间的左边界为该节点的索引值。 而区间的右边界可以叙述如下： 设搜索该节点过程中最后一次经历的纵向边为 u-v，则该节点右边界为 u的后继节点的索引值。 该值不需额外存储，每次搜索过程中即可动态获 得。 两类区间信息的维护 DP 信息 (DPi)： 树形 DP时存储的某一区间的信息。 e.g. 区间内的点的个数、最大值最小值等。 特征是每一个节点都保存此信息，而这个信息是由 区间的孩子 (子区间 )得出的。 线段信息 (SEGi)： 线段树中存储的信息。 e.g. 区间的染色情况等等。 特征是并非所有的节点都需要保存此信息。添加信 息时，选择尽量高的节点进行操作 (染色等 )。 两类区间信息的维护 插入 两类区间信息的维护 插入 4,5.5) Path(v) Path(v-) 两类区间信息的维护 插入 1.沿 Path(v)下分 SEGi信息，并通过此过程，得出 v节点的 SEGi信息。 2.插入检索值为 v的块，并且设置底层节点的 SEGi 值为之前求出的 SEGi值。 3.沿 Rev-Path(v)顺序更新路径上各节点的 DPi信 息。 4.沿 Rev-Path(v- )顺序更新路径上各节点的 DPi 信息。 两类区间信息的维护 删除 1.清理被覆盖的 SEGi信息。 2.判断要删除的节点是否为当前某一覆 盖范围的端点。 3.删除检索值为 v 的各个节点。 4.沿 Rev-Path(v)更新 DPi信息。 线段跳表，通过随机化得到一个相对平衡的结 构，支持线段树与平衡树能够实现的功能。相 比线段树，具有能够动态处理信息，支持在线 询问的特点；相比平衡树，具有编写简便、代 码精简的特点。 当跳表进化为了线段跳表，它能够处理 的信息也更加多样。跳表及其拓展，将 在众多领域发挥更大的作用。 总结 谢谢大家 欢迎提问