数据结构中 Splay 树的最优性

动态最优性猜想

除了对 Splay 树的已证明的性能保证外，还有一个尚未证实的猜想备受关注。动态最优性猜想指的就是这个猜想。令 B 为任意二叉搜索树算法，该算法访问元素 y 时的开销为 d(y) + 1，并在访问之间以每旋转一次 1 的开销进行树中的任何旋转操作。记 B(s) 为 B 执行访问序列 s 时的开销，则 Splay 树执行相同访问时的开销为 O[n+B(s)]。

动态最优性猜想有很多推论，但这些推论仍然未得到证明

遍历猜想两棵 Splay 树 t1 和 t2 包含的相同元素。将通过前序（即深度优先搜索顺序）访问 t2 中元素而获得的序列假设为 s。在 t1 上执行访问序列 s 时的全部开销为 O(n)。

双端队列猜想定义一系列 s 的 p 个双端队列操作（进栈、出栈、插入、弹出）。则在 Splay 树上执行序列 s 的开销为 O(p+n)。

分离猜想令 s 为 Splay 树元素的任意排列。则按顺序 s 删除元素的开销为 O(n)。

Arnab Chakraborty

更新时间： 07-01-2020

95 视图

开启你的事业

完成课程认证

开始