python实现跳跃表(SkipList)

Posted on | In

跳跃表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，它的效率和红黑树以及 AVL 树不相上下，但原理相当简单，只要你能熟练操作链表，就能轻松实现一个跳跃表。

img

从图中可以看到， 跳跃表主要由以下部分构成：

  • 表头（head）：负责维护跳跃表的节点指针。
  • 跳跃表节点：保存着元素值，以及多个层。
  • 层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。
  • 表尾：全部由 NULL 组成，表示跳跃表的末尾。

跳跃表有如下特点：

  1. 每个跳跃表由很多层结构组成。
  2. 每一层都是一个有序链表，且第一个节点是头节点。
  3. 最底层的有序链表包含所有节点。
  4. 每个节点可能有多个指针，这与节点所包含的层数有关。
  5. 跳跃表的查找、插入、删除的时间复杂度均为O(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
import random
MAX_DEPTH = 5

class SkipNode:
    def __init__(self, height = 0, elem = None):
        self.elem = elem
        self.next = [None]*height

    def __repr__(self):
        return str(self.elem)

class SkipList:
    def __init__(self):
        self.head = SkipNode()

    def updateList(self, elem):

        update = [None] * len(self.head.next)
        x = self.head

        for i in reversed(range(len(self.head.next))):
            while x.next[i] != None and \
                    x.next[i].elem < elem:
                x = x.next[i]
            update[i] = x

        return update

    def find(self, elem, update=None):
        if update == None:
            update = self.updateList(elem)
        if len(update) > 0:
            candidate = update[0].next[0]
            if candidate != None and candidate.elem == elem:
                return candidate
        return None

    def insert(self, elem):
        node = SkipNode(self.randomHeight(), elem)
        
        while len(self.head.next) < len(node.next):
            self.head.next.append(None)

        update = self.updateList(elem)
        if self.find(elem, update) == None:
            for i in range(len(node.next)):
                node.next[i] = update[i].next[i]
                update[i].next[i] = node

    def randomHeight(self):
        k = 1
        while random.randint(0, 1):
            k = k + 1
            if k == MAX_DEPTH:
                break
        return k

    def remove(self, elem):
        update = self.updateList(elem)
        x = self.find(elem, update)
        if x != None:
            for i in range(len(x.next)):
                update[i].next[i] = x.next[i]
                if self.head.next[i] == None:
                    self.head.next = self.head.next[:i]
                    return

    def traversal(self):
        for i in reversed(range(len(self.head.next))):
            x = self.head
            line = []
            while x.next[i] != None:
                line.append(str(x.next[i].elem))
                x = x.next[i]
            print('line{}: '.format(i+1) + '->'.join(line))

主要方法updateList的作用是，从跳跃表的最顶层开始依次向下查找，找到该层级中比给定元素elem小的最大一个元素，将该元素保存起来，重复以上步骤知道到达最底层。它返回一个列表update，update[0]表示第一层最后一个比elem小的元素，以此类推。该方法可以使得插入删除操作变得更加简单。

在向跳跃表中插入新的结点时候，我们需要生成该结点的层数。使用抛硬币的思想随机生成层数，如果是正面（random.randint(0, 1) == 1）则层数加一，直到抛出反面为止。其中的 MAX_DEPTH 是防止如果运气太好，层数就会太高，而太高的层数往往并不会提供额外的性能。