返回主题:存储常用数据结构

知识卡片

普通读书笔记卡 · 3622.d

跳表用额外指针加速查找

理解等级:中级

跳表在有序链表上增加多层跨越指针,让查找、插入和删除能跳过大量节点;它是平衡搜索树的替代结构,字典操作的期望时间为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.