跳表

跳表定义

在原有的有序链表上增加了多级索引，通过索引来实现类似二分查找的快速查找。

• 和红黑树的对比：

---

跳表的建立

• 若存在有序链表：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

建立第一层：

• 将上面的有序链表放到最下层，和原来的一模一样

  
  

建立第二层：

• 从左到右，依次数，数到1。抛一枚硬币，假设得到正面。那么1上去一层。
  
• 从左到右，依次数，数到2。抛一枚硬币，假设得到正面。那么2上去一层。
  
• 从左到右，依次数，数到3。抛一枚硬币，假设得到反面。那么3不能上去一层。
• 从左到右，依次数，数到4。抛一枚硬币，假设得到反面。那么4不能上去一层。
• 从左到右，依次数，数到5。抛一枚硬币，假设得到正面。那么5上去一层。
  
• 从左到右，依次数，数到6。抛一枚硬币，假设得到正面。那么6上去一层。
  
• 从左到右，依次数，数到7。抛一枚硬币，假设得到反面。那么7不能上去一层。
• 从左到右，依次数，数到8。抛一枚硬币，假设得到正面。那么8上去一层。
  
• 从左到右，依次数，数到9。抛一枚硬币，假设得到反面。那么9不能上去一层。
• 从左到右，依次数，数到10。抛一枚硬币，假设得到正面。那么10上去一层。
  

建立第三层：

• 从左到右，依次数第二层，数到1。抛一枚硬币，假设得到反面。那么1不能上去一层。
• 从左到右，依次数第二层，数到2。抛一枚硬币，假设得到正面。那么2上去一层。
  
• 从左到右，依次数第二层，数到5。抛一枚硬币，假设得到正面。那么5上去一层。
  
• 从左到右，依次数第二层，数到6。抛一枚硬币，假设得到反面。那么6不能上去一层。
• 从左到右，依次数第二层，数到8。抛一枚硬币，假设得到正面。那么8上去一层。
  
• 从左到右，依次数第二层，数到10。抛一枚硬币，假设得到反面。那么10不能上去一层。
  

建立第四层：

• 从左到右，依次数第三层，数到2。抛一枚硬币，假设得到正面。那么2上去一层。
  
• 从左到右，依次数第三层，数到5。抛一枚硬币，假设得到反面。那么5不能上去一层。
• 从左到右，依次数第三层，数到8。抛一枚硬币，假设得到正面。那么8上去一层。
  

建立第五层：

---

跳表的查找(前面没有了，或者目标比节点小，则跳到下一层)

假设查找6

• 第五层开始：发现6>2，继续往前比较，发现 前面没有了，则跳到第四层
• 到第四层发现： 6< 8,则跳到第三层，
• 到第三层发现：由于6>5,继续往前比较，由于 6<8,则跳到第二层
• 到第二层发现：由于6=6(由于竖排节点都指向同一个内存地址)，查找结束

---

跳表的插入 (首先通过上面的查找方式，查找插入位置。然后抛最多高度次硬币，抛到反面则停止，正面则继续增长)

假设插入5.5

• 第五层开始：发现5.5>2，继续往前比较，发现 前面没有了，则跳到第四层
• 到第四层发现： 5.5< 8,则跳到第三层，
• 到第三层发现：由于5.5>5,继续往前比较，由于 5.5<8*,则跳到第二层
• 到第二层发现：由于5.5<6，,则跳到第二层

• 到第一层发现：5.5>5且5.5<6,则在5和6之间插入5.5

  
  
• 抛一枚硬币，假设得到正面。那么5.5上去一层。
  
• 由于采用不限制最度，再抛一枚硬币，假设得到反面。那么5.5不能上去一层。插入结束。

PS:本来想多抛几次硬币，不小心把图删掉了。所以就直接抛到反面了...

---

跳表的更新

---

跳表的删除

假设删除5

• 根据跳表的查找，查找到要删除的节点5存在。

---

跳表的代码实现

抛硬币的随机函数

After(P)：返回和P在同一层的后继节点，不存在返回Null

Before(P)：返回和P在同一层的前驱节点，不存在返回Null

Below(P)：返回P下一层的节点，不存在返回Null

Above(P)：返回P上一层的节点，不存在返回Null

插入

更新

查找

def 跳表查找(被查找节点):
  

删除：

def 跳表删除(被删除节点):
  被删除节点位置=跳表查找(被删除节点)
  if 被删除节点位置==None: #不存在该节点，直接返回
    return
  while 被删除节点位置!=None:
    被删除节点前一个节点=根据位置获取前一个节点(被删除节点位置)
    被删除节点后一个节点=根据位置获取后一个节点(被删除节点位置)
    将前一个节点指向后一个节点=修改节点位置(被删除节点前一个节点,被删除节点后一个节点)
    临时存储节点 =  被删除节点位置
    被删除节点位置=根据位置获取上一个节点(被删除节点位置) # 注意这句,将删除的节点放到了 临时存储节点 ，然后在重新赋值 被删除节点位置
    删除节点(临时存储节点)
  #要是有某一层只有被删除的那个节点，则清除该层，并且跳表高度减一。
  下一个判断位置=下面一个元素(跳表头节点)
  if 下一个判断位置!=None&&Key(根据位置获取后一个节点(下一个判断位置))== 正无穷:
    将被删除的负无穷节点=起始判断位置
    将被删除的正无穷节点=根据位置获取后一个节点(起始判断位置)
    下一个判断位置=下面一个元素(下一个判断位置)
    跳表高度-=1
    删除节点(将被删除的负无穷节点,将被删除的正无穷节点)