[数据结构]Python实现跳表skipList

Author： Mkdir700
发布时间：August 25, 2020
427views
No comments
4216 words
Categories：面试考点

## [数据结构] 跳表(skipList) Python实现

[漫画： 什么是“跳表”？](http://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653211187&idx=1&sn=c062ab9598cf0af12acbf849478bb0d3&chksm=8c99b8e9bbee31ff9b1c86cfb32030b4cbabc0b98e9be850efe46fffb6eb6bac335f8b2b7b43&mpshare=1&scene=23&srcid=0825XUNJkU280Ru3Dbkw7v3w&sharer_sharetime=1598339631027&sharer_shareid=00bca55feaecb55710fa0a163922966c#rd)

Python实现：

<pre mdtype="fences" cid="n7" lang="python" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false"> import random      MAX_VALUE = float('inf')  MIN_VALUE = float('-inf')      class Node(object):      """     链表节点     """      def __init__(self, val):          self.left = self.right = self.up = self.down = None          self.val = val      class SkipList(object):        promote_rate = 0.5      max_level = 0      head, tail = Node(MIN_VALUE), Node(MAX_VALUE)        def __init__(self):          self.head.right = self.tail          self.tail.left = self.head        def find_node(self, data) -> Node:          """         找到值对应的前置节点         :param data:         :return: 返回前置节点         """          node: Node = self.head          while True:              while node.right.val != MAX_VALUE and node.right.val <= data:                  node = node.right              # 在水平方向已找到前置节点              if node.down is None:                  break              node = node.down          return node        def search(self, val) -> (Node, None):          """         查找节点         :return: None         """          p = self.find_node(val)          if p.val == val:              print("找到节点： ", val)              return p          print("未找到节点： ", val)          return None        def insert(self, val):          """         插入节点         :param val: 节点值域         :return:         """          pre_node: Node = self.find_node(val)          # 如果值相同，直接返回          if pre_node.val == val:              return            node: Node = Node(val)          self.append_node(pre_node, node)          current_level: int = 0          while random.uniform(0, 1) < self.promote_rate:              # 如果当前层已是最高层，需要增加一层              if current_level == self.max_level:                  self.add_level()              # 找到上一层的前置节点              while pre_node.up is None:                  pre_node = pre_node.left              pre_node = pre_node.up              # 把新节点插入到上一层              upper_node = Node(val)              self.append_node(pre_node, upper_node)              upper_node.down = node              node.up = upper_node              node = upper_node              current_level += 1        @staticmethod      def append_node(pre_node: Node, new_node: Node) -> None:          """         在前置节点后添加新节点         :param pre_node: 前置节点         :param new_node: 新节点         :return:         """          new_node.left = pre_node          new_node.right = pre_node.right          pre_node.right.left = new_node          pre_node.right = new_node          return None        def add_level(self) -> None:          """         增加一层         :return:         """          self.max_level += 1          p1 = Node(MIN_VALUE)          p2 = Node(MAX_VALUE)          p1.right = p2          p2.left = p1          p1.down = self.head          self.head.up = p1          p2.down = self.tail          self.tail.up = p2          self.head = p1          self.tail = p2        def remove(self, val) -> bool:          """         删除节点         :param val:         :return:         """          # 找到这个待删除节点          remove_node = self.search(val)          if remove_node is None:              return False          current_level: int = 0          while remove_node is not None:              remove_node.right.left = remove_node.left              remove_node.left.right = remove_node.right              # 如果不是最底层且只有无穷小和无穷大节点，则删除该层              if current_level != 0 and remove_node.left.val == MIN_VALUE and remove_node.right.val == MAX_VALUE:                  self.remove_level(remove_node)              else:                  current_level += 1              remove_node = remove_node.up          return True        def remove_level(self, left_node: Node) -> None:          """         删除一层         :param left_node:         :return:         """          right_node: Node = left_node.right          # 如果删除层是最高层          if left_node.up is None:              left_node.down.up = None              right_node.down.up = None          else:              left_node.up.down = left_node.down              left_node.down.up = left_node.up              right_node.up.down = right_node.down              right_node.down.up = right_node.up          self.max_level -= 1          return None        # 输出底层链表      def print_list(self) -> None:          node = self.head          while node.down is not None:              node = node.down          # 此时node是最底层的head节点          # 下面循环一直往右遍历          while node.right.val != MAX_VALUE:              print(node.right.val, end=" ")              node = node.right          print("")          return None      if __name__ == '__main__':      skip_list = SkipList()      skip_list.insert(50)      for i in range(12):          skip_list.insert(random.randint(10, 200))      skip_list.print_list()      skip_list.search(50)      print(skip_list.remove(50))      skip_list.print_list()  </pre>

Last modification：August 25th, 2020 at 03:17 pm