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

《算法合集之《线段跳表——跳表的一个拓展》.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线段跳表——跳表的一个拓展2009年冬令营论文李骥扬线段跳表——跳表1的一个拓展石家庄二中李骥扬摘要本文主要介绍我对跳表(跳跃表,SkipLists,SL,1987年由WilliamPugh发明)的一个拓展：线段跳表(SegmentSkipLists,SSL)以及相关的效率证明。并简要分析跳表及其拓展在信息学竞赛中的优势。关键词跳表平衡树线段跳表线段树引言在信息学竞赛中，数据结构是重要的一部分。通常考察我们维护、处理数据的能力。这类题目常常要求我们维护一个线性有序的结构，并对其进行插入查询等操作，常用的实现方式有平衡树、块状链表、树状数组等。跳表是一种新型数据结构，支持有序表的插入、删除

2、、查找等字典操作。跳表基于随机化和概率，插入、删除、查找操作的期望时间复杂度均为O(logN)。同时由于其线性表的本质，具有编写简单，易于拓展的性质。它能代替平衡树实现字典操作。且由于其结构简单，不需要旋转操作，跳表支持将各部分存放在不同介质上，进行并行操作2。但是基本的跳表只支持插入、删除、查找的字典操作，并不支持区间操作。跳表的能力绝不限于此，只要更深入地分析一下跳表的结构，我们就能从跳表中得到一棵二叉树的结构。进而添加区间信息，得到线段树。本文将通过对插入、删除操作的升级，使得这些操作能够维护区间信息。拓展后的跳表，称为线段跳表，能够完全替代各类平衡树，支持字典操作和区间操作。同时

3、保持了其原有特点，简单易用，还支持顺序操作等特殊操作。线段跳表将成为信息学竞赛中的理想数据结构。1本文讨论跳表的范围仅限于基于期望的随机跳表(SkipLists，SL)，不涉及确定性跳表（1-2-3DeterministicSkipList，1-2-3DSL)的内容。2相关内容参见WilliamPugh的《CONCURRENTMAINTENANCEOFSKIPLISTS》-1-线段跳表——跳表的一个拓展2009年冬令营论文李骥扬第一部分跳表简介�从链表到跳表链表作为一种常用而灵活的数据结构，常常用于维护线性数据。链表可以方便的执行插入删除操作，但是从链表中查找一个数的代价可能很大(时间复

4、杂度O(N))。相反，维护一个有序数组可以使用二分方便地在O(logN)的时间内进行查找，但若要维护数组的有序性，插入和删除的复杂度又会很大(时间复杂度O(N))。如果能维护一个有序链表且支持二分，我们就可以在O(logN)的时间内完成一组规模为n的数据的插入、查找、删除操作(字典操作)。让我们首先考虑一个静态链表的查询。一个简单的想法就是在链表中给一些节点增加一个指针（加速指针），使得我们能够在适当的时候跳过一些结点，从而达到加速查找的目的。（如下图）[figure1.1]带加速指针的链表然而如果我们限制对于一个结点只连出一个加速指针，使用类似块状链表的结构，我们能达到的最优的复杂度为

5、O(n)。能不能得到更好的结果呢？我们放宽每个节点有一个加速指针的限制，基于与静态数组的二分搜索的类比，我们能够得到如下结构：[figure1.2]空想跳表-2-线段跳表——跳表的一个拓展2009年冬令营论文李骥扬每个节点连出的加速指针指向该节点在二分过程中可能作为左端点的区间中点。这一结构可以在O(logN)的时间内实现对数据的搜索，搜索过程即二分，每次通过加速指针找到当前区间的中间节点，比较后确定更精确的区间继续二分。但是当我们面对动态数据的时候，这一结构在插入删除过程中显然无法以较小代价进行维护。随机化经常被用来降低算法的时间复杂度。在以上思路中增加随机化思想，我们便得到了跳表：跳

6、表由Lev层链表以及下行指针构成，插入数据v时随机化得出高度h，然后向第1层至第h层插入索引值为v的节点，对于第2层至第h层的节点插入下行指针，指向第一层具有相同索引值的节点。这h个节点构成一个高度为h的块(Block)。如下图所示：[figure1.3]跳表具有这样结构的跳表查找的期望时间复杂度为O(logN)，参见第三部分。�形式化地给出跳表结构跳表由多条链表（L,L……L）以及下行指针构成，满足以下条件12maxlev1>L为一条链表，自左至右单调递增，包含两个特殊元素−∞(起始节点)和i+∞(终止节点)2>L包含所有元素，L(i≥2)包含部分元素，且1i对∀x∈L有x∈L

7、∀1≤

8、j对于L(i≥2)中的任意节点，有一个下行指针，指向L中具有相同索引ii−1值的节点。同时给出一些下文使用到的术语的解释：横向边：即各层链表中的指针。纵向边：即下行指针。块：只考虑纵向边时的一个连通分支，其包含的节点数成为其高度。前驱节点、后继节点：即某一节点在所在跳表中的前驱节点和后继节点。底层节