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
