A Tango Tree is a type of binary search tree created to surpass the usual O(log n) (log n) Binary Search Tree cost of opertions. It performs basic operations such as searches in O(log n)(log n) (log n) time. This optimization is acheved dinamically by adjusting the search tree structure as a result of all serches. It is similar in it's dynamic behaviour with other types of structures like Splay tree however the search speed is considerably improved.
It achieves this by a combination of augumentation of attributes in the data structure, a more elaborated algorithm and the use of other type of trees for some of it's structure. The Tango trees was invented by Erik D. Demaine, Dion Harmon, John Iacono and Mihai Patrascu in 2004.[1] The main idea behind this performant data structure is to extract from the original tree a number of virtual smaller subtrees all with a normal O((lg number of subtree elements) cost of access. These subtrees are dinamically balanced to offer the usual O(log n) (log n) perfomance for data retrieval. Via this classic divide and conquer approach once the original tree has been adjusted to include a collection of these subtrees we can actually obtain a much improved the cost of access of these subtrees. Both the Tango Tree and these subtrees are a type of Self-balancing binary search tree.
Advantages
editThe Tango Trees currently offer the ultimate retrieval speed for online data. That makes the Tango Tree the most competitive tree for online operations. Online structures deal with operations that are not known in advance before the data structure is created. The majority of the real life situations are online.
Outstanding search performance for a Tango tree relies on the fact in that that accessing nodes constantly update 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
editThe Tango Tree focuses on data searches on static data structures rather than on deletions or insertions so they might not be appropriate in any situation.
The Tango Tree uses augumentation meaning storying more data in a node that a plain Binary Search Tree. Tango Trees use O(lg lg n) bitswhich is not a significant increase in the data storage. That results in a bigger memory footprint.
A more complex algorithm that makes use of other algorithms like RedBlack Trees and balancing operations
Tango trees change n 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.
Operations
editInsertion
editTo insert a node x into a splay tree, we first insert it as with a normal binary search tree. Then we splay the new node x to the top of the tree..
Deletion
editTo delete a node x, we use the same method as with a binary search tree. If x has two children, we replace its value with either the rightmost node of its left sub tree (its in-order predecessor) or the leftmost node of its right subtree (its in-order successor). Then we remove that node instead. In this way, deletion is reduced to the problem of removing a node with 0 or 1 children. After deletion, we splay the parent of the removed node to the top of the tree. OR The node to be deleted is first splayed, i.e. brought to the root of the tree and then deleted. This leaves the tree with two sub trees. The maximum element of the left sub tree (: METHOD 1), or minimum of the right sub tree (: METHOD 2) is then splayed to the root. The right sub tree is made the right child of the resultant left sub tree (for METHOD 1). The root of left sub tree is the root of melded tree.
Deletion Code in C language
editThe Splay function is same as the one defined below.
Delete _ Splay (root, x) // delete 'x' from tree rooted at 'root'
{
node=find (root, x) // find node in tree (similar to search fn of BST)
// find returns 'x' if it is found else it returns 'node' where search terminated
Splay (node, root) // bring x to root
L = node-> left // save left and right child of x (current root) before
// deleting
R = node-> right
M= tree_ Max (L) // node with largest key: rightmost in right of L
Splay (M,L ) // the left tree will now have no right sub-tree
root=M // Make M root of tree and R its right child
( This process automatically deletes root: free the memory allocated to previous root )
R-> parent=M
M->right=R
}
Code in C language
editSplay operation in BST
editHere x is the node on which the splay operation is performed and root is the root node of the tree.
void splay (struct node *x, struct node *root)
{
node *p,*g;
/*check if node x is the root node*/
if(x==root);
/*Performs Zig step*/
else if(x->parent==root)
{
if(x==(x->parent)->left)
rightrotation(root);
else
leftrotation(root);
}
else
{
p=x->parent; /*now points to parent of x*/
g=p->parent; /*now points to parent of x's parent*/
/*Performs the Zig-zig step when x is left and x's parent is left*/
if(x==p->left&&p==g->left)
{
rightrotation(g);
rightrotation(p);
}
/*Performs the Zig-zig step when x is right and x's parent is right*/
else if(x==p->right&&p==g->right)
{
leftrotation(g);
leftrotation(p);
}
/*Performs the Zig-zag step when x's is right and x's parent is left*/
else if(x==p->right&&p==g->left)
{
leftrotation(p);
rightrotation(g);
}
/*Performs the Zig-zag step when x's is left and x's parent is right*/
else if(x==p->left&&p==g->right)
{
rightrotation(p);
leftrotation(g);
}
splay(x, root);
}
}
Analysis
editA simple amortized analysis of static splay trees can be carried out using the potential method. Suppose that size(r) is the number of nodes in the subtree rooted at r (including r) and rank(r) = log2(size(r)). Then the potential function P(t) for a splay tree t is the sum of the ranks of all the nodes in the tree. This will tend to be high for poorly-balanced trees, and low for well-balanced trees. We can bound the amortized cost of any zig-zig or zig-zag operation by:
- amortized cost = cost + P(tf) - P(ti) ≤ 3(rankf(x) - ranki(x)),
where x is the node being moved towards the root, and the subscripts "f" and "i" indicate after and before the operation, respectively. When summed over the entire splay operation, this telescopes to 3(rank(root)) which is O(log n). Since there's at most one zig operation, this only adds a constant.
Performance theorems
editThere are several theorems and conjectures regarding the worst-case runtime for performing a sequence S of m accesses in a splay tree containing n elements.
- Balance Theorem[2]
- The cost of performing the sequence S is In other words, splay trees perform as well as static balanced binary search trees on sequences of at least n accesses.
- Static Optimality Theorem[2]
- Let be the number of times element i is accessed in S. The cost of performing S is In other words, splay trees perform as well as optimum static binary search trees on sequences of at least n accesses.
- Static Finger Theorem[2]
- Let be the element accessed in the access of S and let f be any fixed element (the finger). The cost of performing S is
- Working Set Theorem[2]
- Let be the number of distinct elements accessed between access j and the previous time element was accessed. The cost of performing S is
- Dynamic Finger Theorem[3][4]
- The cost of performing S is
- Scanning Theorem[5]
- Also known as the Sequential Access Theorem. Accessing the n elements of a splay tree in symmetric order takes O(n) time, regardless of the initial structure of the splay tree. The tightest upper bound proven so far is .[6]
Dynamic optimality conjecture
editIn addition to the proven performance guarantees for splay trees there is an unproven conjecture of great interest from the original Sleator and Tarjan paper. This conjecture is known as the dynamic optimality conjecture and it basically claims that splay trees perform as well as any other binary search tree algorithm up to a constant factor.
- Dynamic Optimality Conjecture:[2] Let be any binary search tree algorithm that accesses an element by traversing the path from the root to at a cost of , and that between accesses can make any rotations in the tree at a cost of 1 per rotation. Let be the cost for to perform the sequence of accesses. Then the cost for a splay tree to perform the same accesses is .
There are several corollaries of the dynamic optimality conjecture that remain unproven:
- Traversal Conjecture:[2] Let and be two splay trees containing the same elements. Let be the sequence obtained by visiting the elements in in preorder (i.e. depth first search order). The total cost of performing the sequence of accesses on is .
- Deque Conjecture:[7][5][8] Let be a sequence of double-ended queue operations (push, pop, inject, eject). Then the cost of performing on a splay tree is .
- Split Conjecture:[9] Let be any permutation of the elements of the splay tree. Then the cost of deleting the elements in the order is .
References
edit- Erik D. Demaine, Dion Harmon, ,John Iacono and Mihai Pătraşcu, 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.
- finger tree
External links
edit- ^ Cite error: The named reference
???SleatorTarjan
was invoked but never defined (see the help page). - ^ a b c d e f Sleator, Daniel D.; Tarjan, Robert E. (1985), "Self-Adjusting Binary Search Trees" (PDF), Journal of the ACM (Association for Computing Machinery), 32 (3): 652–686, doi:10.1145/3828.3835
- ^ Cole, Richard (2000), "On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences", SIAM (Society for Industrial and Applied Mathematics) Journal on Computing, 30: 1–43
{{citation}}
: Unknown parameter|coauthors=
ignored (|author=
suggested) (help) - ^ Cole, Richard (2000), "On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof", SIAM Journal on Computing, 30: 44–85, doi:10.1137/S009753979732699X
- ^ a b Tarjan, Robert E. (1985), "Sequential access in splay trees takes linear time", Combinatorica, 5: 367–378, doi:10.1007/BF02579253
- ^ Elmasry, Amr (2004), "On the sequential access theorem and Deque conjecture for splay trees", Theoretical Computer Science, 314 (3): 459–466, doi:10.1016/j.tcs.2004.01.019
- ^ Pettie, Seth (2008), "Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture", Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms: 1115–1124
- ^ Sundar, Rajamani (1992), "On the Deque conjecture for the splay algorithm", Combinatorica, 12 (1): 95–124, doi:10.1007/BF01191208
- ^ Lucas, Joan M. (1991), "On the Competitiveness of Splay Trees: Relations to the Union-Find Problem", Online Algorithms, Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) Series in Discrete Mathematics and Theoretical Computer Science Vol. 7: 95–124