New Analytical Methods for Online Binary Search Trees

Thumbnail Image

Files

isbn9789526412832.pdf (1.76 MB)
Errata_wanchote.pdf (66.99 KB)

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Doctoral thesis (article-based) | Defence date: 2023-05-29
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2023

Department

Tietotekniikan laitos
Department of Computer Science

Major/Subject

Mcode

Degree programme

Language

en

Pages

112

Series

Aalto University publication series DOCTORAL THESES, 77/2023

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.

Description

Supervising professor

Chalermsook, Parinya, Asst. Prof., Aalto University, Department of Computer Science, Finland

Thesis advisor

Chalermsook, Parinya, Asst. Prof., Aalto University, Department of Computer Science, Finland

Keywords

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

Other note

Citation

Permanent link to this item

https://urn.fi/URN:ISBN:978-952-64-1283-2

Collections

[diss] Perustieteiden korkeakoulu / SCI