Tango tree
A tango tree is a type of binary search tree proposed by Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pătrașcu in 2004.
competitive ratio relative to the offline optimal binary search tree, while only using
This equals the length of the longest path, and therefore the size of the largest auxiliary tree.
Note that if the most recently accessed node of T is p itself, then l is the preferred child by definition.
For each non-leaf node n in a preferred path P, it has a non-preferred child c, which is the root of a new auxiliary tree.
If the auxiliary tree doesn't contain the desired element, the search terminates on the parent of the root of the subtree containing the desired element (the beginning of another preferred path), so we simply proceed by searching the auxiliary tree for that preferred path, and so forth.
In order to maintain the structure of the tango tree (auxiliary trees correspond to preferred paths), we must do some updating work whenever preferred children change as a result of searches.
In order to do this efficiently, we'll define cut and join operations on our auxiliary trees.
Our join operation will combine two auxiliary trees as long as they have the property that the top node of one (in the reference tree) is a child of the bottom node of the other (essentially, that the corresponding preferred paths can be concatenated).
To find a lower bound on the work done by the optimal offline binary search tree, we again use the notion of preferred children.
The total number of switches (summed over all nodes) gives an asymptotic lower bound on the work done by any binary search tree algorithm on the given access sequence.
The total cost is divided into two parts, searching for the element, and updating the structure of the tango tree to maintain the proper invariants (switching preferred children and re-arranging preferred paths).
To see that the searching (not updating) fits in this bound, simply note that every time an auxiliary tree search is unsuccessful and we have to move to the next auxiliary tree, that results in a preferred child switch (since the parent preferred path now switches directions to join the child preferred path).
The update cost fits within this bound as well, because we only have to perform one cut and one join for every visited auxiliary tree.
A single cut or join operation takes only a constant number of searches, splits, and concatenates, each of which takes logarithmic time in the size of the auxiliary tree, so our update cost is
-competitive, because the work done by the optimal offline binary search tree is at least linear in k (the total number of preferred child switches), and the work done by the tango tree is at most
