数据结构：跳跃表

发表于

跳表(skip list) 对标的是平衡树(AVL Tree)，是一种 插入/删除/搜索 都是 O(log n) 的数据结构。它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此在一些热门的项目里用来替代平衡树，如 redis, leveldb 等

跳表的基本思想

首先，跳表处理的是有序的链表（一般是双向链表，下图未表示双向），如下：

这个链表中，如果要搜索一个数，需要从头到尾比较每个元素是否匹配，直到找到匹配的数为止，即时间复杂度是 O(n)O(n)。同理，插入一个数并保持链表有序，需要先找到合适的插入位置，再执行插入，总计也是 O(n)O(n) 的时间。

那么如何提高搜索的速度呢？很简单，做个索引：

如上图，我们新创建一个链表，它包含的元素为前一个链表的偶数个元素。这样在搜索一个元素时，我们先在上层链表进行搜索，当元素未找到时再到下层链表中搜索。例如搜索数字 19 时的路径如下图：

先在上层中搜索，到达节点 17 时发现下一个节点为 21，已经大于 19，于是转到下一层搜索，找到的目标数字 19。

我们知道上层的节点数目为 n/2n/2，因此，有了这层索引，我们搜索的时间复杂度降为了：O(n/2)O(n/2)。同理，我们可以不断地增加层数，来减少搜索的时间：

在上面的 4 层链表中搜索 25，在最上层搜索时就可以直接跳过 21 之前的所有节点，因此十分高效。

更一般地，如果有 kk 层，我们需要的搜索次数会小于 ⌈n2k⌉+k⌈n2k⌉+k ，这样当层数 kk 增加到 ⌈log2n⌉⌈log2⁡n⌉ 时，搜索的时间复杂度就变成了 lognlog⁡n。其实这背后的原理和二叉搜索树或二分查找很类似，通过索引来跳过大量的节点，从而提高搜索效率。

跳表

上节的结构是“静态”的，即我们先拥有了一个链表，再在之上建了多层的索引。但是在实际使用中，我们的链表是通过多次插入/删除形成的，换句话说是“动态”的。上节的结构要求上层相邻节点与对应下层节点间的个数比是 1:2，随意插入/删除一个节点，这个要求就被被破坏了。

因此跳表（skip list）表示，我们就不强制要求 1:2 了，一个节点要不要被索引，建几层的索引，都在节点插入时由抛硬币决定。当然，虽然索引的节点、索引的层数是随机的，为了保证搜索的效率，要大致保证每层的节点数目与上节的结构相当。下面是一个随机生成的跳表：

可以看到它每层的节点数还和上节的结构差不多，但是上下层的节点的对应关系已经完全被打破了。

现在假设节点 17 是最后插入的，在插入之前，我们需要搜索得到插入的位置：

接着，抛硬币决定要建立几层的索引，伪代码如下：

1
2
3
4
5
6
randomLevel()  
 lvl := 1  
 -- random() that returns a random value in \[0...1)  
 while random() < p and lvl < MaxLevel do  
 lvl := lvl + 1  
 return lvl

上面的伪代码相当于抛硬币，如果是正面（random() < p）则层数加一，直到抛出反面为止。其中的 MaxLevel 是防止如果运气太好，层数就会太高，而太高的层数往往并不会提供额外的性能，一般 MaxLevel\=log1/pnMaxLevel\=log1/p⁡n。现在假设 randomLevel 返回的结果是 2，那么就得到下面的结果。

如果要删除节点，则把节点和对应的所有索引节点全部删除即可。当然，要删除节点时需要先搜索得到该节点，搜索过程中可以把路径记录下来，这样删除索引层节点的时候就不需要多次搜索了。

显然，在最坏的情况下，所有节点都没有创建索引，时间复杂度为O(n)O(n)，但在平均情况下，搜索的时间复杂度却是 O(logn)O(log⁡n)

总结

1.各种搜索结构提高效率的方式都是通过空间换时间得到的
2.跳表通过随机方式决定新插入节点索引层数
3.跳表搜索查询删除时间复杂度为Log(n)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
type Skiplist struct {
    Head  *Node     //dummynode 虚拟头节点
    Level int
}
type Node struct {
    Key     int
    Forword []*Node     //存放索引
}
const p = 0.5
const MaxLevel = 32
func Constructor() Skiplist {
    level := randLevel()
    return Skiplist{Head: &Node{Forword: make([]*Node, MaxLevel)}, Level: level}    //初始化时dummynode 层级直接给到最大
}
func randLevel() int {
    level := 1
    rand.Seed(time.Now().UnixNano())
    for rand.Float64() < p && level < MaxLevel {
        level++
    }
    return level
}
func (this *Skiplist) Search(target int) bool {
    x := this.Head
    for i := this.Level - 1; i >= 0; i-- {
        for x.Forword[i] != nil && x.Forword[i].Key < target {
            x = x.Forword[i]
        }
    }
    x = x.Forword[0]
    if x != nil && x.Key == target {
        return true
    } else {
        return false
    }
}
func (this *Skiplist) Add(num int) {
    x := this.Head
    update := make([]*Node, MaxLevel)       //update[i]表示第i层前驱节点
    for i := this.Level - 1; i >= 0; i-- {
        for x.Forword[i] != nil && x.Forword[i].Key <= num {
            x = x.Forword[i]
        }
        update[i] = x
    }
    level := randLevel()
    node := &Node{Key: num, Forword: make([]*Node, level)}
    if level > this.Level {
        for i := this.Level; i < level; i++ {
            update[i] = this.Head
        }
        this.Level = level
    }
    for i := level - 1; i >= 0; i-- {       //实际只需对0~level-1层进行改动，举个例子this.Level为5 level为3 则只需要对0~2层做调整 3~4层不动
        node.Forword[i] = update[i].Forword[i]
        update[i].Forword[i] = node
    }
    return
}
func (this *Skiplist) Erase(num int) bool {
    x := this.Head
    flag := false
    for i := this.Level - 1; i >= 0; i-- {
        for x.Forword[i] != nil {
            if x.Forword[i].Key == num {
                tmp := x.Forword[i]
                x.Forword[i] = tmp.Forword[i]
                tmp.Forword[i] = nil
                flag = true
                break //遇到满足条件的node后删除后切换到下一层，对外表现是对于多个相同的num删除时只删一个
            } else if x.Forword[i].Key < num {
                x = x.Forword[i]
            } else {
                break
            }
        }
    }
    return flag
}

参考

跳表──没听过但很犀利的数据结构
跳跃表（skiplist）及其 Go 实现