Tree rotation

Tree rotation

A tree rotation is an operation on a binary search tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. They are used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations.

There exists an inconsistency in different descriptions as to the definition of the direction of rotations. Some say that the direction of a rotation depends on the side which the tree nodes are shifted upon whilst others say that it depends on which child takes the root's place (opposite of the former). This article takes the approach of the side where the nodes get shifted to.

Illustration

The right rotation operation as shown in the image above is performed with Q as the root and hence is a right rotation on, or rooted at, Q. This operation results in a rotation of the tree in the clockwise direction. The symmetric operation is the left rotation which results in a movement in an anti-clockwise direction (the left rotation shown above is rooted at P).

Assuming this is a binary search tree, as stated above, the elements must be interpreted as variables and not as alphabetic characters.

Detailed Illustration

What happens when a subtree is rotated is that the subtree side upon which it is rotated decreases its height by one node whilst the other subtree increases its height. This makes it useful to rebalance a tree.

Using the terminology of Root for the parent node of the subtrees to rotate, Pivot for the node which will become the new parent node, RS for rotation side upon to rotate and OS for opposite side of rotation. In the above diagram for the root Q, the RS is C and the OS is P. The pseudo code for the rotation is:

Pivot = Root.OS Root.OS = Pivot.RS Pivot.RS = Root Root = Pivot

This is thus a constant time operation. The programmer must also make sure that the root's parent points to the pivot afterwards.

Inorder Invariance

The tree rotation renders the inorder traversal of the binary tree invariant. This implies the order of the elements are not affected when a rotation is performed in any part of the tree. Here are the inorder traversals of the trees shown above:

Left tree: ((A, P, B), Q, C) Right tree: (A, P, (B, Q, C))

Computing one from the other is very simple. The following is example Python code that performs that computation:

def right_rotation(treenode): left, Q, C = treenode A, P, B = left return (A, P, (B, Q, C))

Another way of looking at it is:

Left Rotation of node P:

Let Q be P's right child.Set Q to be the new root.Set P's right child to be Q's left child.Set Q's left child to be P.

Right Rotation of node Q:

Let P be Q's left child.Set P to be the new root.Set Q's left child to be P's right child.Set P's right child to be Q.

All other connections are left as-is.

There are also "double rotations", which are combinations of left and right rotations. A "double left" rotation at X can be defined to be a right rotation at the right child of X followed by a left rotation at X; similarly, a "double right" rotation at X can be defined to be a left rotation at the left child of X followed by a right rotation at X.

Tree rotations are used in a number of tree data structures such as AVL trees, red-black trees, splay trees, and treaps. They require only constant time because they are "local" transformations: they only operate on 5 nodes, and need not examine the rest of the tree.

Rotations for rebalancing

A tree can be rebalanced using rotations. A type of tree which uses this rebalancing technique is the AVL tree. The reason why rotations can result in a change in balance is because after a rotation, the side of the rotation will decrease in height by 1 whilst the other side will increase in height by 1. Therefore the heights can be arranged to form a balanced tree.

Rotation distance

The rotation distance between any two binary trees with the same number of nodes is the minimum number of rotations needed to transform one into the other. With this distance, the set of "n"-node binary trees becomes a metric space: the distance is symmetric, positive when given two different trees, and satisfies the triangle inequality.

It is an open problem whether there exists a polynomial time algorithm for calculating rotation distance. However, Daniel Sleator, Robert Tarjan and William Thurston showed that the rotation distance between any two "n"-node trees (for "n" ≥ 11) is at most 2"n" − 6, and that infinitely many pairs of trees are this far apart. [citation|last1=Sleator|first1=Daniel D.|authorlink1=Daniel Sleator|last2=Tarjan|first2=Robert E.|authorlink2=Robert Tarjan|last3=Thurston|first3=William P.|authorlink3=William Thurston|title=Rotation distance, triangulations, and hyperbolic geometry|journal=Journal of the American Mathematical Society|volume=1|issue=3|year=1988|pages=647–681|doi=10.2307/1990951|id=MathSciNet|id=928904.]

References

External links

* [http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm Java applets demonstrating tree rotations (dynamic)]
* [http://www.cs.queensu.ca/home/jstewart/applets/bst/bst-rotation.html Java applets demonstrating tree rotations]
* [http://fortheloot.com/public/AVLTreeTutorial.rtf The AVL Tree Rotations Tutorial] (RTF) by John Hargrove

ee also

* AVL tree, red-black tree, and splay tree, three binary search tree data structures that are updated using rotations and guarantee fast access times over a sequence of operations
* Associativity of a binary operation means that performing a tree rotation on it does not change the final result.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • AVL tree — In computer science, an AVL tree is a self balancing binary search tree, and it is the first such data structure to be invented. [Robert Sedgewick, Algorithms , Addison Wesley, 1983, ISBN 0 201 06672 6, page 199, chapter 15: Balanced Trees.] In… …   Wikipedia

  • Red-black tree — A red black tree is a type of self balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer who called them symmetric… …   Wikipedia

  • Left rotation — refers to the following * In an array, moving all items to the next lower location. The first item is moved to the last location, which is now vacant. * In a list, removing the head and inserting it at the tail. Tree Rotation In a binary search… …   Wikipedia

  • T-tree — In computer science a T tree is a type of binary tree data structure that is used by main memory databases, such as DataBlitz, e X treme DB, MySQL Cluster, Oracle TimesTen and [http://www.kairosdbms.com Kairos] [http://www.emware.co.kr… …   Wikipedia

  • Splay tree — A splay tree is a self balancing binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look up and removal in O(log(n)) amortized time. For many… …   Wikipedia

  • Interval tree — In computer science, an interval tree, also called a segment tree or segtree, is an ordered tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is… …   Wikipedia

  • Kd-tree — In computer science, a k d tree (short for k dimensional tree ) is a space partitioning data structure for organizing points in a k dimensional space. k d trees are a useful data structure for several applications, such as searches involving a… …   Wikipedia

  • Self-balancing binary search tree — In computer science, a self balancing binary search tree or height balanced binary search tree is a binary search tree that attempts to keep its height , or the number of levels of nodes beneath the root, as small as possible at all times,… …   Wikipedia

  • Optimal rotation age — Contents 1 Economically optimum rotation age 2 Biologically optimum rotation age 3 Non timber forest use and effect on rotation 4 Factors …   Wikipedia

  • AA tree — In computer science, AA trees (Arne Andersson trees) are a form of balanced trees used for storing and retrieving ordereddata efficiently.Unlike red black trees, red nodes on an AA tree can only be added as a right subchild. In other words, no… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”