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

No comments: