User:Ontariolot/test

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. 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

The 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

The 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

Insertion

To 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

To 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

The 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

Splay operation in BST

Here 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

A 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) = log₂(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(t_f) - P(t_i) ≤ 3(rank_f(x) - rank_i(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

There 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

The cost of performing the sequence S is $O(m(1+\log n)+n\log n).$ In other words, splay trees perform as well as static balanced binary search trees on sequences of at least n accesses.

Static Optimality Theorem

Let $q_{i}$ be the number of times element i is accessed in S. The cost of performing S is $O\left(m+\sum _{i=1}^{n}q_{i}\log {\frac {m}{q_{i}}}\right).$ In other words, splay trees perform as well as optimum static binary search trees on sequences of at least n accesses.

Static Finger Theorem

Let $i_{j}$ be the element accessed in the $j^{th}$ access of S and let f be any fixed element (the finger). The cost of performing S is $O{\Bigl (}m+n\log n+\sum _{j=1}^{m}\log(|i_{j}-f|+1){\Bigr )}.$

Working Set Theorem

Let $t(j)$ be the number of distinct elements accessed between access j and the previous time element $i_{j}$ was accessed. The cost of performing S is $O{\Bigl (}m+n\log n+\sum _{j=1}^{m}\log(t(j)+1){\Bigr )}.$

Dynamic Finger Theorem

The cost of performing S is $O{\Bigl (}m+n+\sum _{j=1}^{m}\log(|i_{j+1}-i_{j}|+1){\Bigr )}.$

Scanning Theorem

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 $4.5n$.

Dynamic optimality conjecture

In 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: Let $A$ be any binary search tree algorithm that accesses an element $x$ by traversing the path from the root to $x$ at a cost of $d(x)+1$, and that between accesses can make any rotations in the tree at a cost of 1 per rotation. Let $A(S)$ be the cost for $A$ to perform the sequence $S$ of accesses. Then the cost for a splay tree to perform the same accesses is $O(n+A(S))$.

There are several corollaries of the dynamic optimality conjecture that remain unproven:

Traversal Conjecture: Let $T_{1}$ and $T_{2}$ be two splay trees containing the same elements. Let $S$ be the sequence obtained by visiting the elements in $T_{2}$ in preorder (i.e. depth first search order). The total cost of performing the sequence $S$ of accesses on $T_{1}$ is $O(n)$.

Deque Conjecture: Let $S$ be a sequence of $m$ double-ended queue operations (push, pop, inject, eject). Then the cost of performing $S$ on a splay tree is $O(m+n)$.

Split Conjecture: Let $S$ be any permutation of the elements of the splay tree. Then the cost of deleting the elements in the order $S$ is $O(n)$.

References

• 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

• NIST's Dictionary of Algorithms and Data Structures: TangoTree
• "Dynamic Optimality-Almost"