[H数据布局] lc1206. 计划跳表(模仿+数据布局+跳表实现+良好博文)

1. 标题泉源

链接：1206. 计划跳表

干系博文：

• 良好博主：张铁蕾 — Redis内部数据布局详解(6)——skiplist
  
• 良好题解：C++ 手写跳表最简朴的实现方式，思绪详解附具体代码解释【1206. 计划跳表】
  

题单：

• 待增补
  

2. 标题剖析

本题是一个非常良好的数据布局，跳表。
其在 Redis 和 levelDB 中都有用到。其计划头脑和实用场景见：良好博主：张铁蕾 — Redis内部数据布局详解(6)——skiplist 博文即可。
这里我仅做 golang 版本的代码实现，算是一个算法模板。

---

• 时间复杂度：                                   O                         (                         log                         ⁡                         n                         )                              O(\log n)                  O(logn)
  
• 空间复杂度：                                   O                         (                         n                         )                              O(n)                  O(n)
  

---

1. const LEVEL = 8         // 经验值，本题跳表层级 8 层，Redis 32 层。0层为最下层包含所有元素。7层为最上层元素最少
2. type Node struct {      // 跳表节点结构体
3.     val int      // 节点值
4.     ns []*Node   // 节点在每一层所指向的下一个 next 节点列表  ns: make([]*Node, LEVEL)
5. }
7. // 新建跳表节点
8. func newNode(v int) *Node {
9.     return &Node { val: v, ns: make([]*Node, LEVEL) }
10. }
12. // 核心：辅助查找函数。
13. // 作用：找到每一层中最后一个小于 v 的节点。这里需要从上往下找
14. func (this *Skiplist) find(v int) []*Node {
15.     pre := make([]*Node, LEVEL)
16.     p := this.head
17.     for i := LEVEL - 1; i >= 0; i -- {
18.         for p.ns[i] != nil && p.ns[i].val < v {
19.             p = p.ns[i]
20.         }
21.         pre[i] = p
22.     }
24.     return pre
25. }
27. // 跳表结构
28. type Skiplist struct {
29.     head *Node   
30. }
32. // 初始化跳表头指针，作为虚拟头节点，跳表各层的虚拟头节点
33. func Constructor() Skiplist {
34.     return Skiplist{head: newNode(-1)}
35. }
37. // 查找
38. // 1. 辅助函数，先找到每一层中最后一个小于 v 的节点列表
39. // 2. 第 0 层包含所有元素。pre[0] 代表小于 target 的最后一个元素
40. // 3. pre[0].ns[0] 则为第零层小于 target 的下一个第 0 层的元素。
41. // 4. 若其不为 nil 并且值等于 target 时，target 则存在，否则不存在。
42. func (this *Skiplist) Search(target int) bool {
43.     pre := this.find(target)
44.     p := pre[0].ns[0]
45.     return p != nil && p.val == target
46. }
48. // 插入
49. // 1. 辅助函数，先找到每一层中最后一个小于 v 的节点列表
50. // 2. 运用链表插入的方式将新建的 num 节点插入进跳表中。
51. // 3. 注意该节点有 50% 的几率会被加入上层跳表
52. func (this *Skiplist) Add(num int)  {
53.     pre := this.find(num)
54.     p := newNode(num)
55.     for i := 0; i < LEVEL; i ++ {
56.         p.ns[i] = pre[i].ns[i]
57.         pre[i].ns[i] = p
58.         if rand.Intn(2) == 0 {
59.             break
60.         }
61.     }
62. }
64. // 删除
65. // 1. 辅助函数，先找到每一层中最后一个小于 v 的节点列表
66. // 2. 先查询一下 num 是否存在, 不存在无法删除，直接返回即可
67. // 3. 再进行每一层的判断这个元素是否存在，存在则进行单链表的删除即可
68. func (this *Skiplist) Erase(num int) bool {
69.     pre := this.find(num)
70.     if this.Search(num) == false {
71.         return false
72.     }
74.     p := pre[0].ns[0]
75.     for i := 0; i < LEVEL && pre[i].ns[i] == p; i ++ {
76.         pre[i].ns[i] = p.ns[i]
77.     }
79.     return true
80. }
82. /**
83. * Your Skiplist object will be instantiated and called as such:
84. * obj := Constructor();
85. * param_1 := obj.Search(target);
86. * obj.Add(num);
87. * param_3 := obj.Erase(num);
88. */

复制代码