C++ Info: Data Structure

if we make a restriction that each node can have maximum two children we can have binary tree.

The definiation: a binary tree as a tree which is either empty or consists of a root node together
with two binary tree a left subtree and right subtree of the root.

                                                             A
                                                          /      \
                                                         B      C

The definition given above is a recursive definition where an empty binary tree is a base case
which allows the recursion loop.

A binary tree with a single node is a binary tree with a root whose left and right subtrees are empty.

if there are two nodes in the binary tree one will be root and other can be the left child or
the right child of the root.

                 A               C
               /                or            \
              B                                D

A binary tree is called a strictly binary tree if every nonleaf node in the binary tree has nonempty
left and right subtree.
This means each node in a binary tree will have either 0 or 2 children.

A strictly binary tree with n leaves always contain exactly 2n-1 nodes.

A complete binary tree can be defined as a binary tree whose nonleaf nodes have non empty
left and right subtree and all leaves are at the same level.

                                                       A
                                                   /        \
                                                  B        C
                                                 /   \       / \
                                                D   E   F G

If a binary tree has the property that all elements in the left subtree of a node n are less than
the contents of n and all elements in the right subtree are greater than the content of n
such a binary tree is called binary search tree.

As the name suggest they are very useful for searching an element just as with binary search.

A binary search tree is a binary tree which is either empty or contains a node whose key
statisfies the condition:

a) The key in the left child of a node (if any) precees the key in the parent node

b) The key in the right child of a node (if any) suceesds the key in the parent node

c) The left and right subtree of the root are again binary search tree.

we are assuming that there are no duplicates which means that no two entries in binary
search tree can have equal keys.

Binary Tree Representations

Tree node may be implemented as array element or as dynamically allocated variables.
Each node of a tree contains info left and right field.

Using the array implemenation we may declare

#define maxnum 100
struct nodetree {
int info;
int left;
int right;
}

struct nodetree node[maxnum];
here we can refer to the info,left and right field of a node as a node[p].info,
node[p].left and node[p].right respectively.

This representation is called as linked array represenation.

we can also define a node as

struct nodetree
{
     int info;
     struct nodetree *left,*right;
}tree;

struct nodetree *p;

Now the fileds info left right of a node p can be referred as p->info,
p->left and p->right respectively. This representation is called the dynamic node
representation of binary tree.

Operation on binary tree

To search the tree we use a traversal pointer p and set it equal to the root of the tree. Then we comparethe info field of p with the given value. if the info is equal to x we exit the routine and return the current value of p. if the x is less than info p we search in the left subtree of p otherwise we search in the right
subtree by making p equal to p->right we continue searching untill we have found the desire value or reach the end of the tree.

search(p,x)
int x;

struct tree *p;
{
       p=root;
       while(p!=NULL && p->info !=x)
       {
                   if(p->info >x)
                         p =p->left;
                   else
                         p->right;
          }

          return p;
}

Insertion into a Tree
Another important operation is to create and maintain a binnary search tree. A new node
will always be inserted at its proper position in the binary search tree as a leaf

While inserting any node we have to take that the resulting tree statisfie the properties of
binary search tree.

A new node will always be inserted at the proper position in the binary search tree as a leaf.

Before writing a routine for inserting a node let us see how a binary tree may be
created for following input.

10,15,12,7,8,18,6,20

First of all we must initialize the tree . To create an empty tree we must initialize root to null.

The first node will be inserted into the tree as a root.

                        10
                       /    \
                      7      15
                     /  \    /    \
                    6    8 12    18
                                       \
                                       20

To find the insertion place for the new value we initialize temporary pointer p which point to the root node we can change p to move left and right through the tree as we did for searching
a particular value in the tree.

When p becomes null it is not possible to the link new node at this position becuase there is no
access to the node p was pointing to just before it became null.

P become null when we have found that 17 will be inserted at the left of 18 so we need a way to climb back into the tree so that we can access node cotaining 18 in order to make its left
pointer point to node 17

We must therefore need a pointer which points to a node cotaining 18 when p becomes null
To achieve this we have another pointer which must follow p as it moves through the tree

When p become null this pointer will point to the leaf node to which we will the new node

The algorithum to insert a new node is as follows.

/* get a new node and make it a leaf
getnode(q);
left(q)=null;
right(q)=null;
info(q)=x;
/* Initialize the traversal pointer */

p=root
trail =null

/* search for the insertion place */
while p<>null do
begin
trail =p
if info(p)> x
           then p=left(p)
            else p=right(p)
end

/* To adjust the pointer*/
if trail =null
then root =q
else
if info(trail) >X
    then left(trail) =q
    else right(trail)=q

The insertion algorithum can be coded into a C routine.There are two parameters
which msut be passed to this routine.

one is tree and other is the value to be inserted x.

tree insert(s,x)

int x;
tree *s;
{
     tree   *trail,*p,*q;

     q=(tree*) malloc(sizeof(tree));
q->info =x;
      q->left =null;
      q->rigth =null;

   p =s;
   trail =null;

while(p!=null)
{
   trail =p;
   if(p->info >x)
           p=p>left
               else
                     p=p->right;
        }

       if trail ==null
       {
              s=q;
               return (s);
        }

        if(info(trail)>x)
               left(trail)=q;
        else
                right(trail)=q;
          return(s);
}

Deletion from a binary search tree

Another important function for maintaining binary search tree is to delete a specific
node from the tree. The method to delete a node depends on the specific position
of the node in the tree.

if the node to be deleted is a leaf, we only need to set the appropiate link of its parent
to nil and dispose of the node which is deleted.

if the node to be deleted has only one child we can not make the link of the parent
to nil as we have done in the case of leaf becuase if we do so we will loose all of the
descendants of the node which we are deleting from the tree.

so we need to adjust the link from the parent of the deleted node to the point to the
child of the node we intend to delete.

The most complicated problems comes when we have to delete a node with two
children.

There is no way we can make the parent of the deleted node to point to both
of the children of the deleted node.

So we attach one of the subtree of the nodes to be deleted to the parent and then
hang the other subtree onto the appropriate node of the first sub tree

Let us attach right subtree to the parent node of the right subtree since every key
in the left subtree is less than every key in the right subtree.

Therefore we must attach the left subtree as far to the left as possible.
This proper place can be found by going left untill an empty left subtree is found

For example we want to delete x.

                      r
                   /    \
                 q        x
                        /   \
                       t      y
                    /   \      \
                   s    u       z
if we delete node containing x we make parent of x to point to the right
subtree and then go as far as left possible and attach the left subtree there

To understand in better way let us look at some more examples of these type of deletion

void delete (p)
struct tree *p;
{
      struct tree *temp;

      if(p==null)
      cout<<" trying to delete a non existent"<<endl;

    else if ( p->left ==null)
    {
           temp =p;
          p=p->right;
         free(temp);
     }

    else if( p-> right ==null)
   {
          temp =p;
          p=p->left;
          free(temp);
    }

   else if( p->left != NULL && p->right !=NULL)
   {
        temp =p->right;

         while(temp ->left !=null)
                    temp= temp ->left;

           temp->left = p->left;
           temp=p;
         p=p->right;
           free(temp);
    }

Notice that the while loop stop stop when it finds a node with an empty left subtree
and not when it finds an empty subtree itself. So that the left subtree of the node to be deleted
can be attached here.

Also note that we first attach the left subtree at the proper plcae and then attach the right
subtree to the parent of the node to be deleted.

Some more info
http://www.algolist.net/Data_structures/Binary_search_tree/Removal

Tree Traversals
Another useful operation on a binary tree is a traversal which is to move all the nodes
of the binary tree visiting each one in turn for example to print all of the values in the tree

At a given order, there are three things to do in the some order.To visit the node itself
to traverse its left subtree and to taverse its right subtree.
Depending on the whether we traverse the node itself before traversing either subtree
between the subtree or after traversing both subtrees there are many orders in which
we can traverse all the nodes

Depending of the position at which the given node or the root is visited the name is given

if the root is visited before traversing its subtree it is called the pre order traversal

if the root is visited after traversing its subtree it is called the post order traversal

if the root is visited in between the subtree it is called in order traversal

                           A
                         / \
                       B   C
       Pre Order -->(root,left,right) ABC

       Post Order --> (left,right,root) BCA

       In Order ---> (left,root,right) BAC

       Wiki Pages : http://en.wikipedia.org/wiki/Tree_traversal

      Some info about Tree : http://nptel.iitm.ac.in/courses/Webcourse-contents/IIT-%20Guwahati/data_str_algo/frameset.htm

Very Good Exersize for tree traversal

http://nova.umuc.edu/~jarc/idsv/

void inorder(p);
struct tree *p
{
if(p!=NULL)
{
   inorder(p->left)
               printf("%c,p->info);

               inorder(p->right);
        }
}

void preorder(p)
struct tree *p
{
        if(p!=NULL)
        {
                printf("%c,p->info);
              preorder(p->left);
preorder(p->right);
}
}

void postorder(p)
struct tree *p;
{
   if(p!=NULL)
   {
   postorder(p->left);
   postorder(p->right);
   printf("%c",p->info);
}
}

Preorder traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)
Inorder traversal sequence: A, B, C, D, E, F, G, H, I (left, root, right); note how this produces a sorted sequence
Postorder traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)
Level-order traversal sequence: F, B, G, A, D, I, C, E, H

      Level Oder traversal :
      http://neural.cs.nthu.edu.tw/jang/courses/cs2351/slide/animation/Level%20Order%20Traversal%20of%20a%20Binary%20Tree.pps

     http://www.thecareerplus.com/?page=resources&cat=10&subCat=75&qNo=12

Some Pratical use

Hashing:
What is hashing or hash function?
Producing hash value for for accesing data.A hash value also call message digest is a number
generated from hash function. A hash function will generate a unique key value to search data.

Hash seacrh?
A hash search is a search in which the key,through an algorithum function determines the location of
the data.
we use a hashing algo to transform the key into the index that contain the data we need to locate.

Binary tree info