[Home]History of Tree rotation

HomePage | Recent Changes | Preferences

Revision 2 . . October 30, 2001 5:21 am by Kragen [Added code.]
Revision 1 . . October 1, 2001 10:09 am by BlckKnght [new entry]

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

Added: 21a22

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.

HomePage | Recent Changes | Preferences