数据结构-高级搜索树

Splay

Splay，

总结

• 无需记录高度和平衡因子，编程实现简单
• 均摊复杂度为 $O(\log n)$
• 局部性强时效率更高，假设多次访问 $k$ 个数据，连续的 $m$ 次查找只需 $O(m\log k+n\log n)$ 时间，均摊每次 $O(\log k)$
• 若反复顺序地访问一个子集，均摊成本仅为常数
• 可能出现单次最坏情况，效率降为 $O(n)$，不适用于瞬时效率敏感的场合

Link to original

B 树

B 树，理解红黑树的基础，简单理解为多层节点合并为一个超级节点，在大规模数据处理中可以减少 I/O 次数

红黑树

红黑树，是一种特殊的 BST，有以下一些优势

优势

并发性

并发操作的主要时间瓶颈在 lock & unlock 操作， 耗时取决于结构变化处数量：

• Splay：最坏 $O(n)$
• AVL：insert $O(1)$，remove $O(\log n)$
• 红黑树：$O(1)$

持久性

支持对历史版本的访问。 蛮力实现：空间复杂度 $O(nh)$ 能否将空间复杂度控制在 $O(n+h\log n)$ 内？

Link to original

跳表

跳表，一种带随机性的数据结构，通过随机来控制期望查询次数，期望时间复杂度为 $O(\log n)$