AVL Trees
From
(→AVL Tree Single Rotations) |
(→AVL Tree Double Rotations) |
||
| Line 21: | Line 21: | ||
== AVL Tree Double Rotations == | == AVL Tree Double Rotations == | ||
| - | Double Right Rotation for trees that are out of balance to the left, and the left subtree is right heavy (a Left-Right case): | + | '''Double Right Rotation''' for trees that are out of balance to the left, and the left subtree is right heavy (a Left-Right case): |
[[Image:DoubleRightRotation.png]]<br><br> | [[Image:DoubleRightRotation.png]]<br><br> | ||
| - | Double Left Rotation for subtrees that are out of balance to the right and the right subree is left heavy (a Right-Left Case): | + | '''Double Left Rotation''' for subtrees that are out of balance to the right and the right subree is left heavy (a Right-Left Case): |
[[Image:DoubleLeftRotation.png]]<br><br> | [[Image:DoubleLeftRotation.png]]<br><br> | ||
Revision as of 16:38, 7 May 2009
| ← Binary Search Trees | ↑ Binary Trees | Red-Black Trees → |
An AVL tree is a self-balancing binary search tree, and it is the first such data structure to be invented.[1] In an AVL tree, the heights of the two child subtrees of any node differ by at most one; therefore, it is also said to be height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
The AVL tree is named after its two inventors, G.M. Adelson-Velskii and E.M. Landis, who published it in their 1962 paper "An algorithm for the organization of information."
AVL Behavior
Each node in an AVL tree contains information regarding the balance of the tree at that node. This information, called the balance factor, is defined as the height of the left subtree minus the height of the right subtree. Thus, when a tree is perfectly balanced, every node has a balance factor that equals zero.
Whenever a node is inserted or deleted into an AVL tree, the balance factor for each node along the path from the root to the inserted or deleted node must be recalculated. As long as the balance factor for each node is a -1, 0, or +1, no further action is taken. If a balance factor does not fall within this range, one of four type of rotations is performed that involve the out-of-balance node. The possible rotations are: (1) single right rotation, (2) single left rotation, (3) double left-right rotation, and (4) double right-left rotation. The rules for which rotation are somewhat complex, but we will look at an example of a single and a double rotation below.
AVL Tree Single Rotations
Single Right Rotation for subtrees that are out of balance to the left, and the left subtree is left heavy (Left-Left case): 
Single Left Rotation for subtrees that are out of balance to the right, and the right subtree is right heavy (Right-Right case): 
AVL Tree Double Rotations
Double Right Rotation for trees that are out of balance to the left, and the left subtree is right heavy (a Left-Right case): 
Double Left Rotation for subtrees that are out of balance to the right and the right subree is left heavy (a Right-Left Case): 
CS2: Data Structures
Theory of Computation - ADT Preliminaries
Linear ADTs - Tree ADTs - Graph ADTs - Unordered Collection ADTs
