B-TREE

AIM

To implement the b-tree with insert and delete operations using Java.

ALGORITHM

Step 1:                    Start the program by defining function.

Step 2:                    Declare the class btree

Step 3:                    The insert and delete operations are performed

Step 4:                    To insert, check if root is empty, if it is empty

                     insert the element as root.
                

Step 5:                    If it is greater insert it into right sub tree.

Step 6:                    Otherwise, insert it into left sub tree

Step 7:                    Use the function split, to split the nodes

Step 8:                    Call the function display to display

                     data1,data2,address and parent

Step 9:                    End of the program

PROGRAM

B-TREE

import java.io.*;

class bnode

{

        int data1,data2;

        bnode lptr,mptr,rptr,parent;

        public void bnode()

        {

                this.data1=this.data2=0;

                this.lptr=this.mptr=this.rptr=this.parent=null;

        }

}

class btree

{

        bnode root=null;

        bnode p,p1;

        bnode prev;

        void insert(int ele)

        {

                bnode temp=new bnode();

                temp.data1=ele;

                if(root==null)

                {

                        root=temp;

                }

                else

                {

                       p1=root;

                       while(p1!=null)

                       {

                       prev=p1;

                       if(temp.data1<p1.data1)

                       p1=p1.lptr;

                       else if((temp.data1>p1.data1) &&(temp.data1<p1.data2))                                                           

                       p1=p1.mptr;

                       else

                       p1=p1.rptr;

                 }

                       p1=prev;

                       while(p1!=null)

                       {

                               if(p1.data2==0)

                                {

                                        if(temp.data1<p1.data1)

                                        {

                                                int t=p1.data1;

                                                p1.data1=temp.data1;

                                                p1.data2=t;

                                                p1.lptr=temp.lptr;

                                                if(temp.lptr!=null)

                                                temp.lptr.parent=p1;                                           

                                                p1.mptr=temp.rptr;

                                                if(temp.rptr!=null)

                                                 temp.rptr.parent=p1;

                                        }

                                        else

                                        {

                                                p1.data2=temp.data1;

                                                p1.mptr=temp.lptr;

                                                if(temp.lptr!=null)

                                                temp.lptr.parent=p1;

                                                p1.rptr=temp.rptr;

                                                if(temp.rptr!=null)

                                                temp.rptr.parent=p1;

                                        }

                                        temp.parent=p1.parent;

                                        break;

                                }

                                else if((p1.data1!=0) && (p1.data2!=0))

                                {

                                        p1=split(temp,p1);

                                        temp=p1;

                                        p1=p1.parent;

                                }

                        }

                }

              display(root);

        }

B-TREE

PROGRAM:

import java.io.*;

class Node

{

Node left;

Node right;

int value;

public Node(int value)

{

this.value = value;

}

}

public class BTree

{

public static void main(String[] args)throws Exception

{

Node rootnode = new Node(25);

Operation op = new Operation();;

System.out.println("Building tree with rootvalue"+rootnode.value);

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

System.out.println("Enter the no of nodes");

String size=br.readLine();

int si=Integer.parseInt(size);

for(int i=0;i<si;i++)

{

System.out.println("Enter the element");

String element=br.readLine();

int elements=0;

elements=Integer.parseInt(element);

op.insert(rootnode,elements);

System.out.println("Traversing tree in order");

op.printInOrder(rootnode);

}

}

}

class Operation{

static void insert(Node node, int value)

{

if (value < node.value)

{

if (node.left != null)

{

insert(node.left, value);

}

else

{

System.out.println("  Inserted " + value +" to left of node " + node.value);

node.left = new Node(value);

}

}

else if (value > node.value)

{

if (node.right != null)

{

insert(node.right, value);

}

else

{

System.out.println(" Inserted " + value + " to right of node " + node.value);

node.right = new Node(value);

}

}

}

public void printInOrder(Node node)

{

if (node != null)

{

printInOrder(node.left);

System.out.println("  Traversed " + node.value);

printInOrder(node.right);

}

}

}