网站设计制作程序,青云 wordpress加速,友情链接发布平台,单页网页制作视频教程为什么选择跳表 目前经常使用的平衡数据结构有#xff1a;B树#xff0c;红黑树#xff0c;AVL树#xff0c;Splay Tree, Treep等。 想象一下#xff0c;给你一张草稿纸#xff0c;一只笔#xff0c;一个编辑器#xff0c;你能立即实现一颗红黑树#xff0c;或者AVL树…为什么选择跳表 目前经常使用的平衡数据结构有B树红黑树AVL树Splay Tree, Treep等。 想象一下给你一张草稿纸一只笔一个编辑器你能立即实现一颗红黑树或者AVL树 出来吗 很难吧这需要时间要考虑很多细节要参考一堆算法与数据结构之类的树 还要参考网上的代码相当麻烦。 用跳表吧跳表是一种随机化的数据结构目前开源软件 Redis 和 LevelDB 都有用到它 它的效率和红黑树以及 AVL 树不相上下但跳表的原理相当简单只要你能熟练操作链表 就能轻松实现一个 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) 每个节点包含两个指针一个指向同一链表中的下一个元素一个指向下面一层的元素。 跳表的搜索 例子查找元素 117 (1) 比较 21 比 21 大往后面找 (2) 比较 37, 比 37大比链表最大值小从 37 的下面一层开始找 (3) 比较 71, 比 71 大比链表最大值小从 71 的下面一层开始找 (4) 比较 85 比 85 大从后面找 (5) 比较 117 等于 117 找到了节点。 具体的搜索算法如下 C代码 /* 如果存在 x, 返回 x 所在的节点 * 否则返回 x 的后继节点 */ find(x) { p top; while (1) { 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 插入元素的时候元素所占有的层数完全是随机的通过一下随机算法产生 C代码 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 方法删除该节点。 例子删除 71 转载于:https://www.cnblogs.com/papobabe/p/5885808.html
