On Dynamic Optimality in Binary Search Tree Algorithms

摘要

The binary search tree is the most well studied data structure in computer science. Sleator and Tarjan introduced the splay tree in 1985, and showed that its amortized performance matches that of any of the other known binary search tree algorithms. Sleator and Tarjan made an even stronger claim concerning splay trees. They conjecture that splay trees are dynamically optimal; i.e., that the cost of performing any sequence of searches using splaying is at most a constant multiple of the cost of performing those same searches using any possible binary search tree algorithm. This conjecture remains an open problem. We examine the properties of dynamically optimal binary search tree algorithms. We show that, without loss of generality, all such algorithms can be shown to conform to a limited range of behavior while maintaining their efficiency.