# Tree rotation

HomePage | Recent Changes | Preferences

Difference (from prior major revision) (no other diffs)

Changed: 24c25,36
 See AVL tree, Red-Black tree
 If we write our tree nodes as (left subtree, nodevalue, 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: ` 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 AVL trees, Red-Black trees, splay trees, and others.

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. Tree rotations are used to balance some kinds of trees to improve performance.

#### 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, nodevalue, 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:

```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 AVL trees, Red-Black trees, splay trees, and others.

Reference: [this] page has some excelent (Free) java applets demonstrating tree rotations. (can we add applets to the Wiki?)

HomePage | Recent Changes | Preferences