Geometry of binary search trees

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

The geometry of binary search trees is a way to think about how BSTs perform by turning a sequence of searches into points on a plane. The goal behind dynamic optimality is to have a BST algorithm that does almost as well for any search sequence as the best possible BST algorithm could do.

How the geometric view works
- Imagine keys 1 through n laid out on the x-axis and time steps 1, 2, 3, … on the y-axis. For each search of a key x at time t, plot a point at (x, t). As the BST algorithm processes the sequence, it “touches” certain nodes on the way to the target; every touched node adds its own point to the set.
- A set of points is called arborally satisfied if for every pair of points that are not in the same row or column, there is a third point inside the axis-aligned rectangle formed by those two points. If the touched points satisfy this property, they correspond to a valid BST execution for the given sequence.

Why arborally satisfied matters
- It’s true that any valid BST run yields an arborally satisfied set of points. When you touch two nodes at different times, the structure of the tree and the path between them guarantees there is a point inside the rectangle that reflects their relationship in the tree.
- Conversely, if you start with a set of points that is arborally satisfied, you can build a BST that realizes that point set. One way to do this is to organize the nodes into a treap whose heap order is given by each node’s next time it will be touched. As time moves forward, the nodes touched recently form a connected top part of the treap, and you can rearrange that part into a new local treap to continue.

Why this helps with finding the best BST
- The search for the best BST for a given sequence becomes the search for the smallest set of points (a superset of the original touched points) that is arborally satisfied. That is, you want to add as few extra points as needed so the rectangle condition holds.
- If you allow multiple points for the same time (more than one point with the same y-coordinate), the problem of finding the smallest arborally satisfied superset becomes NP-hard in general.

Greedy approach and its promise
- A simple greedy algorithm can be used to add points to ensure arboral satisfaction. It’s conjectured to be near-optimal, meaning it’s believed to be good up to an additive constant.
- This geometric framework has already inspired algorithms that would be dynamically optimal if any BST algorithm were dynamically optimal. In other words, proving dynamic optimality for BSTs would translate into proving optimality for a geometry-based method.

In short
- The geometric view reframes BST performance as a question about points in the plane and a rectangle-coverage property.
- Arborally satisfied point sets exactly capture valid BST executions, and building a BST from such a set can be done with a treap-based approach.
- The best BST problem becomes a question of minimally extending a point set to be arborally satisfied, a task that is easy to approximate with greedy methods but hard in general.
- This connection provides a path to understanding dynamic optimality and to designing algorithms that could be optimally competitive for online BST problems.