Carleton University - School of Computer Science Honours Project
Summer 2020
Geometric Representation of Binary Search Trees
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.