Wednesday, January 14, 2009

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

Wednesday, January 07, 2009

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);
    }
  }
}

Saturday, January 03, 2009

Traversing binary trees

What are trees? Trees are data structures which contain a node and one or more children. A binary tree is a tree in which each node is either empty or contains at max two children.

A binary tree...

root --------> R
                /    \
               L     R
              /  \   /  \
             l  r   rl  

A binary tree of height h<=0 has at max 2^h+1 - 1 nodes. And the height of the tree h = log2(n), where n is the number of nodes in the binary tree.

Lets check out the recursive functions used to traverse the binary trees:

1. Preorder traversal:
Preorder traversal does the following recursively :
-> visit the root
-> traverse left subtree
-> traverse right subtree

function preorder(tree)
{
  if (tree == null) return;

  print(tree.root);
  call preorder(tree.left_subtree);
  call preorder(tree.right_subtree);
}

2. Inorder traversal:
Inorder traversal does the following recursively :
-> traverse left subtree
-> visit the root
-> traverse right subtree

function inorder(tree)
{
  if (tree == null) return;

  call inorder(tree.left_subtree);
  print(tree.root);
  call inorder(tree.right_subtree);
}

3. Postorder traversal:
Postorder traversal does the following recursively :
-> traverse left subtree
-> traverse right subtree
-> visit the root

function postorder(tree)
{
  if (tree == null) return;

  call postorder(tree.left_subtree);
  call postorder(tree.right_subtree);
  print(tree.root);
}

4. Breadth-first or level-order traversal:
In Level-order traversal each level is visited successively starting from root(level-0) and nodes are visited from left to right on each level. This is generally implemented using a queue data structure.

- push the root node in the queue
- pop the node from the queue, push the left and right child node in the queue.
- pop the root->left node from the queue and push the left and right child node of root->left in the queue.
- pop the root->right node from the queue and push the left and right child node of root->right in the queue.

function levelorder(tree)
{
  queue.push(tree.root);
  while(queue.size > 0)
  {
    Node n = queue.pop(); //get first node in queue
    if (n.left != null) queue.push(n.left);
    if (n.right != null) queue.push(n.right);
    print n;
  }
}