AVL Trees

Review Binary search trees:
Binary search tree are organized:

BST node: key  = k*
       /      \
     Tleft     Tright
     k<=k*   k*<=k

Note: dependence of the height on the input order.

Binary searching is efficient, but the binary search tree does not guarantee a short search.  We want a height-balance tree, this type of structure will guarantee a short search.  We enforce the height-balance property:

For every internal node b of, the heights of the children differ by at most 1.

A binary search tree which also satisfies the height-balance property is called an AVL tree, Adel'son-Vel'skii and Landis.  AVL trees keep the height small and  guarantees O(lg n) searches.

Data Structure

An AVL tree is a balanced search tree.  The nodes of the AVL tree

AVLNode extends BTNode{
    protected int height;
    ... // methods
}

The height must be maintained during insertion and removal.  We also must restructure the tree during insertion and removal in order to maintain the height-balance.

Algorithms

Insertion

The insert method for the binary search tree locates an external to place the new item and then expands the node to make it an internal node, w. Adding the new external nodes may unbalance the height (i.e.. height-balance property of the tree maybe invalidated).

We must check the balance at each ancestor node to the added node.  This suggests that nodes should have additional attribute, height.  After inserting the new node we update the height of all ancestors and check the balance.

A node is in balance if the height difference of its children is no more then 1, otherwise the node is unbalanced.  All nodes of an AVL are balanced.

After inserting a new node we may discover moving up the tree an unbalanced node z (implying that the children have a height difference of 2).

We will say that node y, child of z, is the higher node.  Note that because this is an insertion it is necessary that the inserted internal node, w,  is a child of y.  Also we call node x the higher child of y.  Note x may or not be w.

Node z is unbalanced because x and y are too high, basically we would like to exchange node z with either x or y.  This will elevate x or y and lower the height of z making the tree balance. Naturally this is easier said then done because we must keep the binary search tree ordering property.

The binary search tree property is an in-order property, implying that in-order listing of nodes satisfy the ordering.  Note key(leftChild) ≤ key(thisNode) ≤ key(rightChild).  We must preserve the in-order sequence.  Consequently we need to know the in-order sequence of the x, y and z nodes.  We call  a, b, c the in-order sequence of the x, y and z nodes.  Note that z may equal a or c but not b.  Nodes x and y may equal a, b or c. This means there are 4 possible mapping of a, b and c to x, y and z implying 4 different tree configurations. See figure below.  The operations we perform to bring the tree in balance is called tri-node restructuring, because we are rearranging three nodes.  They are also called rotations.  There are are two types of rotations, single or double, depending if y or x is equal to b.  Single if y = b and double if x = b.

We must also keep the in-order sequence of the sub trees associated with a, b, and c.  There are 4 of them
even if some of the trees are an external;  T0, T1, T2, and T3.

So node b should become the top(highest) node with left and right child nodes a and c.  The trees follow the in-order sequence.  The key to the algorithm is to recognize that we need to know the in-order sequence.

Single Rotation

 \                       \
  z = a                   b = y
 / \                     / \
T1  y = b     ---> z = a     c = x
   / \                / \   / \
  T2  x = c          T1 T2 T3 T4     
     / \    
    T3 T4

Double Rotation

   \                       \
    z = a                   b = x
   / \                     / \
  T1  y = c     ---> z = a     c = y
     / \                / \   / \
b = x  T4              T1 T2 T3 T4     
   / \    
  T2 T3


Examples

How can your program determine a, b, and c?  How many if-else statements are required?

Algorithm: restructure(x)

input: A node x of a binary tree that has both a parent y and a grandparent z.
output: Tree T after a tri-node restructuring (corresponding to a single or double rotation) involving nodes x, y and z.
  1. Let (a, b, c) be a in-order listing of the nodes x, y, and z.  And let (T0, T1, T2, T3) be in-order listing for the four subtrees of  x, y and z not rooted at x, y, or z.
  2. Replace the subtree rooted at z with a new subtree rooted at b.  (Three cases: z can be the root, left or right child.)
  3. Let a be the left child of  b and let T0 and T1 be the left and right subtrees of a respectively.
  4. Let c be the right child of b and let T2 and T3 be the left and right subtrees of c respectively.

Note that balancing is performed while preserving the in-order.  The balancing is also performed locally at nodes x, y and z, so the process is O(1).

Note the height of x, y, and z must be corrected.  Also we must update all the heights on the path to the root, unless we perform an restructuring.  Restructuring lowers the limb that is too high, so the local fix is a global fix, and we do not have to continue up the tree.  

Removal


Again removing an item from the AVL tree may imbalance the tree. We must check the balance of the ancestor of the removed node. Again we find z the first unbalanced node and move back down to find y and x children and grandchildren of z respectively.  We then perform restructure(x) as before.

Note that restructure is O(1) and remove is O( lg n)

Now a local fix is not guaranteed to be a global fix, so we have move all the way up the tree to the root.  

Cost

Operation

Time

size, isEmpty

O(1)

find, insert, remove

O(lg n)

findAll

O(lg n + s)


Note there is a downward search and upward check for balancing.