fasionchan

读万卷书,行万里路,品万味肴,撸万行码。

[译文]跳表:一种平衡树的概率性替代品

| Comments

跳表是一种可以替代平衡树的数据结构。跳表追求的是概率性平衡,而不是严格平衡。因此,跟平衡二叉树相比,跳表的插入删除操作要简单得多,执行也更快。

二叉树可以用来实现字典和有序表等抽象数据结构。在元素随机插入的场景,二叉树可以很好应对。然而,在有序插入的情况下,二叉树就退化了(链表),性能非常差。如果有办法对待插入元素进行随机排列,二叉树大概率可以运行良好。大部分情况下,插入是在线进行的,因此随机排列并不具有可行性。平衡树在操作时对树结构进行调整以满足平衡条件,因此获得理想性能。

跳表是一种概率性可行的平衡二叉树替代数据结构。跳表通过一个随机数生成器实现平衡。虽然跳表最坏情况下(worst-case)性能也很差,但是没有任何输入序列必然会导致最坏情况发生(这点类似划分元素(pivot point)随机选定的快排)。跳表极度不平衡发生的概率非常低(一个包含250个元素的字典,一次查找需要花3倍期望时间的概率小于百万分之一)。跳表平衡概率跟随机插入的二叉树差不多,好处是插入顺序不要求随机。

实现概率性平衡比严格控制平衡要简单得多。对很多应用来说,跳表用起来比平衡树更自然,而且算法更简单。跳表算法简单性意味着更容易实现,而且与平衡树和自适应树相比有常数倍数的性能提升。跳表在空间上也比较高效。平均每个元素只需要额外耗费个2指针(甚至可以配置得更低),并不需要在每个节点上都存与平衡和优先级相关的数据。

结构

Paste_Image.png

搜索一个链表时,我们需要遍历每个节点(如图 1a)。如果列表是有序的,偶数节点另存一个指向下一个偶数节点的指针(如图 1b),我们只需要检查最多(n/2)+1个节点(n是链表规模)。如果序号为4的倍数的节点都有一个往前跳4步的节点,那么最多只需要检查(n/4)+2次。如果,序号为2^i的节点有一个向前跳2^i步的指针,那么则需要检查log2 n次了!这种数据结构可以用来做快速搜索,但是插入和删除并没有可行性。

k个前进指针的节点成为k层节点。如果第2^i个节点有一个向前跳2^i步的指针,那么每层节点数满足以下关系:第1层有50%的节点;第2层有25%的节点;第3层有12.5%的节点;以此类推。假设每层的比例还是一样,但是节点随机选择,会怎样呢(图 1e)?节点第i个前进指针不严格跳2^i步,而是可以跳任意步。由于不需要维持特殊条件,插入节点层数随机生成,插入和删除只需要做局部修改。极端情况下,有些层次分布会导致极差的性能,不过接下来我们会看到这种情况非常罕见。这种数据结构在链表的基础上加上额外指针以跳过一些中间节点,因此命名为跳表

算法

这小节介绍用于搜索插入删除的算法。搜索操作返回与给定键(key)关联的值(value),键不存在时则失败。插入操作将给定键关联到新的值,如果键不存在则插入新的节点。删除操作删除给定键。另外,类似最小键下一键这类操作实现起来也非常简单。

每个元素由一个节点表示,层次由节点在插入时随机选定,与已有元素无关。层次为i的节点拥有i个前进指针,下标分别是1i。节点不需要存储层数。选定一个合适的常量MaxLevel,层数在这个范围内。跳表的层数时当前所有节点层数的最大值,或者当跳表为空是,层数为1。用一个头向量存储从层次1MaxLevel的向前指针。指针高于当前跳表层数的部分直接指向NIL

初始化

约定NIL元素,其键比所有合法建都大(上限)。跳表的任意层都以NIL结尾。新的跳表初始化成层数只有1,并且所有表头所有前进指针都指向NIL

查找

查找某个元素时,需要逐层遍历所有键不超过给定键的节点。如果当前层前进节点已经不符合条件了,往下一层开始遍历。当遍历进行到第1层时,下一个节点就是目标节点(如存在)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Search(list, searchKey)
    x := list->header

    for i := list->level downto 1 do
        while x->forward[i]->key < searchKey do
            x = x->forward[i]

    x := x->forward[1]

    if x->key = searchKey
    then
        return x->value
    else
        return failure

插入/删除

插入或者删除节点,只需先执行搜索操作(图 3),然后视情况重新拼接。伪代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Insert(list, searchKey, newValue)
    local update[1..MaxLevel]
    x := list-header

    for i := list->level downto 1 do
        while x->forward[i]->key < searchKey do
            x := x->forward[i]
        update[i] := x

    x := x->forward[i]

    if x->key = searchKey then
        x->value := newValue
    else
        lvl := randomLevel()
        if lvl > list->level then
            for i := list->level+1 to lvl do
                update[i] := list->header
            list->level = lvl
        x := makeNode(lvl, searchKey, value)
        for i := 1 to lvl do
            x->forward[i] = update[i]->forward[i]
            update[i]->forward[i] := x

Paste_Image.png

图3展示了搜索过程。注意到,搜索的过程中维护了一个名为update的向量,在每次降层搜索时更新。搜索完成后,update刚好记录了各层在操作位置(图中环)左边最近的节点:

元素 节点
update[1] 12
update[2] 9
update[3] 6
update[4] 6

如果插入时生成了一个比当前最大层更大的层数,则需要更新跳表层数并且初始化update向量对应部分。

接下来,看看删除操作的伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Delete(list, searchKey)
    local update[1..MaxLevel]
    x := list-header

    for i := list->level downto 1 do
        while x->forward[i]->key < searchKey do
            x := x->forward[i]
        update[i] := x

    x := x->forward[i]

    if x->key < searchKey then
        for i := 1 to list->level do
            if update[i]->forward[i] != x then break
            update[i]->forward[i] = x->forward[i]

        free(x)

        while list->level > 1 and list->header->forward[list->level] = NIL do
            list->level := list->level - 1

在每次删除时,需要检查被删除节点是否是最大层节点。如果是,需要对跳表层数做对应调整。

随机函数

接下来,需啊确定一个随机数生成函数,其概率分布使得第i层中有50%的节点同时数据第i+1层。先抛开具体数值,我们在讨论一个分数p,对于有i层指针的节点中p部分,同时拥有i+1层指针。以下便是一个非常理想的随机数生成函数,随机层数生成与跳表元素及规模无关:

1
2
3
4
5
randomLevel()
    lvl := 1
    while random() < p and lvl < MaxLevel do
        lvl := lvl + 1
    return lvl

Comments