SkipList跳表(一)基本原理
一直听说跳表这个数据结构,说要学一下的,懒癌犯了,是该治治了
为什么选择跳表
目前经常使用的平衡数据结构有:B树、红黑树,AVL树,Splay Tree(这个树好像还没有听说过),Treep(也没有听说过)等。
想象一下,给你一张草稿纸,一支笔,一个编辑器,你能立即实现一颗红黑树,或者AVL树出来吗?
不好意思,我tmd连冒泡都实现不了......
很难吧,这需要时间,需要考虑很多细节,需要参考一堆算法与数据结构之类的书,还需要参考网上的代码,比较麻烦
用跳表吧,跳表是一种随机化的数据结构,目前开源软件Redis和LevelDB(这是个啥)都有用到它。
他的效率和红黑树不相上下,但跳表的原理相当简单,只要你能熟练操作链表,就能轻松实现一个SkipList。
有序表的搜索
考虑一个有序表
从该表中搜索元素<23,43,59>,需要比较的次数分别为<2,4,6>,总共比较的次数为
2+4+6=12次。有没有优化的算法么?链表是有序的,但不能使用二分查找。
类似二叉搜索树,我们可以把一些节点提取出来,作为索引。得到如下结构:
这里我们把<14,34,50,72>提取出来作为一级索引,这样搜索的时候就可以减少比较次数了。
我们还可以再从一级索引中提取一些元素出来,作为二级索引,变成如下结构:
这里元素不多体现不出优势来,如果元素足够多,这种索引结构就能体现出优势来了。
跳表
下面的结构就是跳表:
其中-1表示INT_MIN,链表的最小值,1表示INT_MAX,链表的最大值。
跳表具有如下性质:
1. 由很多层结构组成
2. 每一层都是一个有序的链表
3. 最底层(Level 1)的链表包含了所有元素
4. 如果一个元素出现在Level i的链表中,则它在Level i之下的链表也都会出现
5. 每个节点包含了2个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素
跳表的搜索
图中搜索117的过程用红色线画出来的,从上到下已经很明显了,在此不赘述
具体的搜索算法如下:
/* 如果存在x,返回x所在的节点,否则返回x的后继节点 */
find(x) {
p = top;
while (l) {
while (p->next->key < x)
p = p->next;
if (p->down == NULL)
return p->next;
p = p->down;
}
}
跳表的插入
先确定该元素要占据的层数K(采用丢硬币的方式,这完全是随机的)
然后再Level 1 ...... Level K各个层的链表都插入元素
例如,插入119,K=2
如果K大于链表的层数,则要添加新的层。
例如,插入119,K=4
丢硬币决定K
插入元素的时候,元素所占据的层数完全是随机的,通过以下随机算法:
int random_level() {
K = 1;
while (random(0, 1))
K++;
return K;
}
相当于做了一次丢硬币的实验,如果遇到正面,继续丢,遇到反面则停止,】
用实验中丢硬币的次数K作为元素占有的层数。显然随机变量K满足p=1/2的几何分布,K的期望值是E[K] = 1/p = 2。
也就是说,各个元素的层数,期望值是2层。
跳表的高度
n个元素的跳表,每个元素插入的时候都要做一次实验,用来决定元素占据的层数K,跳表的高度等于这n次实验中产生的最大K。
跳表的空间复杂度分析
根据上面的分析,每个元素的期望高度是2,一个大小为n的跳表,其节点数目的期望是2n。
跳表的删除
在各个层中找到包含x的节点,使用标准的delete from list方法删除。
最新文章
- 多重共线性的解决方法之——岭回归与LASSO
- 【整理】--【字符设备】cdev_init()/cdev_alloc(),cdev_add(),cdev_del()
- HOLOLENS的空间管理
- 根据html容器大小和显示文字多少调节字体大小
- leetcode 100 Same Tree ----- java
- Working with Sprites
- 15个必知的Android开发者选项
- HDU3362+状态压缩
- PHP使用IP地址连接MySQL数据库
- 1. mybatis批量插入数据
- java基础之String
- SQL Server 日志截断
- [每日一题] OCP1z0-047 :2013-07-26 alter table set unused之后各种情况处理
- 【第四篇】Volley修改之GsonRequest
- myeclipse eclipse创建maven web项目时 index.jsp报错
- Tools:实现vmware虚拟机开机自启动
- hbase 实战项目
- 屏幕适配(UGUI)非UI
- vuex-state
- 锚接口(下)——html5的history api
热门文章
- c#使用Split分割字符串的几种方法
- 存储过程中set什么什么的讲解
- js,add script async? loaded ok.
- 《Linux命令行与shell脚本编程大全 第3版》Linux命令行---37
- 处理printf的变参问题
- poj 2100(尺取法)
- Educational Codeforces Round 34 C. Boxes Packing【模拟/STL-map/俄罗斯套娃】
- 聚类kmeans算法在yolov3中的应用
- cdq分治解决区间问题
- .Net 多线程小结