Tango tree

A Tango tree is an online binary search tree that is $O{\Bigl (}\log \log(n){\Bigr )}$-competitive proposed by Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Patrascu in 2004.

Overview

Tango trees were designed to surpass the usual $O{\Bigl (}\log(n){\Bigr )}$ binary search tree cost of operations. They perform basic operations such as searches in $O{\Bigl (}\log \log(n){\Bigr )}$ time. This optimization is achieved dynamically by adjusting the search tree structure after each search. They are similar in their dynamic behaviour to other types of structure like a Splay tree however the competitive ratio is dramatically improved.

The approach is similar to the Greedy BST algorithm that while searching for an element rearranges the nodes on the search path to minimize the cost of future searches.

For Tango Trees the approach is a classic divide and conquer approach combined with a bring to top approach.

The main divide and conquer idea behind this data structure is to extract from the original tree a number of virtual smaller subtrees all with a normal O(log number of subtree elements) cost of access. These subtrees are dynamically balanced to offer the usual $O{\Bigl (}\log(n){\Bigr )}$ performance for data retrieval.

The bring to top approach is not done at the node level as much as at the subtree level which further improve competitiveness. Once the original tree has been adjusted to include a collection of these subtrees, it is possible to greatly improve the cost of access of these subtrees. Both the Tango tree and these subtrees are a type of Self-balancing binary search tree.

Tango tree achieves this outstanding competitive ratio by using a combination of augmentation of attributes in the data structure, a more elaborated algorithm and the use of other type of trees for some of its structure.

Example

Fig. 1 An example of a Tango Tree

---

Similar Data Structures

Red Black tree introduced by Bayer in 1972 and have a $O{\Bigl (}\log(n){\Bigr )}$ competitive ratio
Splay tree Introduced by Sleator and Tarjan in 1985 and have a $O{\Bigl (}\log(n){\Bigr )}$ competitive ratio
AVL tree Introduced by Adelson and Landis in 1962 and have a $O{\Bigl (}\log(n){\Bigr )}$ competitive ratio
Multi-Splay Tree Introduced by Sleator and Wang in 2006 and have a $O{\Bigl (}\log \log(n){\Bigr )}$ competitive ratio

Advantages

Tango Trees offer unsurpassed competitive ratio retrieval for online data. Online data means that operations that are not known in advance before the data structure is created. Outstanding search performance for a Tango tree relies on the fact that accessing nodes constantly updates the structure of the search trees. That way the searches are rerouted to searches in much shallower balanced trees. Obviously significantly higher access time constitutes an advantage for nearly all practical applications that offer searches as a use case. Dictionary searches like telephone directory search would be just one of the possible an examples.

Disadvantages

The Tango tree focuses on data searches on static data structures, and does not support deletions or insertions, so it might not be appropriate in every situation. The Tango tree uses augmentation, meaning storing more data in a node than in a node of a plain binary search tree. Tango trees use $O{\Bigl (}\log \log(n){\Bigr )}$ bits. Although that is not a significant increase, it results in a bigger memory footprint. It is a complex algorithm to implement like for instance [splay tree], and it also makes use rarely used operations of Red-Black Tree. Tango trees change when they are accessed in a 'read-only' manner (i.e. by find operations). This complicates the use of Tango trees in a multi-threaded environment.

Terminology and Concepts

There are several types of trees besides the Red-Black trees (RB) used as a base for all Tree structures:

Reference Trees
Tango Trees
Auxiliary Trees

As all trees are derived from RB trees, they are also [Binary Search Trees] with all their inherent behaviour. Auxiliary trees can be considered sub-trees of the Tango Tree. Tango Trees are the actual employed trees while in production mode. Reference Trees are used only initial set-up and for illustration of the concepts. Any search in the Reference Tree creates a path from root to the searched node. We call that a Preferred Path and the Preferred Child attribute specific to the Reference Tree indicates if the preferred path of a node goes to the left or right child if any. A Preferred Path is determined by the longest path formed by preferred children. Any new search in the Reference Tree will carve new paths and modify the existing paths. Correspondingly, the preferred children change too. Any switch from right to left or vice versa is called an Interleave. Interleaves changes are the basis for analysis of expected performance. Fig. 2,3 and 1 examples of Reference Tree, Auxiliary tree and Tango Tree, respectively.

Fig. 2 Reference Tree example with Preferred Paths in dark red

Fig. 3 Example of Auxiliary Tree formed from a Preferred Path.

Operations

As we stated Tango Trees are static so they support only searches. That also means that there is a construction phase where the elements are inserted in the Tango Tree. That start-up cost and any search performance during the construction period is not considered part of the operational part of Tango trees therefor the performance is not $O{\Bigl (}\log \log(n){\Bigr )}$ competitive. The outstanding idea behind Tango Trees is to collect the nodes belonging to a Preferred Path as a balanced tree of height O(log log n) called auxiliary tree and then assemble them in a tree of trees where higher trees contain the mostly accessed preferred paths elements.

Search

To search for a node x in a Tango tree, we search for the element in the collection of Auxiliary Trees that make up the Tango Tree like in any ordinary binary search tree. Simultaneously we adjust the corresponding affected Auxiliary Trees in the Tango Tree. This will preserve the ideal structure that will give us this unprecedented search performance. We could achieve this ideal structure by updating the Reference Tree P after every search and recreating the Tango tree however this would be very expensive and nonperforming. The reasons why such a structure is $O{\Bigl (}\log \log(n){\Bigr )}$ competitive is explained in the Analysis There is a direct way to update the structure and that is shown in the [Algorithm]

Tango Tree Life Cycle

The main phases are Construction and Operation

Construction First create the reference tree and insert the desired data in it. Update the attributes of depth for each node After this phase the data and the value of the depth for the nodes will remain unchanged. Let's call that field d for further reference and understand that it always refers to the Reference tree not to the Tango tree as that can cause confusions. While in principle the reference tree can be any balanced tree that is augmented with the depth of each node in the tree the TODO [Demaine et al. 2004] uses [red-black tree]. Secondly we will perform some warm-up searches with the goal to create a decent distribution of Preferred Paths in the Reference Tree. Remember there is no Tango tree and all this is done on line. This means that performance is not critical at this point.

[Construction Algorithms] explains this phase.

After this begins the phase of collecting the preferred paths. Out of each Preferred Path we create a new Auxiliary Tree which is just an ordinary RedBlack Tree where the nodes inherit the value of field d. That value will stay unchanged forever because it stays with the node even if the node is moved in the trees. There is no Tango Tree at this point. We add auxiliary trees such a way that the largest one is the top of a tree and the rest and 'hung' below it. This way we effectively create a forrest where each tree is an Auxilary tree.

See

Example of a Tango Tree

where the roots of the composing auxiliary tree are depicted by magenta nodes. It after this step that the Tango tree becomes operational. The

[Operation Algorithms] explain this phase

Operation

The operation phase is the main phase where we perform searches in the Tango tree.

Data Augumentation

Reference Tree augmentation

Besides the regular RB Tree fields we introduce two more fields: isPreferredChild representing the direction the last search traversing the node took. It could be either Boolean or a pointer to another node. In the figures it's represented by a red line between a node and its preferred child. d representing the depth of the node in the Reference Tree. See value of d in Fig 3.

Tango Tree Augmentation

For each nodes in Tango or Auxiliary Tree we also introduce several new fields:

isRoot that will be false for all nodes except for the root.
This is depicted in magenta for nodes where isRoot is true

maxD that is the Maximum value of d for all the children of the node
. This is depicted as MD in the figures. For some nodes this value is undefined and the field is not depicted in the figure

minD that is the Minimum value of d for all the children of the node
This is depicted as mD in the figures. For some nodes this value is undefined and the field is not depicted in the figure

isRoot, maxD and minD will change in time when nodes are moved around in the structure.

Algorithms

The main task in a Tango Tree is to maintain an 'ideal' structure mirroring changes that occur in the reference tree. As recreating the Tango tree form the reference tree would not be performing the algorithms will have only use and modify the Tango tree. That means that after the construction phase the reference tree could and should be destroyed. After this we would refer to it a s virtual meaning 'as if it existed'.

Analysis

Here are some elements necessary to understand why the Tango Tree achieve such an amazing performance and become $O{\Bigl (}\log \log(n){\Bigr )}$ competitive.

Wilber's 1st Lower Bound [Wil89]

Fix an arbitrary static lower bound tree P with no relation to the actual BST T, but over the same keys. In the application that we consider, P is a perfect binary tree. For each node y in P, we label each access X1 L if key X1 is in y's left subtree in P, R if key X1 is in y's right subtree in P, or leave it blank if otherwise. For each y, we count the number of interleaves (the number of alterations) between accesses to the left and right subtrees: interleave(y)= ? of alternations L ? R.

Wilber's 1st Lower Bound [Wil89] states that the total number of interleaves is a lower bound for all BST data structures serving the access sequence x. The lower bound tree P must remain static.

Proof.

File:Wilber 1 bound picture.jpg

We define the transition point of y in P to be the highest node z in the BST T such

that the root-to-z path in T includes a node from the left and right subtrees if y in P. Observe that the transition point is well defined, and does not change until we touch z. In addition, the transition point is unique for every node y.

Lemma 1

The running time of an access xi is $O{\Bigl (}(k+1)(1+lglg(n)){\Bigr )}$, where k is the number of nodes whose preferred child changes during access xi.

Lemma 2

The number of nodes whose preferred child changes from left to right or from right to left during an access xi is equal to the interleave bound ${\Bigl (}IBi(X{\Bigr )}$ of access xi.

Theorem 1

The running time of the Tango BST on an sequence X of m accesses over the universe ${1,2,...,n}.$ is $O{\Bigl (}(OPT(X)+n)(1+lglg(n)){\Bigr )}$ where $OPT{\Bigl (}X{\Bigr )}$ is the cost of the offline optimal BST servicing X.

Corollary 1.1

When m = (n), the running time of the Tango BST is

$O{\Bigl (}OPT(X)(1+lglg(n)){\Bigr )}$

-BST model

-Comparativeness def
-Splay configured

- PP ? TANGO connection

- If no reconfiguring cost how much

- How do you do reconfiguring in kloglog u

Back to BST model

- Given sequence of accesses

$X=<X1,X2,...,Xm>$

What would it mean to say that some BST execute this sequence optimally that is best possible
- If we are allowed to look at X ? D off-line BSTs
- If not ? on-line (dynamic) BST

Question: Is the dy-BST that executes X as well as best off-line BST for X
Relationship (or ? there of) to entropy y

• Why does the fact that splay trees met entropy bound does not answer the above question?

SET UP:
Assume over $[n]={1,2,....n}$
Access sequence $X=<X1,X2,...Xm>$€[n]^m
-$O{\Bigl (}\log \log(n){\Bigr )}$ must process the sequence in order
MODEL: - Search from the root to X_i and then before some arbitrary num of rotation

COST: num nodes in search path + num of rotations


DEF: OPT(x): smallest cost over all (off-line) BST i.e length of the shortest sequence that executes X
COMPETITIVENESS
BST runs X in K.OPT(X)?K competitive
if K cost ? DYNAMICALUU

- Splay configured to be OPTIMA BST

• But in fact not known if such BST even exists.
  
• What is comparativeness of BALANCES STATIC BST?
  

Trivially (m log n)

- one of the most important or at least most frustrating O in DS_i:

• Is there O(₁) competitive BST
  

- until recently only trivially O(log) Comparativeness (obtained by balances BST) was best known
Trivial upper bound for balanced BST was obtained lower bound O(m).
Need better LB.

LOWER BOUND
Trivial lower bound O(m)

• Wilber interleave bound W2

Defined with respect to arbitrary (but fixed) tree P. take P? perfect BST

• left region $L(y)=y+itsleftsubtree$
  
• right region $R(y)=itsrightsubtree$
  

the amount of interleaving through y: $I(y)$

• $L(7)={7,6}$
  
• $R(7)={9,8}$
  

e.g.
X=<3,1,4,1,5,9,2,6,5,3,5,8,9,7,3, 2,3,8,4,6,L7>
x⁷=<9,6,8,9,78,6,7>
I(y)=5

INTERLEAVE BOUND: W2

File:Diagram05.jpg

for any access tag X and any ref tree P examples
EXAMPLES SCANNING

File:Diagram07.jpg

? OPT(X)=O(m)
achievable by SPLAY

In fact: think of what DYNAMIC FINGER says
EXAMPLE RANDOM X

|B(randomX)=O(mlog)
that is highest W2 can give
O(mlog)? worst case

IDEA FOR TANGO (good BST)
Simulate interleave bound
DIFFERENT VIEW OF INTERLEAVE BOUND
PREFERRED PATH
node if: its preferred child indicates
if L(y) or R(y) contains the latest accessed element accessed by element in X
[[ Image:1 Reference tree after inserting all the elements and before any searches, d is the depth in tree, Md is the Max depth of a node considering all it's subchildren. JPG| frame | center | sizepx |Reference Tree after inserting all the elements and before any searches. d is the depth in tree. Md is the Max depth of a node considering all it's subchildren]]

Reference Tree after first search for element 17

Reference Tree after first 2 searches for 17 and 7

Reference Tree after performing searches for 17,7,1,18,23,31,27,13,9

preferred paths after accesses:
X=<7,1,18,23,31,2713,9...>
-since reference tree is balanced high of ? per. path O(logn)

Back to interleave
|B(X)=total ? times
the preferred paths changes as we execute X

IDEA FOR BST (tango)
Simulate IB(x)
Tango: after every access to element in X, preferred paths, in P are redefined.
WANT TANGO after EVERY ACCESS
to look as follows

top AUXILIARY TBE preferred path at balanced BST

second level Preferred Paths

third level etc

Reference Tree P with Preferred Paths marked in red after performing all warm-up searches for elements 17,7,1,18,23,31,27,13,9,20 searches

NOTICE: because preferred paths are PATHS, all the children subpaths form consecutive keys in[n]
thus the subtree hang in different places on top path

• height of every path representation in TANGO is $O{\Bigl (}\log \log(n){\Bigr )}$ since P has O(log) vertices
  

tango of previous example

7 Second formed Auxiliary Tree formed from a Preferred Path from the previously searched Reference Tree.

Last Auxiliary Tree to be added to the Tango Tree, note that nodes that are not part of a preferred path become one node Auxiliary Trees.

9 Tango Tree based on previous Reference Tree where the first 2 Auxiliary Trees were added.

Tango Tree generated from the reference Tree P after the last warm-up search for for element 20, Nodes in pink are roots of Auxiliary Trees.

IMAGINING that after every access the TANGO looks the way we want (that is as defined above) and that we get that MAGICALLY FOR TREE. So we are not concerned how we get from Tango T_i to Tango T_i+1 after accessing X_i+1.

Given that for tree

How much would just accesses that is searches, of X COST

X=<X₁,X₂,...X_i,...X_m> how much is access to X_i in T_i O(K_i.loglogn)

number of times preferred child changes while searching for X_i

thus access to the whole X costs

File:Diagram03.jpg

cost searches = O(IB_(x).loglogn)=O(opt(x),logn) given transformation for tree

REST OF CLASS

System accessing Xi how do we transform T_i to T_i+1
spending O(Klglogn) time

(that is same time as accessing Xi)

We would then need following operations on Auxiliary Trees

• search
  
• cutting Aux Tree in 2
  

1 containing all elements at dept= d in P

2-containing all elements at dept > d in P

• joining 2 Aux Trees that store disjoint paths when the bottom of one
  

Each preferred path as Auxiliary Tree -> RB tree

3 additional info in every node of AUX Tree

• 1. own depth in P
  
• 2. max depth in its subtree
  
• 3. node is marked if root of AUX Tree
  

join + cut can be achieved by standard RB tree operation

- split at x

- concatenate two RB trees

- HOW TO DO CUT IN TANGO

Reference Tree after inserting all the elements and before any searches. d is the depth in tree. Md is the Max depth of a node considering all it's subchildren

Remember the Reference Tree after warm-up search for 20 looked like this

If after that we would do a search for 30 it would have looked like this, where the path 16,24,20,22 and 23 becoming 16 , 24, 28, 30 therefore loosing 20, 22 and 23

Tango Tree after search for 20 with the Auxiliary tree corresponding

Tango Tree after search for 20 with the Auxiliary tree corresponding to the preferred path that will change after searching for 30 and cut points l, l, l prime and r prime marked

- You can find l in AUX by going to left child as long as its subtree contains an element of greater depth then l

-similarly you can find r

l' = predecessor of l
r'= successor of r

CUT

Implementation Tango Cut using RedBlack Split

Tango Join Algorithm as a Sequence of Tree Split Un-mark and Concatenate RP Operations

- cut of D (by concatenating its root)

- merge c,l,r,& E all done in $O{\Bigl (}\log \log(n){\Bigr )}$ time

Bibliography

• Erik D. Demaine, Dion Harmon, John Iacono and Mihai Patrascu, Dynamic optimality - almost [competitive online binary search tree], In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pages 484–490, Rome, Italy, October 2004, http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=9430

• Allen, Brian; and Munro, Ian (1978), "Self-organizing search trees", Journal of the ACM 25 (4): 526–535, doi:10.1145/322092.322094
• Knuth, Donald. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Page 478 of section 6.2.3.

External links

• Dynamic Optimality-Almost