B-TREE
Program Coding:
import java.io.*;
import java.util.*;
import java.lang.*;
class dataitem
{
public int ddata;
public dataitem()
{
ddata=0;
}
public dataitem(int dd)
{
ddata=dd;
}
public void displayitem()
{
System.out.print("/"+ddata);
}
}
class node extends dataitem
{
private static final int ORDER=4;
private int numitems;
private node parent;
private node childarray[]=new
node[ORDER];
private dataitem itemarray[]=new
dataitem[ORDER-1];
public void connectchild(int
childnum,node child)
{
childarray[childnum]=child;
if(child!=null)
child.parent=this;
}
public node disconnectchild(int
childnum)
{
node tempnode=childarray[childnum];
childarray[childnum]=null;
return tempnode;
}
public node getchild(int childnum)
{
return childarray[childnum];
}
public node getparent()
{
return parent;
}
public boolean isleaf()
{
return (childarray[0]==null)?true:false;
}
public int getnumitems()
{
return numitems;
}
public dataitem getitem(int index)
{
return itemarray[index];
}
public boolean isFull()
{
return (numitems==ORDER-1)?true:false;
}
public int finditem(int key)
{
for(int j=0;j<ORDER-1;j++)
{
if(itemarray[j]==null)
break;
else if(itemarray[j].ddata==key)
return j;
}
return -1;
}
public int insertitem(dataitem newitem)
{
numitems++;
int newkey=newitem.ddata;
for(int j=ORDER-2;j>=0;j--)
{
if(itemarray[j]==null)
continue;
else
{
int itskey=itemarray[j].ddata;
if(newkey<itskey)
itemarray[j+1]=itemarray[j];
else
{
itemarray[j+1]=newitem;
return j+1;
}
}
}
itemarray[0]=newitem;
return 0;
}
public dataitem removeitem()
{
dataitem temp=itemarray[numitems-1];
itemarray[numitems-1]=null;
numitems--;
return temp;
}
public void displaynode()
{
for(int j=0;j<numitems;j++)
itemarray[j].displayitem();
System.out.println("\n");
}
}
class tree234 extends node
{
private node root=new node();
public int find(int key)
{
node curnode=root;
int childnumber;
while(true)
{
if((childnumber=curnode.finditem(key))!=-1)
return childnumber;
else if(curnode.isleaf())
return -1;
else
curnode=getnextchild(curnode,key);
}
}
public void insert(int dvalue)
{
node curnode=root;
dataitem tempitem=new
dataitem(dvalue);
while(true)
{
if(curnode.isFull())
{
split(curnode);
curnode=curnode.getparent();
curnode=getnextchild(curnode,dvalue);
}
else if(curnode.isleaf())
break;
else
curnode=getnextchild(curnode,dvalue);
}
curnode.insertitem(tempitem);
}
public void split(node thisnode)
{
dataitem itemb,itemc;
node parent,child2,child3;
int itemindex;
itemc=thisnode.removeitem();
itemb=thisnode.removeitem();
child2=thisnode.disconnectchild(2);
child3=thisnode.disconnectchild(3);
node newright=new node();
if(thisnode==root)
{
root=new node();
parent=root;
root.connectchild(0,thisnode);
}
else
parent=thisnode.getparent();
itemindex=parent.insertitem(itemb);
int n=parent.getnumitems();
for(int j=n-1;j>itemindex;j--)
{
node temp=parent.disconnectchild(j);
parent.connectchild(j+1,temp);
}
parent.connectchild(itemindex+1,newright);
newright.insertitem(itemc);
newright.connectchild(0,child2);
newright.connectchild(1,child3);
}
public node getnextchild(node
thenode,int thevalue)
{
int j;
int numitems=thenode.getnumitems();
for(j=0;j<numitems;j++)
{
if(thevalue<thenode.getitem(j).ddata)
return thenode.getchild(j);
}
return thenode.getchild(j);
}
public void displaytree()
{
recdisplaytree(root,0,0);
}
private void recdisplaytree(node
thisnode,int level,int childnumber)
{
System.out.print("level="+level+"child="+childnumber+"
");
thisnode.displaynode();
int
numitems=thisnode.getnumitems();
for(int j=0;j<numitems+1;j++)
{
node nextnode=thisnode.getchild(j);
if(nextnode!=null)
recdisplaytree(nextnode,level+1,j);
else
return;
}
}
}
class btree234app extends tree234
{
public static void main(String[]
args)throws IOException
{
int value;
tree234 thetree=new tree234();
int data[]=new int[20];
char choice='i';
int e1,nee1;
BufferedReader ne=new BufferedReader(new
InputStreamReader(System.in));
BufferedReader ch=new
BufferedReader(new InputStreamReader(System.in));
try
{
System.out.println("ENTER NO
OF ELEMENTS:\t\n");
BufferedReader br=new
BufferedReader(new InputStreamReader(System.in));
e1=Integer.parseInt(br.readLine());
System.out.println("ENTER THE
ELEMENTS:\n");
BufferedReader da=new
BufferedReader(new InputStreamReader(System.in));
for(int i=0;i<e1;i++)
{
data[i]=Integer.parseInt(da.readLine());
thetree.insert(data[i]);
}
}
catch(Exception e)
{
System.out.println(e);
}
while(choice!='e')
{
System.out.print("ENTER FIRST
LETTER OF ");
System.out.print("SHOW,INSERT,
FIND OR EXIT:");
choice=getChar();
switch(choice)
{
case 's':
thetree.displaytree();
break;
case 'i':
System.out.print("ENTER VALUE
TO INSERT:");
value=getInt();
thetree.insert(value);
break;
case 'f':
System.out.print("ENTER VALUE
TO FIND:");
value=getInt();
int found=thetree.find(value);
if(found!=-1)
System.out.println("FOUND"+value);
else
System.out.println("COULD NOT
FIND"+value);
break;
case 'e':
break;
default:
System.out.print("INVALID
ENTRY \n");
}
}
}
public static String getString()
throws IOException
{
InputStreamReader isr=new
InputStreamReader(System.in);
BufferedReader br=new
BufferedReader(isr);
String s=br.readLine();
return s;
}
public static char getChar() throws
IOException
{
String s=getString();
return s.charAt(0);
}
public static int getInt() throws
IOException
{
String s=getString();
return Integer.parseInt(s);
}
}
Output:
BTREE
Enter the no. of
elements:
4
Enter the
elements:
20
40
30
50
Enter first
letter of show, insert, find or exit: s
Level=0
child=0/30
Level=1
child=0/20
Level=1
child=1/40/50
Enter first
letter of show, insert, find or exit: i
Enter the value
to insert: 25
Enter first
letter of show, insert, find or exit: s
Level=0
child=0/30
Level=1
child=0/20/25
Level=1
child=1/40/50
Enter first
letter of show, insert, find or exit: f
Enter the value
to find: 25
FOUND 25
Enter first
letter of show, insert, find or exit: e
excellent........
ReplyDelete