Binary Search Tree

The property that makes a Binary Tree into Binary Search Tree is that for every node, X, in the tree, the values of all the keys in the left subtree are smaller than the key value in X and the values of all the keys in the right subtree are larger than or equal to key value in X.

Example of a Binary Search Tree is:

The class to implement Binary Search Tree :

// Node class

template < class Etype >
class TreeNode
{
public:
        Etype element;
        TreeNode* Left;
        TreeNode* Right;
        TreeNode( Etype e = 0, TreeNode* l = NULL, TreeNode* r = NULL) : 
        element ( e), left ( l ), right ( r ) { }
        friend int height ( TreeNode *T);
        friend void inOrderTraversal ( TreeNode *T);
        friend void preOrderTraversal ( TreeNode *T);
        friend void postOrderTraversal ( TreeNode *T);
        friend class BinarySearchTree < Etype >;
};

// Binary Search Tree Class

template<class Etype>
class BinarySearchTree
{
public: 
         BinarySearchTree ( ) : Root ( NULL ) { }
         void insert ( const Etype & x ) {  insert ( x, root ); }
         void remove ( const Etype& x ) { Remove (  x, root ); }
private:
         void insert ( const Etype& x, TreeNode<Etype>* & T );
         void remove ( const Etype& x, TreeNode<Etype>* & T);
         TreeNode *root;
};

Height:

int height ( TreeNode *T)
{
        return ( T ? 1 + Max ( height ( T-> left ), height ( T-> right ) ) : 0 ) ; 
}

Inorder Traversal:

void inOrderTraversal ( TreeNode *T)
{
       if ( T )
       {
                inOrderTraversal ( T-> left );
                cout<< T-> element;
                inOrderTraversal ( T-> right);
        }
}

Preorder Traversal:


void preOrderTraversal ( TreeNode *T)
{
       if ( T )
       {
                cout<< T-> element;
                preOrderTraversal ( T-> left );
                preOrderTraversal ( T-> right);

        }

}

Postorder Traversal:


void postOrderTraversal ( TreeNode *T)
{
       if ( T )
       {
                postOrderTraversal ( T-> left );
                postOrderTraversal ( T-> right);
                cout<< T-> element;
        }

}




Insert:

Following image shows how to insert an element in Binary Search Tree:

Following is the implementation of insert( ) function:

template < class Etype >
void BinarSearchTree< Etype > :: insert ( const Etype & x, TreeNode<Etype> * & T)
{
         if ( T = = NULL )
                 T = new TreeNode<Etype> ( x );
        else
        {
                 if ( x < T -> element )
                          insert ( x, T->left );
                 else if ( x > T-> element)
                          insert ( T-> right )
         }
}


Remove:

Following image shows how to remove an element in Binary Search Tree:

Following is the implementation of remove( ) function:

template < class Etype >
void BinarySearchTree< Etype > :: remove ( const Etype & x, TreeNode<Etype> * & T)
{
        TreeNode<Etype> *tmpCell;
   
        if ( T = = NULL )
                 cout << " Element Not Found ";
        else if ( x < T-> element )
                 remove ( x, T-> left );
        else if ( x > T-> element )
                 remove ( x, T-> right );
        else       // element found
        {
                  if ( T-> left != NULL && T -> right != NULL )
                  {
                            tmpCell = findMin ( T-> right );   // Minimum element
                            T-> element = tmpCell -> element;
                            remove ( T->element, T->right );
                  }
                 else
                 {
                          tmpCell = T;
                          if ( T-> left)
                                     T = T-> left;
                         else if ( T-> right )
                                     T = T-> right;
                         delete tmpCell;
                  }
        }
}

Linked List

Well the first Data Structure that we studied is Linked List and it also provides a way to implement various Advance Data Structures. It can be defined in the following way --

                    "A Linked List is a Data Structure that consists of a sequence of Data Records such that in each record there is a field that contains a reference or link to the next record in the sequence."

Above is the Singly Linked List in which each node has data and a link to the next node in the List. Head node is the start of the List. Next of the last node in the List is NULL.

To implement Singly Linked List, I used following way (C++) --

template <class Etype>

class List

{

     struct Node

     {

            Etype element;

            Node *next;

            Node(Etype E = 0, Node *N = NULL) : element ( E ), next ( N ) { }

      };

    

     Node *head; // start position of head 

     Node *curr;  // To optimize and support many operation, think what we can do with this

   // then various operations, constructors, destructors etc.

};

* In My implementation, head is always in the list even in the case of empty list and head will remain same for lifetime of a list object.


Insert ::
//Insert after curr

template < class Etype  >
void List < Etype > :: insert ( const Etype & data )
{
     curr->next = new Node (data, curr->next );
}

See the following figure for more clarification, it shows insert( 30 ) --

Remove ::
template < class Etype >
int List < Etype > :: remove ( const Etype & data )
{
      if ( Find_Prev( data ) )   // set curr to the node whose next node's element is data
      {
              Node *toDelete = curr->next;
              curr->next = toDelete->next;
              delete toDelete;
               return 1;
      }
      return 0;
}

Following figure shows remove( 8 )