Binary Tree and its Implementation in Database

A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subset of tree.The first subset contains a single element called the root and other two are left and right sub trees which

can be also empty.Each element of a binary tree is called nodes of the tree.

A rooted tree is called binary tree if every internal vertex has no more than two children.

Types of Binary tree:_

a)Strictly / fully binary tree

b)complete binary tree

c)almost complete binary tree

a)Strictly/full binary tree

    If every non-leaf node in binary tree has non-empty left and right sub tree then it is called strictly binary tree i.e. every internal  node has exactly two children.It must contains n=2L-1 nodes and  i=L-1 internal nodes for L leaves.

b)complete binary tree

   It is strictly binary tree of depth d whose all leaves are at level d.It contains 2^h ( 2^d ) nodes at height h.

c)almost complete binary tree

   A binary tree of depth d is an almost complete binary tree if -

  1)Any node (nd) at level less than d-1 has two sons

  2)For any node (nd) in the tree with right descendant at level d,must have a left son and every left descendent of node (nd) is either a leaf at level d or has two sons.

For inserting a node in binary tree

   i)Declare and initialize necessary variables

   ii)Read the data item to be inserted in the tree say x

   iii)create a new node with its left and right pointer to NULL

   iv)Assign data x to info field of new node

   v)    IF(tree==NULL)

                tree=address of new node

                ELSE  IF(x<tree->info) ------------------( 1 )

                           IF(tree->left==NULL)

                              tree->left=new node

                           ELSE

                               tree=tree->left

                               Repeat from  line no 1

                 ELSE IF(x>tree->info)------------------( 2 )

                          IF(tree->right=NULL)

                               tree->right=new node

                          ELSE

                                tree=tree->right

                                Repeat form line no 2

           ELSE  IF(x==tree->info )

                     Print”Duplicated data”and exit

vi)For next insertion go to step 5

vii)stop

Deletion in binary tree

     i)Declare and initialize necessary variables

    ii)read data to be deleted say x

    iii)Find the node where data is exist

             IF node is not found

                  Print”Node not found ” and exit

    v)IF the node has no subtrees

         then assign the father node’s pointer with NULL that points to the node

         delete the node that contains data item

   v)IF the node has to be deleted has only one sub tree

            move its son up to take it place

           delete the node that contains data item

   vi)IF the node has to be deleted of node to be deleted

        set the information of node to be deleted by the information of leftmost node of right 

         sub tree of the  node to be deleted

   vii)For next deletion go to step2

   viii)stop