Otimalidade dinâmica: um survey

Abstract

Binary Search Trees (BSTs) belong to the classic data structures within Computer Science and, despite their simplicity, have many open questions after decades of research. The main open question about BSTs is the following: “What is the best Binary Search Tree over any given search sequence of elements in the tree?”. In 1983, the Splay Tree was proposed and conjectured that its cost to perform any search sequence S on this BST is as good, asymptotically, as the lowest possible cost, denoted by OPT(S). This is the famous conjecture of dynamic optimality, where any BST that performs any search sequence S with cost O(OPT(S)) is said to be dynamically optimal. Since the conjecture was proposed, there have been many attempts to prove it, but it has not yet been proven that the Splay Tree, or any another BST, is dynamically optimal. The best known cost is O(loglogn ·OPT(S)), where n is the number of nodes in the tree, from the Tango Tree Multi-Splay Tree and Chain-Splay Tree. In 2009, a point model in the Cartesian plane was proposed, which is equivalent to the search problem in a BST. This result is surprising, as it represents a visual way of executing a BST algorithm on a search sequence. Finally, this dissertation is a survey of the literature on dynamic optimality, where we gather the main results related to the problem.