知识卡片
跳表用额外指针加速查找
跳表在有序链表上增加多层跨越指针,让查找、插入和删除能跳过大量节点;它是平衡搜索树的替代结构,字典操作的期望时间为O(log n),但不提供同样的确定性最坏界。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第13章 红黑树 · 查看原书依据
A skip list is a linked list that is augmented with a number of additional pointers. Each dictionary operation runs in O(lg n) expected time on a skip list of n items.
参考来源
- 位置:《算法导论(第4版)》第13章《红黑树》章注(OEBPS/chapter013.xhtml,文本字符[55000,56375))。
- 结论依据:章注给出跳表的链表加指针结构及O(log n)期望字典操作;最坏界不同是对“期望”条件的边界解释。
- 原始内容:A skip list is a linked list that is augmented with a number of additional pointers. Each dictionary operation runs in O (lg n ) expected time on a skip list of n items.