Carleton University - School of Computer Science Honours Project
Summer 2020
Geometric Representation of Binary Search Trees
Richard St john
SCS Honours Project Image
ABSTRACT
In this report, we examine the geometric representation of binary search tree executions. This geometric view has been a useful tool in the ongoing search for a dynamically optimal binary search tree. We give a detailed explanation, and proof, of how points in the plane with one geometric property, arboreal satisfaction, can represent the execution and associated cost of a binary search tree. We also describe Wilbur’s lower bounds in their original form and their geometric equivalent form and prove this equivalence rigorously. Finally, we created a program to simulate binary search tree access sequences and represent these in both the traditional binary search tree view and the geometric view.