Access sequences and competitive ratio
As typically formulated, the online binary search tree problem involves search trees defined over a fixed key set . An ''access sequence'' is a sequence ... where each access belongs to the key set. Any particular algorithm for maintaining binary search trees (such as the splay tree algorithm orTranslation to a geometric point set
In the geometric view of the online binary search tree problem, an ''access sequence'' (sequence of searches performed on a binary search tree (BST) with a key set ) is mapped to the set of points , where the X-axis represents the key space and the Y-axis represents time; to which a set of touched nodes is added. By touched nodes we mean the following. Consider a BST access algorithm with a single pointer to a node in the tree. At the beginning of an access to a given key , this pointer is initialized to the root of the tree. Whenever the pointer moves to or is initialized to a node, we say that the node is touched. We represent a BST algorithm for a given input sequence by drawing a point for each item that gets touched. For example, assume the following BST on 4 nodes is given:Arborally satisfied point sets
Theorem
A point set containing the points is arborally satisfied if and only if it corresponds to a valid BST for the input sequence .Proof
First, prove that the point set for any valid BST algorithm is arborally satisfied. Consider points and , where is touched at time and is touched at time . Assume by symmetry that and . It needs to be shown that there exists a third point in the rectangle with corners as and . Also let denote the lowest common ancestor of nodes and right before time . There are a few cases: * If , then use the point , since must have been touched if was. * If , then the point can be used. * If neither of the above two cases hold, then must be an ancestor of right before time and be an ancestor of right before time . Then at some time , must have been rotated above , so the point can be used. Next, show the other direction: given an arborally satisfied point set, a valid BST corresponding to that point set can be constructed. Organize our BST into a treap which is organized in heap-order by next-touch-time. Note that next-touch-time has ties and is thus not uniquely defined, but this isn’t a problem as long as there is a way to break ties. When time reached, the nodes touched form a connected subtree at the top, by the heap ordering property. Now, assign new next-touch-times for this subtree, and rearrange it into a new local treap. If a pair of nodes, and , straddle the boundary between the touched and untouched part of the treap, then if is to be touched sooner than then is an unsatisfied rectangle because the leftmost such point would be the right child of , not .Corollary
Finding the best BST execution for the input sequence is equivalent to finding the minimum cardinality superset of points (that contains the input in geometric representation) that is arborally satisfied. The more general problem of finding the minimum cardinality arborally satisfied superset of a general set of input points (not limited to one input point per coordinate), is known to be NP-complete.Greedy algorithm
The following greedy algorithm constructs arborally satisfiable sets: * Sweep the point set with a horizontal line by increasing coordinate. * At time , place the minimal number of points at to make the point set up to arborally satisfied. This minimal set of points is uniquely defined: for any unsatisfied rectangle formed with in one corner, add the other corner at . The algorithm has been conjectured to be optimal within an additive term.Other results
The geometry of binary search trees has been used to provide an algorithm which is dynamically optimal if any binary search tree algorithm is dynamically optimal.See also
* Binary search algorithm * Tango trees * Splay trees * Self-balancing binary search tree * Optimal binary search tree * Interleave lower boundReferences
{{Reflist Binary trees Geometry