PROGRAM:
import java.io.*;
class node
{
public int
tag; //1 for ptr node, 0 for data
node
public int
level; //starts with 1
public node
LC,RC,par; //for ptr node
public int
data; //for data node
}
class trie
{
public node
cptr,root;
trie()
{
root=null;
}
node find(int
key)
{
int item=key;
node
temp=root;
while(temp!=null)// root not empty
{
cptr=temp;
if(temp.tag==1) //temp is a pointer node
{
if((item & 1) ==0) //even
{
temp=temp.LC;
item=item >> 1; //right shift
}
else
{
temp=temp.RC;
item=item
>> 1; //right shift
}
}
else //temp is a data node
{
if(key==temp.data){
return temp;}
else break;
}
}
return null;
}
void insert(int
key)
{
if(root==null)
{
root=new node();
root.data=key;
root.tag=0;
root.level=1;
root.par=null;root.LC=null;root.RC=null;
}
else //trie not empty
{
node temp=find(key);
if(temp==null) //key not in trie
{
temp=cptr;
System.out.println("in find:"+temp.data); //for debug
//cptr points to data node
if(temp.tag==0)
{
node n1=new node();
node n2=new node();
temp.tag=1;
n1.tag=n2.tag=0;
int k1=temp.data; temp.data=0;
int k2=key;
int kk1;
n1.data=k1; n2.data=k2;
int lv=1;
//Branching takes place here
while((k1 & 1) == (k2 & 1))
{
kk1=k1;
k1=k1 >> 1;
k2=k2 >> 1;
//skip already existing branches
if(lv>=temp.level)
{
node n3=new node();
n3.tag=1;
//Branch the new pointer node
towards the left
if((kk1 & 1)==0)
{
temp.LC=n3;
temp.RC=null;
n3.level=temp.level+1;
}
//Branch the new pointer node towards the
left
else
{
temp.RC=n3;
temp.LC=null;
n3.level=temp.level+1;
}
n3.par=temp;
temp=n3; lv++;
}
else lv++;
}//end while
//Branching the data nodes with n1 as a left child
if((k1 & 1)==0)
{
temp.LC=n1;
temp.RC=n2;
n1.level=n2.level=temp.level+1;
}
//Branching the data nodes with n1 as a right child
else
{
temp.LC=n2;
temp.RC=n1;
n1.level=n2.level=temp.level+1;
}
//Setting the par pointer of new data nodes
n1.par=temp; n2.par=temp;
}//end of
cptr points to data node
//cptr
points to pointer node
else
{
node n1=new node();
n1.tag=0;
n1.data=key;
if(temp.LC==null)
temp.LC=n1;
else
temp.RC=n1;
n1.level=temp.level+1;
n1.par=temp;
}
}//end of
if(temp==null)
}//end of else of
if root == null
display(root);
}
void display(node
curr)
{
if(curr!=null )
{
display(curr.LC);
System.out.println("DATA "+curr.data+" TAG-
"+curr.tag+" LEVEL- "+curr.level);
display(curr.RC);
}
}
}
class TrieImp
{
public static void main(String args[])
{
DataInputStream in=new DataInputStream(System.in);
int ch,cont;
int num;
trie t=new
trie();
try
{
do
{
System.out.println("
1.INSERT:");
System.out.println(" Enter ur
choice:");
ch=Integer.parseInt(in.readLine());
if(ch==1)
{
System.out.println(" Enter elt:");
num=Integer.parseInt(in.readLine());
t.insert(num);
}
System.out.println("Press 1 to continue:");
cont=Integer.parseInt(in.readLine());
}while(cont==1);
}
catch(Exception
e){}
}
}
OUTPUT:
ENTER YOUR CHOICE : 1
ENTERT ELEMENTS : 7
11
4
12
8
PRESS 1 TO CONTINUE
GET THE ELEMENTS TO BE INSERTED:13
ENTER YOUR CHOICE : 1
ELEMENTS :
7
11
4
12
8
13
No comments:
Post a Comment