文章目录
  1. 跳跃表

跳跃表

考虑一组数据用一条链表组织，那么在查询数据的复杂度为O(N)；为此，考虑每隔一个节点加一个指针连接。

 

将这种想法扩展，考虑每个$2^{k}$的节点都加一个指针指向下一个$2^{k}$节点，总指针数仅仅加倍。

 

但是，这种结构又导致插入过程过于复杂，考虑稍微放松一下限制条件，即不严格要求每个$2^{k}$的节点都指向下一个$2^{k}$节点，而是以$P\{NumofVec=k\}=1/2^{k}$的概率来随机决定一个插入的节点应有的指针数。这就是跳跃表。

 

那么对应跳跃表的查找、插入、删除操作如下。

  • 从头节点的最高阶指针开始，沿该阶前进直到该阶的下一节点的值大于要查找的值，保存该阶上查找所到的最后的节点，然后来到下一阶继续上述过程直到在最低阶停下来，此时或者当前节点的值就是要查找的值；或者当前节点的值小于要查找的值，则进入下面的插入过程；
  • 随机决定此插入节点的指针数；从最低阶开始，将保存的该阶上查找所到的最后的节点指向插入节点，然后来到上一阶继续上述过程直到最高阶；
  • 删除，其实就是多次的链表删除操作；