[H数据结构] lc1206. 设计跳表(模拟+数据结构+跳表实现+优秀博文)

1. 题目来源

链接：1206. 设计跳表

相关博文：

• 优秀博主：张铁蕾 — Redis内部数据结构详解(6)——skiplist
• 优秀题解：C++ 手写跳表最简单的实现方式，思路详解附详细代码注释【1206. 设计跳表】

题单：

• 待补充

2. 题目解析

本题是一个非常优秀的数据结构，跳表。

其在 Redis 和 levelDB 中都有用到。其设计思想和适用场景见：优秀博主：张铁蕾 — Redis内部数据结构详解(6)——skiplist 博文即可。

这里我仅做 golang 版本的代码实现，算是一个算法模板。

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

const LEVEL = 8         // 经验值，本题跳表层级 8 层，Redis 32 层。0层为最下层包含所有元素。7层为最上层元素最少
type Node struct {      // 跳表节点结构体
    val int      // 节点值
    ns []*Node   // 节点在每一层所指向的下一个 next 节点列表  ns: make([]*Node, LEVEL)
}

// 新建跳表节点
func newNode(v int) *Node {
    return &Node { val: v, ns: make([]*Node, LEVEL) }
}

// 核心：辅助查找函数。
// 作用：找到每一层中最后一个小于 v 的节点。这里需要从上往下找
func (this *Skiplist) find(v int) []*Node {
    pre := make([]*Node, LEVEL)
    p := this.head
    for i := LEVEL - 1; i >= 0; i -- {
        for p.ns[i] != nil && p.ns[i].val < v {
            p = p.ns[i]
        }
        pre[i] = p
    }

    return pre
}

// 跳表结构
type Skiplist struct {
    head *Node    
}

// 初始化跳表头指针，作为虚拟头节点，跳表各层的虚拟头节点
func Constructor() Skiplist {
    return Skiplist{head: newNode(-1)}
}

// 查找
// 1. 辅助函数，先找到每一层中最后一个小于 v 的节点列表
// 2. 第 0 层包含所有元素。pre[0] 代表小于 target 的最后一个元素
// 3. pre[0].ns[0] 则为第零层小于 target 的下一个第 0 层的元素。
// 4. 若其不为 nil 并且值等于 target 时，target 则存在，否则不存在。
func (this *Skiplist) Search(target int) bool {
    pre := this.find(target) 
    p := pre[0].ns[0]
    return p != nil && p.val == target
}

// 插入
// 1. 辅助函数，先找到每一层中最后一个小于 v 的节点列表
// 2. 运用链表插入的方式将新建的 num 节点插入进跳表中。
// 3. 注意该节点有 50% 的几率会被加入上层跳表
func (this *Skiplist) Add(num int)  {
    pre := this.find(num)
    p := newNode(num)
    for i := 0; i < LEVEL; i ++ {
        p.ns[i] = pre[i].ns[i]
        pre[i].ns[i] = p
        if rand.Intn(2) == 0 {
            break
        }
    }
}

// 删除
// 1. 辅助函数，先找到每一层中最后一个小于 v 的节点列表
// 2. 先查询一下 num 是否存在, 不存在无法删除，直接返回即可
// 3. 再进行每一层的判断这个元素是否存在，存在则进行单链表的删除即可
func (this *Skiplist) Erase(num int) bool {
    pre := this.find(num)
    if this.Search(num) == false {
        return false
    }

    p := pre[0].ns[0]
    for i := 0; i < LEVEL && pre[i].ns[i] == p; i ++ {
        pre[i].ns[i] = p.ns[i]
    }

    return true
}


/**
 * Your Skiplist object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Search(target);
 * obj.Add(num);
 * param_3 := obj.Erase(num);
 */