【数据结构】跳跃列表 SkipList
SkipList超高性能的数据库redis和levelDB都用到了这种神奇的数据结构:SkipList(跳跃表)。之所以说它神奇，是因为跳跃表是基于一个随机数的。跳跃表是在有序链表的基础上进行了扩展，解决了有序链表结构查找特定值困难的问题(O(logn))，是一种可以替代平衡二叉树的数据结构(查询的时间二者基本相同，但是插入的时间跳跃表优于平衡二叉树)。 相比于各种平衡二叉树，跳跃表的实现比较简单。 有序表的搜索 怎么优化？链表当然不能二分查找，但可以把一些节点提取出来作为索引，得到下面的结构 我们可以看出，这是一种类似树状数组思想的分层链表结构。 跳跃列表下面的结构就是跳表 跳表具有下面的性质 跳表的搜索从最高层开始找，如果发现下一个元素小于搜索值，那么继续往本层的后一个找。如果发现下一个元素大于搜索值，那么就往当前的下一层找。如果等于 = = 正好。 代码 /*如果存在x 返回x所在的节点 *否则返回x的后继节点*/
find(x)
{
p = top;
while(true) {
while(p->next->key < x) p = p->next;
if(p->down == NULL) return p->next;
p = p->down;
}
}
跳表的插入先确定该元素要占据的层数K(这是一个随机数) 比如K(119) = 2的情况 比如插入119，K=4 “丢硬币”决定K插入元素的时候，元素所占有的层数完全是随机的，通过以下的随机算法产生： int random_level()
{
k = 1;
while(random(0,1)) k ++;
return k;
}
相当于做一次丢硬币的实验，如果正面则继续丢，遇到反面则停止。 跳表的高度n个元素的跳表，每个元素插入的时候都要做一次实验，用来决定元素占据的层数K. 跳表的高度等于这N次实验中产生的最大K。 跳表的空间复杂度每个元素的期望高度为2，一个大小为n的跳表，其节点数目的期望值是2n 跳表的删除在每个层中找到包含x的节点，使用标准的delete form list方法删除该节点 比如，删除 71 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |