数据结构中Splay树的最优性
动态最优猜想
除了成熟的八角树性能保证外，还有一个未经证实的猜想引起了人们的极大兴趣。动态最优猜想表示该猜想。让任何二元搜索树算法（例如B）通过以d(y)+1的代价遍历从根到y的路径来访问元素y，并且两次访问之间的算法可以以1的代价在树中进行任何旋转回转。令B为B执行访问序列的代价。然后，八叉树执行相同访问的成本为O [n + B(s)]。
关于动态最优性猜想的众多推论尚未得到证实
遍历猜想等元素包含在两个展开树t1和t2中。假设通过按顺序（即深度优先搜索顺序）访问t2中的元素而获得的序列为s。在t1上执行访问序列s的全部成本为O(n)。
定义了Deque Conjecture和p个双端队列操作（推，弹出，注入，弹出）的序列。则在展开树上执行s序列的成本为O（p + n）。
分裂猜想可以是展开树元素的任何排列。则按s顺序删除元素的成本为O(n)。
以上是 数据结构中Splay树的最优性 的全部内容， 来源链接： utcz.com/z/321931.html
