y~e
最编程
2024-04-13 08:05:11
...
一：什么是跳表
跳表（Skip List）是由 William Pugh 发明的一种动态数据结构，支持对数据的快速查找，插入和删除。并且跳表的各方面性能都十分优秀，甚至可以媲美红黑树。
跳表本身是对有序链表的改进，首先让我们一起回顾一下链表这种数据结构：
[图片]
上图是一个有序链表，在链表中的查找，插入以及删除操作的时间复杂度均为$O(N)$。
跳表设计的理念就是为了提升链表增删改查的效率，如何提升效率呢？我们可以在有序链表的基础上，引入“索引”的概念，即：每两个节点提取一个节点到上一级，我们将抽出来的那一级叫做索引层：
[图片]
如果我们现在要查找某个节点，比如“16”，我们可以先在索引层遍历，当遍历到索引层“13”这个节点时，我们发现下一个节点是“17”，那么要查找的节点“16”肯定就在这两个节点之间。我们通过索引层节点的“down”指针下降到原始链表这一层继续遍历，现在，我们只需要...... 查看更多
推荐阅读
-
指数族分布简介 / 求指数族分布的 E(a(Y)) 和 D(a(Y))
-
y~e
-
大家口中所说的A站、B站、C站、D站、E站、F站、G站、H站、I站、J站、K站、L站、M站、N站、O站、P站、Q站、R站、S站、T站、U站、V站、W站、X站、Y站、Z站都是什么网站？
-
大家口中所说的A站、B站、C站、D站、E站、F站、G站、H站、I站、J站、K站、L站、M站、N站、O站、P站、Q站、R站、S站、T站、U站、V站、W站、X站、Y站、Z站都是什么网站？
-
A站、B站、C站、D站、E站、F站、G站、H站、I站、J站、K站、L站、M站、N站、O站、P站、Q站、R站、S站、T站、U站、V站、W站、X站、Y站、Z站都是什么网站？Q站是什么？
-
大家口中所说的A站、B站、C站、D站、E站、F站、G站、H站、I站、J站、K站、L站、M站、N站、O站、P站、Q站、R站、S站、T站、U站、V站、W站、X站、Y站、Z站都是什么网站？
-
01 条件期望与条件方差-1.3迭代期望定律 该定律研究的是E(E(X|Y))是什么 image