Back to search

University of Crete (UOC)

Multi-way self-adjusting data structures: a general theory and some limitations

Abstract

dc:description

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 Tarjan’s 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 Sherk’s conjecture (explained fully in Chapter 3). In Chapter 2, “Multi-way Splaying: A General Theory and Calculus,” we develop a general theory of selfadjusting 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 performance in schemes other than search trees. We then present in detail the strict set of conditions required by Subramanian’s 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 selfadjustment scheme that respects the invariant condition required. In Chapter 3, “The Limitations of Multi-Way Self-Adjusting Schemata,” we refute Sherk’s conjecture that the -splay technique for self-adjustment achieves 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 . Sherk’s conjecture is that -splay provides an analogous reduction in the context of self-adjustment. We demonstrate a family of degree- trees for which -splay behaves as if it were operating on a binary tree. Besides the lower bound for -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.

Degree

thesis:*
Grantor dc:publisher
University of Crete (UOC)
Year dc:date
2001

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • McClurkin, David James

Subjects

dc:subject × 4

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/30916

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

McClurkin, David James. Multi-way self-adjusting data structures: a general theory and some limitations. University of Crete (UOC), 2001. http://hdl.handle.net/10442/hedi/30916