有了红黑树,为啥还要跳表?

书接前文。

前文书《红黑树是怎么来的》我们讲了通过红黑树(本质上是 2-3 树或者 2-3-4 树思想)来维护二叉搜索树的平衡性。从红黑树的实现来看,虽然相对于 2-3 树来说是简化了不少,但仍然是相当复杂的。

有没有更加简单的实现方案呢?


源于二分思想

在前文《二叉搜索树的本质》中我们通过将有序数组的二分查找链表化,最终得到二叉搜索树。

这次,我们还是从有序数组的二分查找开始,看看能否发明什么新的数据结构。

和以前不同的是,这次我们先将有序数组链表化:

如图。现在我们考虑如何在该链表中查找元素 40。

最简单的做法是从表头开始往后遍历,时间复杂度 O(n)——显然不是我们想要的。

我们的初步想法是:能否在这个链表上执行二分搜索?

对于数组来说,我们可以通过地址偏移立即定位到中间元素(15),然后发现 40 比 15 大,继续对 15 后面的元素执行二分查找即可。

链表的困境在于,它没法通过地址偏移来快速定位元素。

不过我们并不死心——有没有什么奇技淫巧来模拟链表上的二分查找?

既然对于链表,只能通过指针来遍历元素,那我们能否通过给节点 1、15、60(头尾以及二分查找涉及到的中间元素)之间建立额外的指针来实现快速跳转呢?

如图:

我们建立了一个额外的链表(1→15→60),且该链表的每个节点都有一个额外指针指向下一层的同名节点。

有什么用呢?

再来看看如何查找元素 40。

我们可以先查上面(第二层)那个链表,只需两步就走到元素 15,发现 40 介于 15 和 60(15 的下一个元素)之间,于是我们通过 15 的“下降”指针来到第一层链表同名节点 15,然后在第一层链表中继续往后查找。

如图:

和直接在原始链表上遍历不同,通过添加一层“索引”链表,我们能和二分查找一样“直达”中间元素,搜索效率一下子提升了一倍。

那么,这个查询能否再优化一下呢?

上图中,15 以后的搜索仍然是线性的。我们同样可以对 1-15、15-60 之间的两段子链表再次建立“索引链表”:

乍看有点小复杂,实际上它仍然是对二分查找的模拟。

我们从上层往下层看。

第三层相当于执行第一次二分,标的元素是 15,然后根据实际情况到 1-15 或者 15-60 区间去查找。

第二层则是在第三层(第一次二分查找)的基础上做的第二次二分,得到更细粒度的查找区间。

所以说,如果我们从最上层索引链表往最下层方向逐层查找,就相当于模拟有序数组一次次的二分查找。

妙哉!

我们看看建立两层索引后元素 40 的查找路径:

和一层相比,查找路径要短很多。

和普通链表相比,这种链表通过索引“跳过”了一些节点,以提升搜索效率,因而我们给它起个“望文生义”的名字就叫跳表(skiplist)。

由于跳表本质上是对二分法的模拟,所以其搜索时间复杂度同二分搜索一样是 O(logn)。


数据结构

跳表的节点(最底层除外)除了要指向后继节点(如果是双向链表还要指向前驱节点),还需要指向下层同名节点,所以节点结构初步定义如下:

class Node {
    key: number
    val: unknown
    // 后继节点
    next: Node | null
    // 下层节点(比普通链表多出来的指针)
    down: Node | null

    public constructor(key: number, val: unknown) {
        // ......
    }
}

上图中节点 15 表示如下:

// 第三层的 node15
const node15_l3: Node = {
    key: 15,
    val: 15,
    next: node60_l3,
    down: node15_l2,
}

// 第二层的 node15
const node15_l2: Node = {
    key: 15,
    val: 15,
    next: node30_l2,
    down: node15_l1,
}

// 第一层的 node15
const node15_l1: Node = {
    key: 15,
    val: 15,
    next: node20_l1,
    down: null,
}

我们分析一下上面的数据结构定义有没有什么问题。

首先说明一点,通过建立索引链表来提升搜索速度属于典型的用空间换时间

不过,我们为同一个元素(如上例中的 15)在每一层都建立了一个独立的对象——这是不是过于铺张浪费了?

我们分析一下上面三个 object 的特点,看看有没有什么优化空间:

  1. 三个节点的 key、val 都是一样的;
  2. 最大的不同在于 next 指针,三个节点的 next 都不一样;
  3. 由图可知,上层节点总是逐层下潜的(即第 n 层节点的 down 指针总是指向第 n - 1 层的同名节点);

所以我们可以尝试将同一元素的各层节点合而为一:

class Node {
    public key: number
    public val: unknown
    // 该节点各层的后继节点指针数组
    public nexts: (Node | null)[]

    public constructor(key: number, val: unknown) {
        // ......
    }
}

如上,我们将 next 和 down 两个指针合入到 nexts 指针数组中,nexts[i] 表示该节点在第 i + 1 层的后继节点。

改造后图示如下:

如上图,我们做了四方面的改造:

  1. 各层的同名节点(同 key)合并成一个节点;
  2. 引入 nexts 指针数组,node.nexts[i] 表示节点 node 在第 i + 1 层的后继节点;
  3. 为编码上的方便,引入哨兵节点 head(不表示任何实际节点);
  4. 不再对尾节点(图中的 60)建立索引(没有必要,编程中用 null 值判断即可);

最后我们定义出完整的数据结构:

class SkipList {
    // 表头指针。为方便处理,表头不表示实际节点, 作为哨兵存在
    protected head: Node
    // 跳表中元素个数
    protected length: number
    // 跳表层数
    protected level: number
    
    public constructor() {
        // 创建表头
        this.head = new Node(-Infinity, undefined)
        this.length = 0
        this.level = 0
    }
}

查找元素

我们看看如何查找节点 40。

任何查找都从表头 head 且从最上层开始,到第一层为止:

  1. 取 head.nexts[2],是 15,小于 40,则取 node15 继续比较;
  2. 取 node15.nexts[2],是 null,说明不能再往后找了,则下降到第二层(nexts 下标 1);
  3. 取 node15.nexts[1],是 30,小于 40,则取 node30 继续比较;
  4. 取 node30.nexts[1],是 null,说明不能再往后找了,则下降到第一层(nexts 下标 0);
  5. 取 node30.nexts[0],是 40,找到,返回并结束;

如图:

代码如下:

class SkipList {
    // ......

    /**
     * 根据 key 查找 value 并返回,如果没找到则返回 undefined
     * @param key
     */
    public search(key: number): unknown {
        if (!this.length) {
            return
        }

        // 从 head 开始找
        let node = this.head

        // 从最高层开始往下搜索,直到搜到第一层
        for (let i = this.level - 1; i >= 0; i--) {
            // 如果当前节点该层存在后继节点,且该后继节点的 key 小于等于目标 key,则跳到该后继节点
            while (node.nexts[i] && node.nexts[i].key <= key) {
                node = node.nexts[i]
            }

            // 从 node 进入到下一层继续查找
        }

        return node.key === key ? node.val : undefined
    }
}

超简单有没有!


索引层数

在讲插入之前,我们先思考一个问题:链表中的某个元素应该有多少层(或者说需要给它建多少层索引)?

前面我们通过二分法推导出多层索引的概念。但如果在实际操作中,每次插入一个元素后都用二分法思想去确定元素的索引层数,可能一次插入会导致大范围的索引重建(比如原本通过二分法拿到标的节点是 a,插入新元素后再次二分拿到的标的很可能不再是 a)。

我们也可以采用类似 B 树的裂变思想,比如我们规定第 n 层两个节点之间所囊括的 n - 1 层元素数量不可超过 x,一旦超过就触发裂变以生成新的索引(裂变可能是级联的)。不过其实现起来也比较复杂。

跳表的设计采用了一种简单粗暴但很有效的方法:概率法

思想是这样的:我们规定第 n 层的元素数量是其下一层(n - 1)数量的 1/N。换句话说,一个元素有 1/N 的概率会向上建一层索引。

以 N = 4 为例。

假设我们想插入元素 22——该元素需要建立几层索引呢?

有 3/4 的概率不建立任何索引(也就是只有最底下一层)。

有 1/4 的概率建立 1 层索引。

有 1/4 * 1/4 即 1/16 的概率建 2 层索引。

有 1/4 * 1/4 * 1/4 即 1/64 的概率建 3 层索引。

依此类推。

如此得到的数据结构本质上是一棵 N 叉树(这里是 4 叉树)。

我们通过如下代码计算一个新节点的层数信息:

class SkipList {
    // 最大层数限制
    protected static readonly MAX_LEVEL = 32
    // 上层元素数是下层数量的 1/N(相当于 N 叉树)
    protected static readonly N = 4
    // ......

    /**
     * 随机生成 level 层数
     * 从最底层开始,每增加一层的概率为 1/N
     */
    protected randomLevel(): number {
        let level = 1

        while (Math.round(Math.random()*10000000) % SkipList.N === 0) {
            level++
        }

        return Math.min(level, SkipList.MAX_LEVEL)
    }
}

这里我们通过将生成的随机数对 N 取模和 0 比较来模拟 1/N 的概率(比如 N = 4,则取模后为 0-3)。


插入元素

我们看如何插入元素 22。

首先要确定 22 在原始链表(第一层链表)中的位置,该过程实际就是搜索过程,时间复杂度 O(logn)。

搜索过程如图:

我们找到应该在 20 和 25 两个节点之间插入 22。

假如我们通过 randomLevel() 得到层数是 5,插入后整个跳表长这样:

观察上图发现:

  1. 每层都有 next 指针指向该新节点,具体来说就是搜索路径上各层最右搜索节点(15、15、20)的 next 指针指向新节点;
  2. 新层(最高两层)的前驱节点都是 head;
  3. 新节点的各层 next 指针指向该层前驱节点的 next 原值;

经上面分析发现,整个插入过程中,关键是找出每层的前驱节点。代码如下:

class SkipList {
    /**
     * 搜索关键字 key,返回其搜索路径上经过的每层的前驱节点数组
     * 即每层返回其左边相邻节点
     * @param key - 关键字
     * @returns 关键字 key 在每层的前驱节点数组
     */
    private searchPrevNodes(key: number): Node[] {
        // 记录每层走到的最右边的位置(也就是目标节点的前驱节点)
        const prevNodes: Node[] = []
        // 从 head 开始
        let node = this.head

        // 从最上层开始往下找
        for (let i = this.level - 1; i >= 0; i--) {
            // 如果当前节点该层存在后继节点,且该后继节点的 key 小于 key,则跳到该后继节点
            while (node.nexts[i] && node.nexts[i].key < key) {
                node = node.nexts[i]
            }

            // 下沉之前记录该节点作为本层访问到的最右节点
            prevNodes[i] = node
        }

        // 如果一个都没有(列表为空,this.level = 0 时),将 head 加入进去
        if (!prevNodes.length) {
            prevNodes[0] = this.head
        }

        return prevNodes
    }
}

元素插入逻辑代码如下:

class SkipList {
    // ......

    /**
     * 将 { key, val } 插入到跳表中
     */
    public insert(key: number, val: unknown) {
        // 获取搜索路径上的各层前驱节点
        const prevNodes = this.searchPrevNodes(key)

        // 创建新节点
        const newNode: Node = { key, val, prev: null, nexts: [] }

        // 计算新节点的索引层数
        const level = this.randomLevel()

        // 逐层处理 next 指针
        for (let i = 0; i < level; i++) {
            // prevNodes 里面仅有原先 this.level 层的最右 node,而新 level 可能高于原 level,
            // 该情况下,超出的层在 prevNodes 里面没有对应节点,则直接取 head
            const leftNode = prevNodes[i] ?? this.head

            // 变更 next 指针
            newNode.nexts[i] = leftNode.nexts[i]
            leftNode.nexts[i] = newNode
        }

        if (level > this.level) {
            this.level = level
        }

        this.length++
    }
}

插入过程的平均时间复杂度是 O(logn)。


删除元素

考虑删除节点 22,删除后整个跳表结构如下:

跳表元素的删除本质就是插入的逆操作:将该节点从各层抹除,即将该节点各层的前驱节点的 next 指针指向该节点在该层的后继节点。

插入过程中可能产生新的层(head 层数随之增长),而删除则可能造成层数减少(head 层数收缩)。

通过观察图示不难发现,删除后和插入前的结构竟然是一模一样的,如此的稳定性真让人叹为惊奇。

不同于其他平衡树,跳表的插入和删除不但完全互逆,而且也没有复杂的递归重建过程——这正是跳表这种概率型数据结构的简单性之精华所在。

删除代码如下:

class SkipList {
    // ......

    public delete(key: number) {
        // 获取搜索路径上的各层前驱节点
        const prevNodes = this.searchPrevNodes(key)
        // 待删除的节点就是第一层前驱节点的该层 next 指针所指向的节点
        const current = prevNodes[0].nexts[0]

        if (!current || current.key !== key) {
            return
        }

        // 从下往上,处理各层的 next 指针
        // 需要处理的层:待删节点的索引层数
        for (let i = 0; i < current.nexts.length; i++) {
            prevNodes[i].nexts[i] = current.nexts[i]
            current.nexts[i] = null

            // 如果该层的前驱节点是 head,且调整后其 next 指向 null/undefined,说明该层不再有有效节点,需要将层数减 1
            if (!this.head.nexts[i]) {
                this.level--
            }
        }

        this.length--
    }
}

简单性的源头

对比红黑树的插入和删除实现,你会惊于跳表的实现是如此简单。为何?

我们假设不使用概率来决定新节点的索引层数,就很可能需要采用类似 B 树的方案,通过限制两索引节点之间所辖节点数来决定索引的分裂与合并。比如规定任何两索引节点之间所辖节点数必须在 N/2 到 N 之间,小于 N/2 则谋求合并,超过 N 则分裂。如此必然会带来复杂的级联分裂与合并逻辑。

相反,跳表采用了简单粗暴但同样有效的概率法,在插入元素的时候,通过概率计算得出索引层数,而更新索引(插入和删除)仅影响该节点在各层的前驱节点,影响非常小,更新过程异常简单。

所以说,这种数据结构的概率性带来了其简单性


总结

  1. 我们通过有序数组的二分查找思想推导出链式数据结构的二分法:多级索引
  2. 通过概率决定每个元素的索引层数,在理论正确性的前提下保证了实现的简单性;
  3. 插入和删除操作的关键是找出目标节点在每层的前驱节点
  4. 插入和删除操作是完全互逆的,表明跳表具备很好的动态稳定性
  5. 跳表和红黑树的各项操作具备同级别的时间复杂度,但比红黑树实现起来更加简单,范围查询也更加直观高效(直接定位到起始节点,然后直接在第一层顺序遍历即可),所以现在很多项目都采用了跳表这种数据结构(如 Redis、Lucene、LevelDB 等);

另外,分级索引是人类信息检索领域的一个重要思想,图书检索、书本目录、文件系统、域名(DNS 查询)、ip 地址、操作系统页表等等的设计都体现了该思想。

本文完整代码参见 github: https://github.com/linzier/algo-ts。

为讲解的简单性,本文使用的是单向链表,github 中实现的是双向链表。

热门相关:总裁别再玩了   变身蜘蛛侠   金粉   不良侦探:失踪   裙上之臣