跳表
redis跳表skiplist参考： 参考链接
1206. 设计跳表
通过这张图，可以先确定跳表中每个节点的数据结构：
class Node{
Integer value; //节点值
Node[] next; // 节点在不同层的下一个节点
public Node(Integer value,int size) { // 用size表示当前节点在跳表中索引几层
this.value = value;
this.next = new Node[size];
}
}
知道了层数，这下就好办了。思路如下：
- 先随机出来一个层数，new要插入的节点，先叫做插入节点newNode；
- 根据跳表实际的总层数从上往下分析，要插入一个节点newNode时，先找到节点在该层的位置：因为是链表，所以需要一个节点node，满足插入插入节点newNode的值刚好不大于node的下一个节点值，当然，如果node的下个节点为空，那么也是满足的。
我们先把找节点在某一层位置的方法封装起来：
/**
* 找到level层 value 刚好不小于node 的节点
* @param node 从哪个节点开始找
* @param levelIndex 所在层
* @param value 要插入的节点值
* @return
*/
private Node findClosest(Node node,int levelIndex,int value){
while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){
node = node.next[levelIndex];
}
return node;
}
- 确定插入节点newNode在该层的位置后，先判断下newNode的随机层数是否小于当前跳表的总层数，如果是，则用链表的插入方法将newNode插入即可。
- 如此循环，直到最底层插入newNode完毕。
- 循环完毕后，还需要判断下newNode随机出来的层数是否比跳表的实际层数还要大，如果是，直接将超过实际层数的跳表的头节点指向newNode即可，该跳表的实际层数也就变为newNode的随机层数了。
以上就是插入的算法。
理解了插入算法后，查找跟删除就简单多了。
不管是插入、查找还是删除，均是从跳表上层往下层分析，复用上面的findClosest方法，找到要查询的值 在该层closest的节点。比如查询，只需要判断findClosest出来的节点值是否等于该查询值即可，是就返回，不是则继续往下层判断。删除方法思想也是一致的。
import random
class Node:
def __init__(self, value, size):
# 节点值
self.value = value
# 节点在不同层的下一个节点. 用size表示当前节点在跳表中索引几层
self.next = [None for i in range(size)]
class Skiplist:
# 插入:1. 先随机出来一个层数，new要插入的节点，先叫做插入节点newNode；2. 根据跳表实际的总层数从上往下分析，要插入一个节点newNode时，先找到节点在该层的位置：因为是链表，所以需要一个节点node，满足插入插入节点newNode的值刚好不大于node的下一个节点值，当然，如果node的下个节点为空，那么也是满足的。3. 确定插入节点newNode在该层的位置后，先判断下newNode的随机层数是否小于当前跳表的总层数，如果是，则用链表的插入方法将newNode插入即可。4. 如此循环，直到最底层插入newNode完毕。5. 循环完毕后，还需要判断下newNode随机出来的层数是否比跳表的实际层数还要大，如果是，直接将超过实际层数的跳表的头节点指向newNode即可，该跳表的实际层数也就变为newNode的随机层数了。不管是插入、查找还是删除，均是从跳表上层往下层分析，复用上面的findClosest方法，找到要查询的值 在该层closest的节点。查询:只需要判断findClosest出来的节点值是否等于该查询值即可，是就返回，不是则继续往下层判断。
def __init__(self):
self.default_max_level = 32
self.default_p_factor = 0.25
# 哨兵头节点
self.head = Node(None, self.default_max_level)
# 表示当前nodes的实际层数，它从1开始
self.current_level = 1
# 找到level层 value 大于node 的节点
def __find_closest(self, node, level_index, value):
while node.next[level_index] is not None and value > node.next[level_index].value:
node = node.next[level_index]
return node
def __random_level(self):
level = 1
while random.random() < self.default_p_factor and level < self.default_max_level:
level += 1
return level
def search(self, target: int) -> bool:
search_node = self.head
for i in range(self.current_level - 1, -1, -1):
search_node = self.__find_closest(search_node, i, target)
if search_node.next[i] is not None and search_node.next[i].value == target:
return True
return False
def add(self, num: int) -> None:
level = self.__random_level()
update_node = self.head
new_node = Node(num, level)
# 计算出当前num 索引的实际层数，从该层开始添加索引
for i in range(self.current_level - 1, -1, -1):
# 找到本层最近离num最近的list
update_node = self.__find_closest(update_node, i, num)
if i < level:
if update_node.next[i] is None:
update_node.next[i] = new_node
else:
temp = update_node.next[i]
update_node.next[i] = new_node
new_node.next[i] = temp
# 如果随机出来的层数比当前的层数还大，那么超过currentLevel的head 直接指向newNode
if level > self.current_level:
for i in range(self.current_level, level):
self.head.next[i] = new_node
self.current_level = level
def erase(self, num: int) -> bool:
# 由于我们的实现是在一个跳表中只有一个节点拥有num的值，通过next数组模拟在不同层数，因此需要遍历所有层数删除节点。
deleted = False
search_node = self.head
for i in range(self.current_level - 1, -1, -1):
search_node = self.__find_closest(search_node, i, num)
if search_node.next[i] is not None and search_node.next[i].value == num:
# 删除当前层中的模拟节点。删除方法与删除一个普通链表的节点相同。
search_node.next[i] = search_node.next[i].next[i]
deleted = True
continue
return deleted