清华大学出版社 跳跃表 ERSITY PRESS 舍伍德型算法的设计思想还可用于设计高效的数据结构。 如果用有序链表来表示一个含有η个元素的有序集S,则在最坏 情况下,搜索S中一个元素需要Ω(η)计算时间。 提高有序链表效率的一个技巧是在有序链表的部分结点处增设 附加指针以提高其搜索性能。在增设附加指针的有序链表中搜 索一个元素时,可借助于附加指针跳过链表中若干结点,加快 搜索速度。这种增加了向前附加指针的有序链表称为跳跃表。 应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多 少指针完全采用随机化方法来确定。这使得跳跃表可在O(ognη) 平均时间内支持关于有序集的搜索、插入和删除等运算。 →2|*3|心++9+2 (b) 2|3|5|一+9239 跳跃表 •舍伍德型算法的设计思想还可用于设计高效的数据结构。 •如果用有序链表来表示一个含有n个元素的有序集S，则在最坏 情况下，搜索S中一个元素需要(n)计算时间。 •提高有序链表效率的一个技巧是在有序链表的部分结点处增设 附加指针以提高其搜索性能。在增设附加指针的有序链表中搜 索一个元素时，可借助于附加指针跳过链表中若干结点，加快 搜索速度。这种增加了向前附加指针的有序链表称为跳跃表。 •应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多 少指针完全采用随机化方法来确定。这使得跳跃表可在O(logn) 平均时间内支持关于有序集的搜索、插入和删除等运算