User:Tango tree

This is not a Wikipedia article: It is an individual user's work-in-progress page, and may be incomplete and/or unreliable. For guidance on developing this draft, see Wikipedia:So you made a userspace draft.

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL
Easy tools: Citation bot (help) | Advanced: Fix bare URLs
This page was last edited by Qwerfjkl (bot) (talk | contribs) 2 years ago. (Update timer)

Finished writing a draft article? Are you ready to request an experienced editor review it for possible inclusion in Wikipedia? Submit your draft for review!

This user page may require cleanup to meet Wikipedia's quality standards. No cleanup reason has been specified. Please help improve this user page if you can; the talk page may contain suggestions.

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[edit]

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[edit]

Similar Data Structures[edit]

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[edit]

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[edit]

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 of 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.
It is believed that Tango Tree would work in a practical situation where a very large data set with strong spatial and temporal coherence fits in the memory.

Terminology and Concepts[edit]

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

Reference Trees[edit]

Example of reference tree:

Fig. 2 Reference tree and preferred paths

Tango Trees[edit]

See Fig 1 for an example of Tango tree

Auxiliary Trees[edit]

Example of auxiliary tree:

As all trees are derived from RB trees so 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.

Operations[edit]

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[edit]

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[edit]

The main phases are Construction and Operation

Construction[edit]

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.

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 Fig. 1 where the roots of the composing auxiliary tree are depicted by magenta nodes. It after this step that the Tango tree becomes operational. See [Construction Algorithms And Pseudo-code] for main algorithms And pseudo-code.

Operation[edit]

The operation phase is the main phase where we perform searches in the Tango tree. See [Operation Algorithms And Pseudo-code] for main algorithms And pseudo-code.

Data Augmentation[edit]

Reference Tree augmentation[edit]

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[edit]

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[edit]

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 as virtual meaning 'as if it existed'. As described in [Demaine et al. 2004], the main goal is to maintain the ideal Tango structure that would mimic preferred paths changes on the virtual reference tree. So the purpose of the Tango algorithm is the constructing of a new state Ti of the Tango Tree based on the previous state Ti-1 or the Tango Tree and the new search of xi.

Tango Search

During the search for xi, one or many auxiliary trees could to be traversed. During this Tango walk phase of the Tango search every time when we are crossing from an auxiliary tree in a new auxiliary tree we perform exactly one cut operation on the tree just traversed.
The result of the Cut is than Joined with the newly entered auxiliary tree set of data and repeats for each new auxiliary tree encountered creating a snowball effect. Note that in this analogy, the snowball casts off some nodes and collects other nodes in it’s trajectory towards the final auxiliary tree that contains the searched element. Before performing a cut, the new auxiliary tree is queried to obtain a cut depth which is used in processing the previous auxiliary tree. Starting from a Reference tree in Fig. 7 obtained after performing searches on 17, 7, 1, 18, 23, 31, 27, 13, 9, 20, we see the corresponding Tango Tree as in Fig. 8. On this tree during a walk towards element xi =23 we would have traversed the top auxiliary tree 20 and entered auxiliary tree 22. Note that preferred paths are marked in red and auxiliary tree roots in magenta. Remember that all auxiliary trees are actually RB trees so the red shadows on some nodes represent the red nodes in the RB trees.

Fig. 7 Reference tree and preferred paths

In case we would have searched for element 7 during the Tango Walk we would have crossed the top auxiliary tree rooted at 20, the auxiliary tree rooted at 10, auxiliary tree rooted at 2 and auxiliary tree rooted at 6. That means that we would have to perform the Tango Cut-And-Join several times. For each entrance to a new auxiliary tree, the tree that was just crossed is processed by a Tango cut algorithm. In order to perform the Tango cut we need to determine the cut range. A specific d value is the input data in the algorithm to determine the cut range.

Determining d

This specific d value is determined every time when we cross the boundary to a new auxiliary tree and it’s determined from the soon to be traversed auxiliary tree. We know when we cross the boundary by looking at the isRoot attribute of each node en route to xi. We ignore the isRoot attribute of the root of Tango tree. To simplify the code we don’t even set it on Tango root and that is why top nodes are not colored in magenta in any of the figures.
The value of d is determined by subtracting 1 from the minimum between the root of the new auxiliary tree minD value and its current d value.
So in search for 23 we reach auxiliary tree rooted at 22 we calculate minimum between its minD value and its d value and we subtract 1 and we get this special value of d =2. Please observe by looking in the reference tree in fig. 7 that, that is exactly the depth value where the new search will change the value of a preferred child and create a new interleave. See node 20 on the reference tree in fig 7.
There are some particular cases when either minD or d are out of range or unknown. In the implementation that is represented by a -1, a value which denotes + or -infinity if the value denotes the right side of the range or left side of the range. In all the figures the nodes where the value of minD or maxD is -1 do not show the corresponding value(s) for brevity reasons.
The value of -1 is screened out during the determination of a minimum so it does not mask legitimate d values. This is not the case for maxD.

Determining the cutting range

Considering the auxiliary tree A in Fig 9, we need to determine nodes l and r. According to [Demaine et al. 2004] The node l is the node with the minimum key value (1) and the depth greater than d (2) and can be found in O(log k) time where k is the number of nodes in A.
We observe by looking at the virtual reference tree that all nodes to be cut are actually under the interleave created by the search at the node corresponding to the auxiliary tree the tango search is about to enter. In Fig. 9 we show the reference tree at state ti after a search for 9 and in Fig. 10 we show the reference tree at state ti+1 after a search for 15. The interleave appears at node 12 and we want to ‘cut’ all the nodes in the original path that are below 12. We observe their keys are all in a range of values and their d values are higher than the cutting d which is the depth of the interleave node (d=2).

Fig. 9 Reference tree with preferred paths before search for 15

Fig. 10 Reference tree with preferred paths after search for 15

Of course we need to find the nodes to be cut not in the reference tree but in the corresponding auxiliary tree. We use the value of depth obtained during the Tango search as input to calculate the cut range.
We need to determine the minimum key of a node l that has the depth greater than d. This node can be found in O(log k) time and is the left boundary of our interval. In the same way, a node r with the maximum key value and the depth greater than d can also be found in O(log k), where k is the number of nodes in A.
We already observed that the keys of the nodes to cut are in a key range so instead to take all the nodes in the corresponding auxiliary tree and check if their d is greater than the input d we can just find the left side of the range and the right side of the range.

Finding l

We first find l which is the leftmost element to be cut (using getL). We determine it by walking to the leftmost child whose sub-tree has either its d value or maximum depth greater than d.
No nodes meeting this criteria result in l being -infinity (or NIL in the implementation). This means that the cut interval extends all the way to the left so during the cut or the join less split and concatenate operations have to be performed.

Finding r

For finding r we walk right to the rightmost node whose d value is greater than d. No nodes meeting this criteria result in r being +infinity (or NIL in the implementation). This means that the cut interval extends all the way to the left so during the cut or the join less split and concatenate operations have to be performed.
Algorithms 7 and 8 describe the implementation of getL and getR.

Finding l’ and r’

Following the determination of l and r, the predecessor l’ of the node l and the successor r’ of r are found. These new nodes are the first nodes that ‘survive’ the cut. A NIL in l will also result in a NIL l’ and a NIL in r will result in a NIL in r’.
Both nodes being NIL take a new meaning signifying that all the nodes will survive the cut so practically we can skip the Tango cut and takes the set of nodes directly to Tango join.
During the Tango Search when we finally reached the searched node the tango cut algorithm is run once more however its input provided by Tango search is changed. The input value of d is now the d of the searched node and the tree to be cut is the auxiliary tree that contains the searched node.
During the Tango Search after encountering any new auxiliary tree (NAT) the Tango cut is normally applied on the tree above (except for final cut as described above) and results in a new structure of auxiliary trees. Let’s call this result of the cut A.
The Join operation will join a set of nodes with the nodes in the NAT. There is an exception that applies when we reached the searched node, in which case we join A with the auxiliary tree rooted at the preceding marked node of the searched node.
The Tango cut algorithm consists of a sequence of tree split, mark and concatenate algorithms. The Tango join algorithm consists of a different sequence of tree split, un-mark and concatenate algorithms. Marking a node is just setting the isRoot attribute to true and un-marking setting the same attribute to false.

RB Split and RB Concatenate

Red-black trees support search, split and concatenate in O(log n) time. The split and concatenate operations are the following:

Split: A red-black tree is split by rearranging the tree so that x is at the root, the left sub-tree of x is a red-black tree on the nodes with keys less than x, and the right sub-tree of x is a red-black tree on the nodes with keys greater than x.

Concatenate: A red-black tree is concatenated by rearranging x’s sub-tree to form a red-black tree on x and the nodes in its sub-tree. As condition for this operation all the nodes in one of the trees have to have lower values than the nodes in the other tree.

Note that the behavior for split and concatenate in [Demaine et al. 2004] differs slightly from the standard functionality of these operations as the signature of the operations differ in terms of number and type of input and output parameters.
The two operations describe above apply only to an auxiliary tree and do not cross into other auxiliary trees. We use the isRoot information for each node to avoid wandering in other trees.

Tango Cut algorithm

The main purpose of the cut is to separate a tree in two sets of nodes. Nodes need to be pushed to the top because the search path in the virtual reference tree traversed them and nodes that become less important (cut nodes) and are pushed downwards to the next auxiliary tree.
We already determined the values of l’ and r’ and we want to cut the input auxiliary tree (A in Fig. 11) in the range l’ to r’. We need to split A in three trees and then cut the middle tree and re- assemble the remaining parts. We start with a split at l’ that creates tree B and tree C. Tree B will be free of nodes to cut but tree C will contain nodes to cut and nodes to keep. We do a second split at r’ and obtain trees D and E. D contains all nodes to be cut and E contains all the nodes to keep. We then mark the root of D as isRoot therefore logically pushing it to a lower level. We then concatenate at r’. Note: this is not really a standard RB concatenate but rather a merge between a node and a tree. As a result we obtained C. The last operation is to concatenate C tree, B tree and node l’ obtaining the nodes we want to keep in the new tree A. Note: this is not really a standard RB concatenate but rather a merge between a node and a tree and then a standard two tree concatenation.
The resulting new node A is actually composed of two auxiliary trees: the top one that contains nodes we want to favor and the lower ‘hung’ D which contains nodes that get pushed downwards via this operation. The nodes being pushed downwards are exactly the nodes that were on the old preferred path corresponding to the auxiliary tree being processed but not in the new preferred path. The nodes being pushed upwards (now in A) are exactly the nodes that were became part of the new preferred path due to the performed search. Fig. 11 shows this flow of operations.

Fig. 11 Tango cut comprised of split, mark and concatenate operations on an auxiliary tree

The following special cases may occur:
l’ and r’ are NIL so cut is performed.
r’ is NIL we just do a split at l’ and C becomes the result while we hang B under C via a mark operation.
l’ is NIL we just do a split at r’ and E becomes the result and we hang the left resulting tree under E.
The result will be then joined with the content of the next auxiliary tree via the Tango Join algorithm.

Tango Join algorithm

During the Tango Search after encountering any new auxiliary tree (NAT) the Tango Cut being applied on the tree above the NAT results in a new structure of auxiliary trees. We can think of that as a Tango sub tree. It will normally contain at least two connected auxiliary trees. The top tree A containing the nodes we want to keep close to the surface of the Tango Tree (so we can achieve the ‘bring to top’ approach) and ‘hang’ to it is auxiliary tree D which was pushed downwards. In case of search for 23 all of the nodes from previous auxiliary tree should be kept close to surface and the set of nodes destined to be moved in D is empty so we have no D. Regardless of the situation the result of the Tango cut will contain at least one node (the Tango root) in Tree A. Let’s call this result of the cut A.
The Join will join A set of nodes with the nodes in the NAT. That is done via two splits, an un-mark and two concatenates.
Fig. 12 shows the high level sequence where A is coming from the previous cut tree and B is the NAT. We observe that NAT is actually hung under the tree that was just cut therefore the values of its keys are all in a range of two adjacent keys (a key and its successor) in the tree that was just cut. That is normal for any BST. If the NAT is hanging as a left tree the parent node marks the right side of the range while its predecessor (in the tree that was just cut universe) marks the left side of the range. So in order to join the two trees we just have to wedge B under to the left of its parent in A. Similarly for the case where B happens to hang to the right of its parent where we wedge the content of B to the right of it’s parent. In order to find the wedge insertion point we can just search in the A for the root of NAT. Of course that value is not in NAT but it will find a close value and by taking its predecessor or successor (depending on the search algorithm and if the close value was before or after the value) we find the two nodes between where B should be wedged. Let’s call these values lPrime and rPrime. Next is to split A first at lPrime and then at rPrime therefore creating three trees, a First part (FP), middle part (MP) and last part (LP). While these operations where done in the A universe they also need to carry all the other auxiliary trees as in the Tango universe. In the Tango (forest) universe we discover that MD is actually is B however is severed logically from rPrime because its root is marked as isRoot and it appears like a hung auxiliary tree. Since we want that wedged, we ‘un-mark it) by resetting its isRoot attribute and making it logically part of rPrime. Now we have the final structure in place but we still need to concatenate it first at rPrime and then at lPrime to absorb all the nodes under the same Joined resulting tree.
The difficulty in doing this is the fact that the standard concatenates do not take nodes but just trees. A two tree and a node operation could be constructed and then repeated to obtain a Tango concatenate however it’s hard to preserve the RB integrity and is dependant on the order of operations so the resulting structure is different even if it contains the same node. That is an issue because we can not control the exact reproduction of the ideal structure as if generated from the reference tree. It can be done in such a way to contain all nodes and preserve the correct RB tree structure however the geometry is dictated by the RB concatenates and is not necessarily the ideal geometry mirroring perfectly the reference tree.

Fig. 12 Tango cut comprised of split, mark and concatenate operations on an auxiliary tree

So for example let’s say search for 23. We obtain A as the result on the first Tango cut on the top auxiliary tree. See Fig. 13 where 22 is the root of NAT.

Fig. 13 Tango tree before a search for 23

We use the value of NAT (22) to search in the tree above and we obtain 20 and 24 as the lPrime and rPrime nodes.
We split at lPrime (20) and we obtain FP as in Fig. 14 and LP as in Fig. 15.

Fig. 14 First sub-tree of Tango tree (FP) after executing the first split of Tango join operation

We then split for the second time at rPrime (24) to get the last tree LT as in Fig. 15.

FIg. 15 Last sub-tree of Tango tree (FP) after executing the second split of the Tango join operation

Next we unmark B which is rooted at 22 and we obtain the result in Fig 16. As you can see 22 now is part of the top of the structure. That makes sense if you look at Fig. 10 representing the ‘virtual’ reference tree. To reach 23 which is our target we would have had to go through 22.

File:FIg160.PNG

Fig. 16 Sub-tree rooted at rPrime after executing the second split of the Tango join operation

We then concatenate with rPrime and obtain the result in presented in Fig. 17:

File:FIg170.PNG

Fig. 17 Sub-tree rooted at lPrime after executing the first concatenate of the Tango join operation

Second concatenation takes place and it this particular example will not result in rearranging of the nodes so Fig. 17 is the final result of the Join operation.

Construction Algorithms And Pseudo-code[edit]

Construct the reference tree and perform warm-up searches.
Function: constructReferenceTree
Input:  None
Output: ReferenceTree p

ReferenceTree p = new ReferenceTree()
insertDataInReferenceTree()
p.setAllDepths()
p.warmUpSearches()
ArrayList<PreferredPath> paths = p.collectAndSortPreferredPaths()
assert paths.size() > 0
PreferredPath top = p.collectTopNodePath(p.root)
TangoTree tangoTree = new TangoTree(top)
tangoTree.updateMinMaxD()	
while (takeNext PreferredPath path in paths) do 
	if (path.top = p.root) then
		continue; // skip the top path as it was already added
	else 
		RBTree auxTree = new RBTree(path)
		auxTree.updateMinMaxD()
		auxTree.root.isRoot = true
		tangoTree.hang(auxTree)
return p


Construct an Auxiliary tree out of a Preferred Path. Used in the construction phase.
Function: constructAuxiliaryTree
Input:  Preferred Path path
Output: AuxiliaryTree this
RBTree(PreferredPath path) 
	this()
	RefTreeNode refNode = path.top
	while (Next PreferredPath path in paths exists) do 
		RBNode n = new RBNode(refNode.value, RedBlackColor.RED, null, null)
		n.d = refNode.d
		this.insert(n)
		refNode = refNode.getPreferredChild()


Construct a Tango tree from the Reference tree.
Function: constructTangoTree
Input:  ReferenceTree p
Output: TangoTree tangoTree
ArrayList<PreferredPath> paths = p.collectAndSortPreferredPaths()
assert paths.size() > 0
PreferredPath top = p.collectTopNodePath(p.root)
TangoTree tangoTree = new TangoTree(top)
tangoTree.updateMinMaxD()	
while (Next PreferredPath path in paths exists) do 
	if (path.top = p.root) then
		continue; // skip the top path as it was already added
	else 
		RBTree auxTree = new RBTree(path)
		auxTree.updateMinMaxD()
		auxTree.root.isRoot = true
return tangoTree


Set the depths of all nodded in the tree. Used only once for setting the depths of all nodes in the reference tree.
Function: setAllDepths
Input:  None
setAllDepthsHelper(root)
Algorithm 14.  Set the depths of all nodded in the tree.
Function: setAllDepthsHelper
Input:  RefTreeNode n
if (n == NILL) then
	return	
n.setD(getDepth(n))
if (n.right != null) 
	setAllDepthsHelper(((RefTreeNode) n.right))
if (n.left != null) then
	setAllDepthsHelper((RefTreeNode) (n.left))

Operation Algorithms And Pseudo-code[edit]

There is just one operation: search that calls a number of algorithms to rearrange the data structure.

Tango search pseudocode. Used by the main operation on a Tango tree.
Function: tangoSearch
Input: int vKey
Node currentRoot = root
Node currentNode = root
Boolean found = false
while (true) do
	if (currentNode == NILL) then
		found = false
		break
	if (currentNode.isRoot && currentNode != root) then
		cutAndJoin(minIgnoreMinusOne(currentNode.minD, currentNode.d) - 1, currentRoot, currentNode)
		currentRoot = currentNode
	if (currentNode.value == vKey) then
		found = true
		if (currentNode != currentRoot) then
			cutAndJoin(currentNode.d, currentRoot, currentRoot)
		break
	if (currentNode.value < vKey) then
		currentNode = (RBNode) currentNode.right
	else
		currentNode = (RBNode) currentNode.left
if (found) then
	return currentNode
else
	return NILL


Tango Cut and Join used by Tango Search
Function: cutAntJoin
Input: int d, Node currentRoot, Node newlyFoundRoot
RBNode n = currentRoot
RBNode l = NILL// l is the last node that gets cut
RBNode lPrime = NILL// l' is the first node that escapes from cutting
RBNode r = NILL
RBNode rPrime = NILL
if (currentRoot.maxD <= d) // no nodes to be cut besides maybe the root
	if (currentRoot.d > d) 
		l = currentRoot
		r = currentRoot
		lPrime = getPredecessor(l, currentRoot)
		rPrime = getSuccessor(r, currentRoot)
	
 else // there are nodes to be cut underneath
	l = getL(d, n, currentRoot)
	// determine lPrime as predecessor of l or NILL if it's the last
	if (l != NILL) 
		lPrime = getPredecessor(l, currentRoot)
	 else 
		lPrime = NILL// - infinity maybe redundant			
	// end calculating l and l prime
	// find r the right side node of the cutting range based on value
	n = currentRoot
	r = getR(d, n, currentRoot)
	if (r != NILL) // the root is not to be cut
		rPrime = getSuccessor(r, currentRoot)
	
checkLandR(d, l, r, currentRoot)
RBTree aTree = NILL
if (lPrime == NILL && rPrime == NILL) // nothing to cut therefore so aTree is the whole
	aTree = new RBTree()
	aTree.root = currentRoot
 else 
	RBTreesPair aAndDtreePair = new RBTreesPair()
	aTree = tangoCut(lPrime, rPrime, currentRoot)		
RBTree afterCutAndJoin = tangoJoin(aTree, newlyFoundRootOrCurrentIfWeFound)


Tango Cut used by Tango cut And Join to separate nodes that need to be pushed to top from the rest of nodes.
Function: tangoCut
Input: RBNode lPrime, RBNode rPrime, RBNode aRoot
Output: RBTree
saveShadowAuxTrees(aRoot)
if (lPrime == null || rPrime == null) {// just one splitAnd COncatenate
	return simplifiedTangoCut(lPrime, rPrime, aRoot)
}
RBTree a = new RBTree()
a.root = aRoot
RBTreesPair firstPartAndLastPart = new RBTreesPair()
split(lPrime, a, firstPartAndLastPart)
RBTree b = firstPartAndLastPart.firstPart
RBTree c = firstPartAndLastPart.lastPart
firstPartAndLastPart.firstPart.verifyProperties()
firstPartAndLastPart.lastPart.verifyProperties()
firstPartAndLastPart = new RBTreesPair()
split(rPrime, c, firstPartAndLastPart)// problem
firstPartAndLastPart.firstPart.verifyProperties()
firstPartAndLastPart.lastPart.verifyProperties()
RBTree d = firstPartAndLastPart.firstPart
RBTree e = firstPartAndLastPart.lastPart		
// disconnect d
rPrime.left = NILL
d.root.parent = NILL

Tango Join used by Tango Cut and Join to join the result of Tango cut to auxiliary trees.
Function: tangoJoin
Input: RBTree a, RBNode newlyFoundRoot
Output: RBTree finalJoinResult
RBTree bPrevOp = new RBTree()
RBTree d = new RBTree()		
order(bPrevOp,d, a, newlyFoundRoot)
RBNodePair lAndR = bPrevOp.searchBoundedLPrimeAndRPrime(d.root.value)
if (lPrime == null || rPrime == null) // just one split and one concatenate
	return simplifiedTangoJoin(lPrime, rPrime, bPrevOp, d.root)
RBNode lPrime = lAndR.lPrime
RBNode rPrime = lAndR.rPrime
RBTreesPair firstPartAndLastPart = new RBTreesPair()
split(lPrime, bPrevOp, firstPartAndLastPart)
RBTree b = firstPartAndLastPart.firstPart
RBTree c = firstPartAndLastPart.lastPart
firstPartAndLastPart.firstPart.verifyProperties()
firstPartAndLastPart.lastPart.verifyProperties()
firstPartAndLastPart = new RBTreesPair()
split(rPrime, c, firstPartAndLastPart)//
firstPartAndLastPart.firstPart.verifyProperties()
firstPartAndLastPart.lastPart.verifyProperties()
RBTree e = firstPartAndLastPart.lastPart
// reconnect d which is normally newlyFoundRoot
d.root.isRoot = false// un-mark, a difference from tangoCut
// concatenate part
rPrime.parent = NILL// avoid side effects
RBTree res1 = concatenate(rPrime, d, e)
lPrime.parent = NILL// avoid side effects
RBTree res2 = concatenate(lPrime, b, res1)
return res2 

Check if a node n is in an auxiliary tree defined by currentRoot. Used to verify wandering.
Function: isInThisTree
Input:  RBNode n, RBNode currentRoot
Output: Boolean v
if (n.isRoot and n != currentRoot) then
	return false
else
	return true

Find node l as left of range used by Tango Cut, different from the [Demaine et al. 2004] paper.
Function: getL
Input: int d, Node n, Node currentRoot
Output: Node l
Node l = n
if (left[n] != NIL) and (not(isRoot(n) or n == currentRoot) and ((left(n).maxD > d) or (left(n).d > d)) then
	l=getL(d, left(n), currentRoot)
else
	if (n.d > d)
		l = n
	else
		l=getL(d, right(n), currentRoot)
return l


Find node r as the right limit of the range used by Tango Cut.
Function: getR
Input: int d, Node n, Node currentRoot
Output: Node r
Node r = n
if (right[n] != NIL) and (not(isRoot(n) or n == currentRoot) and ((right(n).maxD > d) or (right(n).d > d)) then
	r=getR(d, left(n), currentRoot)
else
	if (n.d > d)
		r = n
	else
		r=getR(d, right(n), currentRoot)
return r

Return Sibiling. Within enclosing auxiliary tree boundary
Function: siblingBound
Input:  RBNode n, RBNode boundingRoot
Output: Node p
if (n == left[parent[n]] && isInThisTreeAcceptsNull(left[parent[n]]), boundingRoot)) then
	if (isInThisTreeAcceptsNull(right[parent[n]], boundingRoot) then
		return right[parent[n]]
	else
		return NILL
else 
	if (isInThisTreeAcceptsNull(left[parent[n]], boundingRoot)) then
		return left[parent[n]]
 	else
		return NILL


Return Uncle. Within enclosing auxiliary tree boundary
Function: uncleBound
Input:  RBNode n, RBNode boundingRoot
Output: Node p
if (isInThisTreeAcceptsNull(parent[n], boundingRoot)) then
	return siblingBound(boundingRoot)
else
	return NILL


Update Min Max D values in red black tree augmented node. Used to update Tango Tree node attributes.
Function: updateMinMaxD
Input:  RBNode n
int minCandidate
if (n.left != NILL) then
	updateMinMaxD(n.left)
if (n.right != NILL) {
	updateMinMaxD(n.right)
if (n.left != NILL) then
	int maxFromLeft = max(n.left.d, n.left.maxD)
	n.maxD = maxFromLeft > n.maxD ? maxFromLeft : n.maxD
	if (n.left.minD != -1) {
		minCandidate = min(n.left.d, n.left.minD)
	else
		minCandidate = n.left.d
	if (n.minD != -1) then
		n.minD = min(n.minD, minCandidate)
	else
		n.minD = minCandidate
if (n.right != NILL) then
	int maxFromRight = max(n.right.d, n.right.maxD)
	n.maxD = maxFromRight > n.maxD ? maxFromRight : n.maxD
	if (n.right.minD != -1) then
		minCandidate = min(n.right.d, n.right.minD)
	else
		minCandidate = n.right.d
	if (n.minD != -1) then
		n.minD = min(n.minD, minCandidate)
	else
		n.minD = minCandidate

Search Bounded lPrime and rPrime used by Tango Join.
Function: searchBoundedLPrimeAndRPrime
Input:  RBTree rbTree, int value
Output: NodePair p
RBNode n = root
RBNode prevPrevN = NILL
RBNode prevN = NILL
RBNodePair lAndR
while (n != NILL && isInThisTree(n, rbTree.root)) do
	int compResult = value.compareTo(n.value)
	if (key(n) == value) then
		lAndR = new RBNodePair(n, n)
		return lAndR
	else 
		if (key(n) < value) then
			prevPrevN = prevN
			prevN = n
			if (isInThisTree(n.left, rbTree.root) then
				n = n.left
			else
				n = NILL
		else
			prevPrevN = prevN
			prevN = n
			if (isInThisTree(n.right, rbTree.root) then
				n = n.right
			else
				n = NILL
lAndR = new RBNodePair(prevPrevN, prevN)
return lAndR


The minimum in a binary search tree is always located if the left side path is traversed down to the leaf in O(log n) time:
Minimum Value Tree pseudocode. Used by successor.
Function: min_val_tree
Input: Node x
Output: Node x
while left(x) != NIL do
	x = left(x)
return x

Maximum Value Tree pseudocode used by predecessor.
Function: max_val_tree
Input: Node x
Output: Node x
while right(x) != NIL do
	x = right(x)
return x


The next two algorithms describe how to compute the predecessor and successor of a node. The predecessor of a node x is a node with the greatest value smaller the key[x].
Predecessor computing pseudocode used to find lPrime.
Function: predecessor
Input: RBNode x
Output: RBNode y
RBNode y = null
if (n.left != null && isInThisTree(((RBNode) (n.left)), root)) 
	return getMaximum((RBNode) (n.left), root)
y = (RBNode) (n.parent)
if (y == currentRoot) // don't let it escape above it's own root
	return NILL// --------------------------------------------------------------------->		
while (y != NILL && (y != currentRoot) && n == ((RBNode) (y.left))) do
	n = y
	if (isInThisTree(((RBNode) (y.parent)), root)) 
		y = (RBNode) (y.parent)
	 else 
		y = null
return (RBNode) y

Successor computing algorithm used to find rPrime.
Function: successor
Input: Node x
Output: Node y
RBNode y = NILL
if (n.right != NILL && isInThisTree(((RBNode) (n.right)), currentRoot)) 
	return getMinimum((RBNode) (n.right), currentRoot)

y = (RBNode) (n.parent)
if (y == currentRoot) // don't let it escape above it's own root
	return NILL// --------------------------------------------------------------------->		
while (y != NILL && isInThisTree(y, currentRoot) && n == ((RBNode) (y.right))) do
	n = y
	y = (RBNode) (y.parent)

return (RBNode) y


Traverse Tree pseudocode used by Tango Search.
Function: traverse_tree
Input: Node x
Output: None
if x != NIL and InTheAuxiliaryTree(x) then
	traverse_tree (left(x))
	traverse_tree (right(x))


Search Tree algorithm used to find lPrime and rPrime for Tango Join.
Function: search_tree
Input: Node x, value
Output: Node x
if x = NIL or k = key[x] then 
	return x
if k < key[x] then 
	return search_tree(left[x]; value)
else 
	return search_tree(right[x]; value)


Find minimum by ignoring specific values used for the calculation of d.
Function:  minIgnoreMinusOne
Input: int minD, int d
Output: int d
if (minD == -1) then
	return d
if (d == -1) then
	return minD
return min(minD, d)

RedBlack split and Red Black concatenate algorithms are described in the RON WEIN, 2005, Efficient Implementation of Red-Black Trees with Split and Catenate Operations, http://www.cs.tau.ac.il/~wein/publications/pdfs/rb_tree.pdf

Analysis[edit]

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:FigWilber10.PNG

Wilber 1 bound

<br /

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 )}$

Bibliography[edit]

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.

DANIEL DOMINIC SLEATOR AND ROBERT ENDRE TARJAN, 1985, Self-adjusting binary search trees. Journal of the ACM, 32(3):652-686, July 1985
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.1380&rep=rep1&type=pdf

ERIK D. DEMAINE, DION HARMON, JOHN IACONO, AND MIHAI PATRASCU, 2004, Dynamic optimality-almost, FOCS 2004
ERIK D. DEMAINE, DION HARMON, JOHN IACONO, AND MIHAI PATRASCU, Dynamic optimality-almost. SIAM J. Computers., 37(1):240-251, 2007
R. BAYER 1972, Symmetric Binary B-trees: Data Structure and Maintenance Algorithms, Acta Informatica 1:290-306
http://www.springerlink.com/content/qh51m2014673513j/

L. J. GUIBAS AND R. SEDGEWICK, 1978, A dichromatic framework for balanced trees. Nineteenth Annual IEEE Symposium on Foundations of Computer Science, pages 8-12, 1978
http://www.cs.princeton.edu/~sssix/papers/rb-trees.pdf

CHENGWEN CHRIS WANG, JONATHAN DERRYBERRY, DANIEL DOMINIC SLEATOR 2006, O(log log n)-Competitive Dynamic Binary Search Trees, SODA ’06, January 22-26, Miami, FL 2006 SIAM ISBN 0-89871-605-5/06/01
http://books.google.ca/books?id=R3WyVR4nqzgC&pg=PA374&lpg=PA374&dq=O%28log+log+n%29-Competitive+Dynamic+Binary+Search&source=bl&ots=aFEGOBXyDt&sig=sHenZXoRFdCxJpMqVcdMJ3YvgKQ&hl=en&ei=G8u4TcKTA-fg0QGE2Ny_Cg&sa=X&oi=book_result&ct=result&resnum=7&ved=0CE8Q6AEwBg#v=onepage&q=O%28log%20log%20n%29-Competitive%20Dynamic%20Binary%20Search&f=false

ROBERT WILBER, 1989, Lower bounds for accessing binary search trees with rotations, SIAM Journal on Computing, 18(1):56-67, 1989
http://www.informatik.uni-trier.de/~ley/db/journals/siamcomp/siamcomp18.html

ROBERT ENDRE TARJAN, 1983, Linking and cutting trees, In Data Structures and Network Algorithms, chapter 5, pages 59-70. Society for Industrial and Applied Mathematics,1983
http://www.cambridge.org/aus/catalogue/catalogue.asp?isbn=9780898711875

DANIEL DOMINIC SLEATOR, Open Source top-down splay tree implementation, http://www.link.cs.cmu.edu/splay/