New Analytical Methods for Online Binary Search Trees

Research output: ThesisDoctoral ThesisCollection of Articles

Abstract

This thesis aims to analyze the costs of various binary search tree (BST) algorithms. BST is one of the most fundamental data structures. The long-standing dynamic optimality conjecture states that there exists an online self-adjusting BST algorithm such that, starting with any initial tree, its access cost on any sequence X is O(OPT(X)+n) where OPT(X) is the cost of serving X on an offline optimal algorithm and n is the number of keys. Despite attempts from many groups of researchers, we believe that it is still far from being proven, primarily due to the lack of systematic techniques on the analytical side of algorithms. To address this, we explore the power of two analyzing methods in the context of binary search trees: potential functions and extremal combinatorics. In the first part, we focus on the potential function method, which is widely used but mysterious in how it works. We introduce new charging schemes based on inversion counting, a popular potential function for list updates that has not been used in a BST context. An inversion potential function is arguably the most natural potential function, as it captures the difference between the states of two different algorithms. We illustrate our techniques in the context of both list updates and BSTs: (1) systematically deriving many known list update results and (2) unifying, strengthening, and deriving new bounds for BSTs. In the second part, we explore and extend the use of extremal combinatorics in an amortized analysis of BSTs. The technique exploits the specific structures of the input of BSTs. This method encodes the execution log of BSTs in the form of a matrix and applies powerful theorems from forbidden matrix literature to upper-bound the cost. We propose an extra preprocessing step that decomposes the matrix into several simpler submatrices. We show the applications of the BST Greedy algorithm, one of the most promising candidates for being dynamically optimal, including deriving improved bounds for long-standing conjectures such as preorder traversal, postorder traversal, and path conjectures.
Translated title of the contributionNew Analytical Methods for Online Binary Search Trees
Original languageEnglish
QualificationDoctor's degree
Awarding Institution
  • Aalto University
Supervisors/Advisors
  • Chalermsook, Parinya, Supervising Professor
  • Chalermsook, Parinya, Thesis Advisor
Publisher
Print ISBNs978-952-64-1282-5
Electronic ISBNs978-952-64-1283-2
Publication statusPublished - 2023
MoE publication typeG5 Doctoral dissertation (article)

Keywords

  • online algorithms
  • data structures
  • binary search trees
  • list updates
  • extremal combinatorics

Fingerprint

Dive into the research topics of 'New Analytical Methods for Online Binary Search Trees'. Together they form a unique fingerprint.

Cite this