21 附录：K—近邻分类算法初步&附录：跳跃表 知识点梳理- 2023届浙教版（2019）高考信息技术专题复习（选修）

附录：跳跃表（skiplist） 在之前的章节中，我们已经讨论过数组和链表在查找、插入、删除等场景中的算法效率，这里我们再做一个总结。 场景 数组 链表 查找 对分查找O(log2n) 顺序查找O(n) 插入、删除 数据移动O(n) 修改指针O(1) 但这里有个其实bug，在执行插入和删除前需要先查找到插入位置，也就是实际在执行插入或删除操作时，数组实际需要时间为O(log2n+n)=O(n)，链表需要时间为O(n+1)=O(n)。也就是说在插入和删除时，两者综合效率其实是一样的。 由上面的分析可知，链表在实际插入或删除过程中，大部分时间都消耗在了查找过程，我们可以借助对分思想优化链表的查找过程。具体操作如下： （1）对分的前提是数据有序，故第一步需要将链表有序化处理。 （2）二分通过与关键节点比较来缩小查找区间，故需要在原链表上建立一批关键节点。 如此我们就构建了一个名为跳跃表的数据结构。下面我们开始逐一展示跳跃表的使用方法。 1.查找数据过程 跳跃表基础仍是链表，故搜索过程与链表遍历类似，我们需要创建辅助指针 p = skiplist.head q = skiplist.head.nxet 以上用伪代码展示了p,q指针的关系，下面我们以key=6为例。 （1）p,q指针保持上述关系，从关键节点层开始查找 （2）比较key和q.data，若key<q.data，则p向下一层，否则p,q=q,q.next （3）重复（2）直到找到查找值，或已经不能在往下一层，程序结束。 2.插入数据过程 跳跃表的数据是有序排列的，故要求新数据插入后，跳跃表依然有序。这里以插入date=4为例。 （1）p,q指针保持一前一后关系，从关键节点层开始查找 （2）比较date和q.data，若key<q.data，则p往下一层，否则p,q=q,q.next （3）重复（2）直到p,q已经在原链表，并且p.data<date<q.data （4）修改p.next指向date，date.next指向q 3.二级索引 当原链表的数据量足够大时，一级关键节点的效率提升依然有限，这时可以考虑在一级索引的基础上建立二级索引。 当跳跃表具有多级索引时，新插入的值就要考虑是否需要提升为一级索引 因为跳跃表经过多次的插入和删除后，并不能保证每一级的索引都可以均匀分布，所以当新节点插入时，是否需要提升为上级索引是通过“抛硬币”的方式决定的。以上图为例，新节点插入到原链表后，假设“抛硬币”决定需要将其提升为一级索引。 然后再次“抛硬币”决定不需要提升为二级索引，插入结束。节点插入过程是“自下而上”。 4.删除节点 删除节点的查找过程，和上面一致，这里不再复述。下面我们以节点5的删除为例。 删除节点的过程是“自上而下”的过程，首先修改二级索引节点1的指针，接着修改一级索引节点3的指针，最后修改原链表节点4的指针。这里特别需要指出，当节点5删除后，二级索引只剩一个值，没有建立索引的意义，所以可以整层删除。 总结：跳跃表是一种经典的“空间换时间”的数据结构。通过消耗空间建立索引减少数据操作所需要的时间。 学科网（北京）股份有限公司 $