The Dynamic Optimality Conjecture states that given any access sequence, the cost of splay trees applied on the access sequence is within a constant factor c of any other binary search tree (BST) for processing that access sequence. Despite more than 3 decades of research, the Dynamic Optimality Conjecture of BST is yet solved. After Wilber's theorem with rotations on BST been extended to unordered model, researchers have showed that dynamic optimality is unattainable in this extended model. However, when applied to tournament tree, a related but different unordered tree model, the prior existing proof is not applicable.
In this talk, we extend the work and explore the possibility of dynamic optimality upon tournament trees. After giving out the prerequisite theorem, we will discuss the framework design and proof strategy. Followed by the details of on-line and off-line implementation, along with applying encoding methods on augmented root-sequence. We demonstrated our result by constructing an adversary that generates access request sequences to elude efficient On-Line implementation while admitting efficient Off-Line implementation. We'll conclude the work and indicate our further research topic at last.