跳表-白话查询和插入过程

假设初始跳表结构为

Level 3:    [HEAD] ---------------------------------> [100]
Level 2:    [HEAD] ---------> [30] ---------> [70] -> [100]
Level 1:    [HEAD] -> [10] -> [30] -> [40] -> [70] -> [100]

一、查询过程

假如要查找 50。
步骤 1:从顶层开始
从最高层(Level 3)的 HEAD 开始。

Level 3:    [HEAD] --------------------------------> [100]

在这一层中,我们发现下一个节点 100 大于 50,因此我们需要向下移动到 Level 2。
步骤 2:移动到 Level 2
在 Level 2 的 HEAD 开始,下一个节点是 30,小于 50,继续向右。

Level 2:    [HEAD] ---------> [30] ---------> [70] -> [100]

接下来的节点是 70,大于 50,因此我们再次向下移动到 Level 1。
步骤 3: 移动到 Level 1
现在在 Level 1,从 30 向右移动到 40。

Level 1:    [30] -> [40] -> [70] -> [100]

40 小于 50,继续向右。下一个节点是 70,大于 50,停止。此时我们确定 50 不存在于跳表中,且应该位于 40 和 70 之间。

二、插入过程

例如要插入 50。
步骤 1: 找到插入点
首先执行查询过程,并保存查询过程中每一层的前向节点。
Level 3 就是 HEAD。
Level 2 就是 30。
Level 1 就是 40。
步骤 2: 决定新节点的高度
通过随机机制,我们决定新节点 50 的高度(高度越高的概率越小)。假设结果是高度到 Level 2。
步骤 3: 在各层中插入
在 Level 1 执行插入操作:

Level 1:    [40] -> [50] -> [70]

在 Level 2 执行插入操作:

Level 2:    [30] ---------> [50] -> [70]

更新后的跳表结构

Level 3:    [HEAD] -----------------------------------------> [100]
Level 2:    [HEAD] ---------> [30] ---------> [50] -> [70] -> [100]
Level 1:    [HEAD] -> [10] -> [30] -> [40] -> [50] -> [70] -> [100]
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。