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...

Binary Search Tree

In a tightly packed binary search tree you need at max log(2)n comparisons to find a match for n elements. So, for example to search a list of 1000 elements, you should need max 10 comparisons. Additions and deletions from the BST (binary search tree) require that the sorted order of elements should be maintained.

Let us see some pseudo code for creating and maintaining binary search trees

Find an element X in a BST with root node N:

find (X, N)
{
  if(N == NULL) return NULL;
  if(X == N.data) return N;
  else if (X < N.data) return find(X, N.leftChild);
  else if (X > N.data) return find(X, N.rightChild);
}


Find the node with the minimum data. Start from root node N

findMinimum(N)
{
  if(N == NULL) return NULL;
  if(N.leftChild == NULL) return N;
  return findMinimum(N.leftChild);
}

Insert data X in a BST with root node N

Insert(X, N)
{
  if(N == NULL) //insert at last node
  {
    N = new BinaryNode(X, NULL, NULL);
    return;
  }
  if(X == N.data) // data already exists in BST, ignore X
    return;
  else if(X < N.data) Insert(X, N.leftChild);
  else Insert(X, N.rightChild);
}


Delete an element X from the BST with root node N

Delete(X, N)
{
  if(N == NULL) return;
  if(X < N.data) Delete(X, N.leftChild);
  else if (X > N.data) Delete(X, N.rightChild)
  else // X == N.data. Delete and readjust all children
  {
    if(N.leftChild == NULL && N.rightChild == NULL)
    {
      delete N;
      N = null;
      return;
    }
    else if(N.leftChild == NULL)
    {
      tmpN = N;
      N = N.rightChild;
      delete tmpN;
    }
    else if(N.rightChild == NULL)
    {
      tmpN = N;
      N = N.leftChild;
      delete tmpN;
    }
    else //replace N.data with minimum data from right subtree
    {
      tmpN = findMinimum(N.rightChild);
      N.data = tmpN.data;
      delete(N.data, N.rightChild);
    }
  }
}