Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01m326m482r
Title: Bounds on Accessing Sequences in Binary Search Trees
Authors: Zheng, Kai
Advisors: Tarjan, Robert E
Department: Mathematics
Class Year: 2021
Abstract: Binary search trees are perhaps the most important data structure in computer science and are well studied for their efficiency in facilitating a sequence of key accesses. Much of the work regarding binary search trees revolves around dynamic binary search trees which use rotations to restructure the tree between accesses. Dynamic binary search trees are often much more efficient than their static counterparts over long sequences of accesses as they can exploit structure in the access sequence. These trees do some extra work after each access to restructure in the hopes that future accesses become more efficient. If the future accesses are unknown however, it is not entirely clear how to optimize this tradeoff. In 1985, Sleator and Tarjan presented the splay tree which follows a simple online restructuring algorithm and postulated that this tree performs just as fast, to within a constant factor, as any other dynamic binary search tree on any access sequence – even those that know the entire sequence in advance. This is the famous dynamic optimality conjecture, which has been open for over 30 years. Thus far, most results towards this conjecture have only shown specific cases and corollaries. While other binary search trees have since been conjectured to satisfy the dynamic optimality conjecture as well, this thesis focuses mainly on splay trees and shows bounds for the cost of accessing certain well- structured sequences of keys. We also revisit the sequential access theorem for splay trees, showing a new bound, and generalize the result to a larger family of dynamic binary search trees. The performance of splay trees on well–structured sequences is considered central to the dynamic optimality conjecture as for most sequences, even the optimal dynamic binary search tree can only achieve logarithmic time per access, which splay trees are known to match for every access sequence. We conclude by proposing some heuristics for defining more well-structured sequences that splay trees should perform well on. These heuristics are related to pattern-avoidance and sorting with stacks – two topics that have are widely explored in combinatorics.
URI: http://arks.princeton.edu/ark:/88435/dsp01m326m482r
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2021

Files in This Item:
File Description SizeFormat 
ZHENG-KAI-THESIS.pdf585.32 kBAdobe PDF    Request a copy


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.