splay按中序遍历启发式合并复杂度证明

· · 个人记录

原论文

摘要

Step 1

证明splay是一棵Dynamic Finger Search Tree，访问的复杂度为log\ d(finger,a_i)。

leator and Tarjan introduced splay\ trees as a class of self-adjusting binary search trees supporting searches, insertions and deletions in amortized O(log\ n) time. That splay trees can be used as efficient finger search trees was later proved by Cole[17, 18]: Given an

access in a splay tree is $O(log\ d)$ where accesses include searches, insertions, and deletions. Notice that the statement only applies in the presence of one finger, which always points to the last accessed element.

Step 2

证明合并两棵大小分别为n,m(n \leq m)的Dynamic Finger Search Tree复杂度为O(n\ log\ \frac{m}{n})。

Optimal merging of two sets also follows as an application of finger search trees [28]. Assume that the two sequences are represented as finger search trees, and that we repeatedly insert the n elements from the shorter sequence into the larger sequence using a finger that moves monotonically from left to right. If the ith insertion advances the finger d_i positions, we have that the total work of performing the n finger searches and insertions is

由于将它们合并有n + m \choose n种中序，所以至少需log{n + m \choose n}次比较，即O(log{n + m \choose n}) = O(log(\frac{n+ m}{n} \times \frac{n + m - 1}{n - 1} \times \dots \times \frac{m + 1}{1})) = O(\sum_{i=1}^n\ log(1 + \frac{m}{i})) \geq O(n\ log\ \frac{m}{n})为合并它们的下界，所以这是归并两个有序列的最优方法。

Since sets can be represented as sorted sequences, the above merging algorithm gives immediately raise to optimal, i.e. O(log{n + m \choose n}) = O(n\ log\ \frac{m}{n}) time, algorithms for set union, intersection, and difference operations [28]. For a survey of data structures for set representations see [41].

Step 3

证明按任意顺序合并n个点，总复杂度为O(n\ log\ n). 画出merge tree，自底向上归纳可证将根为u的子树的叶子合并成一棵splay复杂度为log({siz_u}!), 所以根节点（即所有合并完成时）复杂度为O(log(n!)) = O(n\ log\ n).

Q.E.D.