清华大学出版社 跳跃表 YERSITY PRESS 在一般情况下,给定一个含有n个元素的有序链表,可以将它改 造成一个完全跳跃表,使得每一个k级结点含有k+1个指针,分 别跳过2-1,2k1-1,,20-1个中间结点。第k级结点安排在 跳跃表的位置i2k处,≌0。这样就可以在时间o(ogn)内完成集合 成员的搜索运算。在一个完全跳跃表中,最高级的结点是gn 级结点。 °02|+3|+5|+13+17|19|2 旧,,,口啦目,: 完全跳跃表与完全二叉搜索树的情形非常类似。它虽然可以有 效地支持成员搜索运算,但不适应于集合动态变化的情况。集 元素的插入和删除运算会破坏完全跳跃表原有的平衡状态 影响后继元素搜索的效率。10 跳跃表 在一般情况下，给定一个含有n个元素的有序链表，可以将它改 造成一个完全跳跃表，使得每一个k级结点含有k+1个指针，分 别跳过2 k -1，2 k-1 -1，…，2 0 -1个中间结点。第i个k级结点安排在 跳跃表的位置i2k处，i0。这样就可以在时间O(logn)内完成集合 成员的搜索运算。在一个完全跳跃表中，最高级的结点是logn 级结点。 完全跳跃表与完全二叉搜索树的情形非常类似。它虽然可以有 效地支持成员搜索运算，但不适应于集合动态变化的情况。集 合元素的插入和删除运算会破坏完全跳跃表原有的平衡状态， 影响后继元素搜索的效率