When we store ordered data in an array, we have a very efficient search algorithm, i.e. the binary searching. —However, we have very inefficient insertion and deletion algorithms that require shifting data in the array. —To provide efficient insertions and deletions, we developed the linked list. —The problem with linked lists, however, is that their search algorithms are sequential searches, which are very inefficient. —Binary trees offer short paths from root. —A node has up to two children. —Data is organized by value. Some of the operations that we’ll discuss in this article are given with brief description below:

  • Insertion: inserts an item into the tree
  • Search: searches an item from the tree
  • Traversal: traverses the tree
  • Deletion: deletes an item from the tree
  • —Find Minimum: find the item that has the minimum value in the tree
  • —Find Maximum: find the item that has the maximum value in the tree
  • —Print: print the values of all items in the tree, using a traversal strategy that is appropriate for the application
  • —Successor: finds the next item in the tree w.r.t current
  • —Predecessor: finds the previous item in the tree w.r.t current

Inserting an item in BST

void Insert(Node *&tree, int item) //’tree’ points to ‘root’ node in 				        // the beginning
{
 if(tree == NULL) {  // base case
   tree = new Node;
   tree->right = NULL;
   tree->left = NULL;
   tree->data = item;
 }
 else if(item < tree->data)
   Insert(tree->left, item);
 else
   Insert(tree->right, item);
}

Finding minimum and maximum

—The minimum element of BST is the left most node of left sub tree. —Therefore the minimum can always be found by tracking the left child pointers until an empty sub tree is  reached. —If there is no left sub tree then minimum key is at root( i.e.   key[ x])

Tree-Minimum(x)
{
      while( x->left != NIL)
      	x = x->left
      return x
}
—The maximum element of BST is the right most node of right sub tree. —Therefore the maximum can always be found by tracking the right child pointers until an empty sub tree is reached.
Tree-Maximum(x)
{
      while( x->right != NIL)
      	x = x->right
      return x
}

Traversing BST

—Many applications require that all of the nodes of a tree be “visited”. —Visiting a node may mean printing contents, retrieving information, making a calculation, etc. —Traverse: To visit all the nodes in a tree in a systematic fashion.

There are mainly three ways to traverse a tree:

  1. In-order Traversal
  2. Post-order Traversal
  3. Pre-order Traversal
1. In-order Traversal:
consider following example, this would be order of traversing in In-order: A E H J M T Y
—Visit the nodes in the left subtree, then visit the root of the tree, then visit the nodes in the right subtree
Inorder(tree) 
If tree is not NULL
  Inorder(Left(tree))
  Visit Info(tree)
  Inorder(Right(tree))
NOTE: “visit” means that the algorithm does something with the values in the node, e.g., print the value.

2. Pre-order Traversal: 

Consider following example, this would be order of traversing in pre-order: J E A H T M Y

—Visit the root of the tree first, then visit the nodes in the left subtree, then visit the nodes in the right subtree
Preorder (tree)
If tree is not NULL
  Visit Info(tree)
  Preorder(Left(tree))
  Preorder(Right(tree))

3. Post-order Traversal: 

Consider following example, this would be order of traversing in post-order: A H E M Y T J

—Visit the nodes in the left subtree first, then visit the nodes in the right subtree, then visit the root of the tree
Postorder (tree)
If tree is not NULL
  Postorder(Left(tree))
  Postorder(Right(tree))
  Visit Info(tree)

Exercise

Find:

  1.   In-order ?
  2.   Pre-order ?
  3.   Post-order ?
for following tree.

Searching the tree

—Start at the root
—Is target = value at current node?
We’re done
—Is target < value at current node?
Yes: search left subtree
No: search right subtree

—When given a pointer to the root of a tree and a key, Tree-Search will return a pointer to the node with key k if there exists one. Suppose  x = root.

Tree-Search (x, k)
{  
   if x=NIL or k= x->data
      return x
   if k < x->data
      return Tree-Search(x->left, k)
   else
      return Tree-Search( x->right, k)
}

—This function follows the BST property, if value of k is smaller than that of x, then it should be in left subtree of x, else it should be in right subtree of x.

—

Successor Function

—The successor of a node x, is node y, that has the smallest key greater than that of x.
  • If x has a right subtree, then successor(x) is the left most element in that sub tree.
  • If x has no right sub tree, then successor(x) is the lowest ancestor of x (above x on the path to the root) that has x in its left sub tree.

  • The successor of node with key 15 is node with key 17.
  • The successor of node with key 7 is node with key 9.
  • The successor of node with key 13 is node with key 15.

Predecessor Function

—The predecessor is the node that has the largest key smaller than that of x—
  • If x has a left sub tree, then the predecessor must be the right most element of the left sub tree.
  • If x has no left sub tree, then predecessor (x) is the lowest ancestor of x (above x on the path to the root) that has x in its right sub tree.

  • The predecessor of node with key 6 is node with key 4.
  • The predecessor of node with key 15 is node with key 13.
  • The predecessor of node with key 17 is node with key 15.

Deleting from BST

—First, find the item; then, delete it. Binary search tree property must be preserved!!

—We need to consider three different cases:

  1. Deleting a leaf
  2. Deleting a node with only one child
  3. Deleting a node with two children

1. Deleting a leaf

2.  Deleting a node with only one child

3.  Deleting a node with two children

  • —Find predecessor (it is the rightmost node in the left subtree) OR —Find successor (it is the leftmost node in the right subtree)
  • ——Replace the data of the node to be deleted with predecessor/successor’s data
  • ——Delete predecessor/successor node
void Delete(Node  *&tree, int  item)
{
 if(item < tree->data)
   Delete(tree->left, item);
 else if(item > tree->data)
   Delete(tree->right, item);
 else
   DeleteNode(tree);
}
void DeleteNode(Node  *&tree)
{
  int  data;
  Node *tempPtr = tree;

  if(tree->left == NULL) { //right child
    tree = tree->right;
    delete tempPtr;
  }
  else if(tree->right == NULL) { // left child
    tree = tree->left;
    delete tempPtr;
 }
 else {
    GetPredecessor(tree->left, data);
    tree->data = data;
    Delete(tree->left, data);
  }
}
void GetPredecessor(Node  * tree, int  &data)
{
 while(tree->right != NULL)
   tree = tree->right;
 data = tree->data;
}

Tagged with: C/C++ languageData structures
 

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 

Looking for something?

Use the form below to search the site:


Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.