| Abstract |
In Chapter 1, Introduction: The Searching Problem, we present a concise history of the searching problem, from the original divide-and-conquer, known intuitevely even to children, up to the formulation of contemporary concepts such as amortized analysis and competitiveness. Our own work focuses on the situations in which we can do better than classical binary search trees, namely in biased searching, when balanced trees lose because of their over-balancedness. The classical answer to this problem, biased search trees, is clearly of little practical use because of the strict assumptions made. We present the reforms of Sleator and Tarjans splay technique and extensions by Subramanian and by Sherk. In this context we summarize our main results: (1) a generalization of almost all aspects of the results of Subramanian together with a substantial weaking of the conditions required for a self-adjustment scheme to exhibit optimality in several biased situations (explained fully in Chapter 2) and (2) our refutation of Sherks conjecture (explained fully in Chapter 3). In Chapter 2, Multi-way Splaying: A General Theory and Calculus, we develop a general theory of self-adjusting tree-based data structures. First we decouple the details of self-adjustment from the underlying invariant conditions necessary for the data structure to operate as designed. This provides the ability to impose self-adjustment on almost any tree-based data structure, guaranteeing logN performance in schemes other than search trees. We then present in detail the strict set of conditions required by Subramanians proof, and how these can be greatly reduced. The impression left at the end is that the vast majority of template sets for self-adjustment satisfy our criteria, and thus the end-user has a great degree of freedom to choose a self-adjustment scheme that respects the invariant condition required. In Chapter 3, The Limitations of Multi-Way Self-Adjusting Schemata, we refute Sherks conjecture that the k-splay technique for self-adjustment achieves O(logkN)nodes visited, amortized. With respect to classical data structures (non-self-adjusting) we may choose B-trees over binary trees, because the number of nodes visited is reduced by a factor of log2k. Sherks conjecture is that k-splay provides an analogous reduction in the context of self-adjustment. We demonstrate a family of degree-k trees for which k-splay behaves as if it were operating on a binary tree. Besides the lower bound for k-splay implied by the existence of this family of trees, they have other interesting properties which we explore. In the final chapter, Chapter 4, Summary and Conclusions, we summarize our work, presenting several possible directions for further research.
|
Collections
