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.
Examples
The tree
D
/ \
/ \
B E
/ \
A C
can be rotated to look like
B
/ \
/ \
A D
/ \
C E
This is called a right rotation. Going from the second tree to the first would be a left rotation.
If we write our tree nodes as (left subtree, node value, right subtree), then the first structure is ((A, B, C), D, E), and the second is (A, B, (C, D, E)), and computing one from the other is very simple. The following is example Python code that performs that computation:
def right_rotation(treenode):
left, D, E = treenode
A, B, C = left
return (A, B, (C, D, E))
There are also "double left" and "double right" rotations, which can be written as compositions of left and right rotations.
Tree rotations are used in a number of tree data structures such as AVL trees, red-black trees, and splay trees. 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.
References
- Java applets demonstrating tree rotations (dynamic) (http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm)
- Java applets demonstrating tree rotations (http://www.cs.queensu.ca/home/jstewart/applets/bst/bst-rotation.html)