AVL Tree Algorithm
An AVL Tree is a form of binary tree,
however unlike a binary tree, the worst case scenario for a search is O(log n).
The AVL data structure achieves this property by placing restrictions on the
difference in height between the sub-trees of a given node, and re-balancing the
tree if it violates these restrictions.
AVL Tree Balance Requirements
The complexity of an AVL Tree comes from
the balance requirements it enforces on each node. A node is only allowed to
possess one of three possible states (or balance factors):
Left-High (balance factor -1)
The left-sub tree is one level
taller than the right-sub tree
Balanced (balance factor 0)
The left and right sub-trees are both
the same heights
Right-High (balance factor +1)
The right sub-tree is one level
taller than the left-sub tree.
If the balance of a node becomes -2 (it was left high and a level was lost
from the left sub-tree) or +2 (it was right high and a level was lost from the
right sub-tree) it will require re-balancing. This is achieved by performing a
rotation about this node (see the section below on rotations).
Inserting in an AVL Tree
Nodes are initially inserted into AVL Trees in
the same manner as an ordinary binary search tree (that is, they are always
inserted as leaf nodes). After insertion, however, the insertion algorithm for
an AVL Tree travels back along the path it took to find the point of insertion,
and checks the balance at each node on the path. If a node is found that is
unbalanced (that is, it has a balance factor of either -2 or +2), then a
rotation is performed (see the section below on rotations) based on the inserted
nodes position relative to the node being examined (the unbalanced node).
NB. There will only ever be at most one rotation required after an insert
operation.
Deleting from an AVL Tree
The deletion algorithm for AVL Trees is a
little more complex, as there are several extra steps involved in the deletion
of a node. If the node is not a leaf node (that is, is has at least one child),
then the node must be swapped with either it's in-order successor or predecessor
(based on availability). Once the node has been swapped we can delete it (and
have its parent pick up any children it may have - bear in mind that it will
only ever have at most one child). If a deletion node was originally a leaf
node, then it can simply be removed.
Now, as with the insertion algorithm, we traverse back up the path to the
root node, checking the balance of all nodes along the path. If we encounter an
unbalanced node we perform an appropriate rotation to balance the node (see the
section below on rotations).
NB. Unlike the insertion algorithm, more than one rotation may be required
after a delete operation, so in some cases we will have to continue back up the
tree after a rotation.
AVL Tree Rotations
As mentioned previously, an AVL Tree and the nodes it
contains must meet strict balance requirements to maintain is O(log n) search
capabilities. These balance restrictions are maintained using various rotation
functions. Below is a diagrammatic overview of the four possible rotations that
can be performed on an unbalanced AVL Tree, illustrating the before and after
states of an AVL Tree requiring the rotation.
LL Rotation
RR Rotation
LR Rotation
RL Rotation
