AVL Search Tree

With BST the problem is that it should be balanced properly so that the height of a tree with node n should be log(2)n. But since BST does not have any balancing algorithm which re-balances the tree on every insert/delete, the tree becomes unbalanced. In this case the height of the tree may go up to n (same as the number of elements n). So the worst case scenario for search is O(n) for a BST.

An AVL tree on the other hand is supposed to be balanced. Balanced means that
* Either the tree is empty
* Or for every node in a non-empty tree height(left_sub_tree) - height(right_sub_tree) <= 1

The idea is that whenever we insert/remove an element from the tree, we should check that the tree is balanced and if not, we should perform "rotations" to balance the tree.

For example we have a tree

        c
       /
      b

If we add a node "a" to the tree we will get

        c
       /
      b
     /
    a

Now the left subtree is of height 2 and the right subtree is of height 0, so it is unbalanced. So a single right rotation is performed to balance the tree.

      b
     / \
    a   c

Lets see a few algorithms to insert and remove nodes from an AVL tree

Single LL & RR rotation will do the following converstion



Simple rotation to left:

function Rotate_LL(oldRoot)
{
  Result = oldRoot.left;
  oldRoot.left = Result.right;
  Result.right = oldRoot;
  AdjustHeight(oldRoot);
  AdjustHeight(Result);
  AdjustHeight(oldRoot.left);
  return Result;
}

Simple rotation to right:

function Rotate_RR(oldRoot)
{
  Result = oldRoot.right;
  oldRoot.right = Result.left;
  Result.left = oldRoot;
  AdjustHeight(oldRoot);
  AdjustHeight(Result);
  AdjustHeight(oldRoot.right);
  return Result;
}

Following are the RL and LR rotations:

Double rotation to right:


Double rotation to left:


Lets assume that every node has a height attribute. AdjustHeight function updates the height to reflect the current height of the tree

Function adjustHeight(Node)
{
  if (Node != null) then
  {
    Node.height=1+max(height(node.left),height(node.right));
  }
}

Function to get the height of the node

Function getHeight(Node)
{
  if(Node == Void) return 0
  else return Node.height
}

Insert record in AVL tree. Remember that the tree has to be rebalanced after insert.

Function insertData(key, data)
{
  Node = new Node(key, data);
  root = insertNode(root, Node);
  root = rebalanceForInsert(root);
  adjustHeight(root);
}

Function insertNode(root, newNode)
{
  if (root == Void) root = newNode;
  else
  {
    if(root.key > newNode.key)
      root.left = insertNode(root.left, newNode);
    else
      root.right = insertNode(root.right, newNode);
  }
  result = rebalanceForInsert(root);
  adjustHeight(result);
}

Function rebalanceForInsert(Node)
{
  h_LL = height(Node.left.left);
  h_LR = height(Node.left.right);
  h_R = height(Node.right);
  h_RR = height(Node.right.right);
  h_RL = height(Node.right.left);
  h_L = height(Node.left);
  if( (h_LL == h_LR) && (h_LR >= h_R) )
    result = rotate_LL(Node);
  else if( (h_RR == h_RL) && (h_RL >= h_L) )
    result = rotate_RR(Node);
  else if( (h_LR == h_LL) && (h_LL >= h_R) )
    result = rotate_LR(Node);
  else if( (h_RL == h_RR) && (h_RR >= h_L) )
    result = rotate_RL(Node);
  else result = Node;
  return result;
}

Lets look at how to remove node from an AVL tree

Function Remove(key)
{
  if (root==void) result = void;
  else if(root.key == key)
  {
    result = root.data;
    root = removeNode(root);
  }
  else
    result = removeRec(root,key);
  adjustHeight(root);
  root = rebalanceForDel(root);
}

Function RemoveRec(node, key)
{
  if(root.key > key) //remove from left subtree
  {
    if(root.left == void) result = void;
    else if(root.left.key == key)
    {
      result = root.left.data;
      root.left = removeNode(root.left);
    }
    else
    {
      result = removeRec(root.left, key);
      adjustHeight(root.left);
      root.left = rebalanceForDel(root.left);
    }
  }
  else //remove from right subtree
  {
    if(root.right == void) result = void;
    else if(root.right.key == key)
    {
      result = root.right.data;
      root.right = removeNode(root.right);
    }
    else
    {
      result = removeRec(root.right, key);
      adjustHeight(root.right);
      root.right = rebalanceForDel(root.right);
  }
  return result;
}

Function removeNode(Node)
{
  if(Node.left == void) result = Node.right;
  else if(Node.right == void) result = Node.left;
  else (child = root.left)
  {
    if(child.right == void)
    {
      Node.data = child.data;
      Node.left = child.left;
    }
    else
      Node.left = swap_and_remove_left_nbr(Node,child);
    adjustHeight(Node);
    result = rebalanceForDel(Node);
  }
}

Function swap_and_remove_left_nbr(Parent, child)
{
  if(child.right.right != void)
    child.right = swap_and_remove_left_nbr(parent, child.right);
  else
  {
    parent.data = child.right.data;
    child.right = child.right.left;
  }
  adjustHeight(parent);
  result = rebalanceForDel(parent);
}

Function rebalanceForDel(Node)
{
  h_LL = height(Node.left.left);
  h_LR = height(Node.left.right);
  h_R = height(Node.right);
  h_RR = height(Node.right.right);
  h_RL = height(Node.right.left);
  h_L = height(Node.left);
  if( (h_LL >= h_LR) && (h_LR >= h_R) )
    result = rotate_LL(Node);
  else if( (h_RR >= h_RL) && (h_RL >= h_L) )
    result = rotate_RR(Node);
  else if( (h_LR >= h_LL) && (h_LL >= h_R) )
    result = rotate_LR(Node);
  else if( (h_RL >= h_RR) && (h_RR >= h_L) )
    result = rotate_RL(Node);
  else result = Node;
  return result;
}

That is quite a lot of stuff to digest...
Happy chewing...