跳表

发布时间 2023-07-30 14:50:44作者: 好人~

  • 查找性能为O(logn)。从最上层开始查找,找到小于目标的最大节点。
  • 插入性能高于平衡树。插入一个元素时,会为该元素生成随机个索引层。跳表使用简单的随机数操作而构建出来的多层链表结构,就获取查找性能为O(logn)【论文中有数学证明】