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);
}
bnode
split(bnode t,bnode p)
{
bnode n1=null;
bnode n2=null;
if(t.data1<p.data1)
{
if(p.mptr!=null)
n1=p.mptr;
if(p.rptr!=null)
n2=p.rptr;
p.lptr=new bnode();
p.lptr=t;
t.parent=p;
p.mptr=null;
p.rptr=new bnode();
p.rptr.data1=p.data2;
p.rptr.lptr=n1;
if(n1!=null)
p.rptr.lptr.parent=p.rptr;
p.rptr.rptr=n2;
if(n2!=null)
p.rptr.rptr.parent=p.rptr;
p.rptr.parent=p;
p.data2=0;
}
else if((t.data1>p.data1)
&& (t.data1<p.data2))
{
if(p.lptr!=null)
n1=p.lptr;
if(p.rptr!=null)
n2=p.rptr;
p.lptr=new bnode();
p.lptr.data1=p.data1;
p.lptr.parent=p;
p.data1=t.data1;
p.lptr.lptr=n1;
if(n1!=null)
p.lptr.lptr.parent=p.lptr;
p.lptr.rptr=t.lptr;
if(t.lptr!=null)
p.lptr.rptr.parent=p.lptr;
p.rptr=new bnode();
p.rptr.data1=p.data2;
p.rptr.rptr=n2;
if(n2!=null)
p.rptr.rptr.parent=p.rptr;
p.rptr.lptr=t.rptr;
if(t.rptr!=null)
p.rptr.lptr.parent=p.rptr;
p.rptr.parent=p;
p.data2=0;
p.mptr=null;
}
else
{
if(p.lptr!=null)
n1=p.lptr;
if(p.mptr!=null)
n2=p.mptr;
p.lptr=new bnode();
p.lptr.data1=p.data1;
p.lptr.parent=p;
p.mptr=null;
p.lptr.lptr=n1;
if(n1!=null)
p.lptr.lptr.parent=p.lptr;
p.lptr.rptr=n2;
if(n2!=null)
p.lptr.rptr.parent=p.lptr;
p.data1=p.data2;
p.data2=0;
p.rptr=new bnode();
p.rptr=t;
p.rptr.parent=p;
}
return
p;
}
void display(bnode temp)
{
if(temp!=null)
{
display(temp.lptr);
display(temp.mptr);
display(temp.rptr);
System.out.println("data1::"+temp.data1+"
data2::"+temp.
data2+"
Address::"+temp+" parent::"+temp.parent);
}
}
}
class btrees
{
public
static void main(String[] args)throws IOException
{
System.out.println("B-Trees");
DataInputStream in=new DataInputStream(System.in);
btree bt=new btree();
int
x,ch;
do
{
System.out.println("Enter the element");
x=Integer.parseInt(in.readLine());
bt.insert(x);
System.out.println("To continue...press 1");
ch=Integer.parseInt(in.readLine());
}while(ch==1);
}
}
OUTPUT:
--------
B-Trees
Enter the element
52
data1::52 data2::0 Address::bnode@923e30 parent::null
To continue...press 1
1
Enter the element
45
data1::45 data2::52 Address::bnode@923e30 parent::null
To continue...press 1
1
Enter the element
89
data1::45 data2::0 Address::bnode@130c19b
parent::bnode@923e30
data1::89 data2::0 Address::bnode@1f6a7b9
parent::bnode@923e30
data1::52 data2::0 Address::bnode@923e30 parent::null
To continue...press 1
1
Enter the element
12
data1::12 data2::45 Address::bnode@130c19b
parent::bnode@923e30
data1::89 data2::0 Address::bnode@1f6a7b9
parent::bnode@923e30
data1::52 data2::0 Address::bnode@923e30 parent::null
To continue...press 1
1
Enter the element
56
data1::12 data2::45 Address::bnode@130c19b
parent::bnode@923e30
data1::56 data2::89 Address::bnode@1f6a7b9
parent::bnode@923e30
data1::52 data2::0 Address::bnode@923e30 parent::null
To continue...press 1
1
Enter the element
1
data1::1 data2::0 Address::bnode@7d772e parent::bnode@923e30
data1::45 data2::0 Address::bnode@11b86e7
parent::bnode@923e30
data1::56 data2::89 Address::bnode@1f6a7b9
parent::bnode@923e30
data1::12 data2::52 Address::bnode@923e30 parent::null
To continue...press 1
1
Enter the element
32
data1::1 data2::0 Address::bnode@7d772e
parent::bnode@923e30
data1::32 data2::45 Address::bnode@11b86e7
parent::bnode@923e30
data1::56 data2::89 Address::bnode@1f6a7b9
parent::bnode@923e30
data1::12 data2::52 Address::bnode@923e30 parent::null
To continue...press 1
1
Enter the element
25
data1::1 data2::0 Address::bnode@7d772e
parent::bnode@35ce36
data1::25 data2::0 Address::bnode@757aef
parent::bnode@35ce36
data1::12 data2::0 Address::bnode@35ce36
parent::bnode@923e30
data1::45 data2::0 Address::bnode@d9f9c3 parent::bnode@9cab16
data1::56 data2::89 Address::bnode@1f6a7b9
parent::bnode@9cab16
data1::52 data2::0 Address::bnode@9cab16
parent::bnode@923e30
data1::32 data2::0 Address::bnode@923e30 parent::null
To continue...press 1
1
Enter the element
60
data1::1 data2::0 Address::bnode@7d772e
parent::bnode@35ce36
data1::25 data2::0 Address::bnode@757aef
parent::bnode@35ce36
data1::12 data2::0 Address::bnode@35ce36
parent::bnode@923e30
data1::45 data2::0 Address::bnode@d9f9c3
parent::bnode@9cab16
data1::56 data2::0 Address::bnode@1a46e30
parent::bnode@9cab16
data1::89 data2::0 Address::bnode@3e25a5
parent::bnode@9cab16
data1::52 data2::60 Address::bnode@9cab16
parent::bnode@923e30
data1::32 data2::0 Address::bnode@923e30 parent::null
To continue...press 1
1
Enter the element
83
data1::1 data2::0 Address::bnode@7d772e
parent::bnode@35ce36
data1::25 data2::0 Address::bnode@757aef
parent::bnode@35ce36
data1::12 data2::0 Address::bnode@35ce36
parent::bnode@923e30
data1::45 data2::0 Address::bnode@d9f9c3
parent::bnode@9cab16
data1::56 data2::0 Address::bnode@1a46e30
parent::bnode@9cab16
data1::83 data2::89 Address::bnode@3e25a5
parent::bnode@9cab16
data1::52 data2::60 Address::bnode@9cab16
parent::bnode@923e30
data1::32 data2::0 Address::bnode@923e30 parent::null
To continue...press 1
12
Thus the program
for b-tree using Java has been implemented.
No comments:
Post a Comment