跳跃表Skip List的原理和实现

  1. 云栖社区>
  2. 博客>
  3. 正文

跳跃表Skip List的原理和实现

邴越 2016-05-05 15:55:10 浏览6419
展开阅读全文

二分查找和AVL树查找

二分查找要求元素可以随机访问,所以决定了需要把元素存储在连续内存。这样查找确实很快,但是插入和删除元素的时候,为了保证元素的有序性,就需要大量的移动元素了。
如果需要的是一个能够进行二分查找,又能快速添加和删除元素的数据结构,首先就是二叉查找树,二叉查找树在最坏情况下可能变成一个链表,
于是就出现了平衡二叉树,根据平衡的算法不同有AVL树,B-Tree,B+Tree,红黑树等,但是AVL树实现起来比较复杂,
平衡操作较难理解,这时候就可以用SkipList跳跃表结构。


什么是跳跃表

Skip list(跳表)是一种可以代替平衡树的数据结构,默认是按照Key值升序的。Skip list让已排序的数据分布在多层链表中,以0-1随机数决定一个数据的向上攀升与否,通过“空间来换取时间”的一个算法,在每个节点中增加了向前的











网友评论

登录后评论
0/500
评论
邴越
+ 关注