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

假设初始跳表结构为：

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]