New Analytical Methods for Online Binary Search Trees

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.

Department dc:contributor.department

Tietotekniikan laitos

Grantor dc:publisher

Aalto University

Year dc:date.issued

2023

Author dc:creator

• Jiamjitrak, Wanchote Po

Advisor dc:contributor.advisor

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

Contributors dc:contributor

• Aalto-yliopisto
• Aalto University

Language dc:language.iso

en

Repository record dc:identifier.uri

https://aaltodoc.aalto.fi/handle/123456789/120799

OAI record oai:identifier

https://aaltodoc.aalto.fi/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aaaltodoc.aalto.fi%3A123456789%2F120799