AIM
To implement the tries with insert
& delete operations using Java.
ALGORITHM
Step 1:
Start the program by defining the functions.
Step 2:
First initialize
the node to null
Step 3:
to find the particular element use function find
check the element to root node, if
it is not found check for left or right side of the root. If its found return
the element
Step 4:
to insert the particular element read that elemnt and
insert the element
with tag as 0 and level as 1.
Step 5:
to display the elements ,display if root as null, print
as
empty, otherwise
call empty
Step
6:
print the current node in left sub tre in the format as
currentnode.data + level and tag.
Step 7:
display current node in the right sub tree
Step 8:
end of the program
PROGRAM
TRIES
import java.io.*;
class node
{
public int tag,level;
starts with 1
public int
data;
public node
LC,RC,par;
}
class trie
{
public node
cptr;
public node
root=null;
public node
find(int key)
{
int
item=key;
node
temp=root;
while(temp!=null)
{
cptr=temp;
if(temp.tag==1)
{
if((item
& 1)==0)
{
temp=temp.LC;
item=item
>> 1;
}
else
{
temp=temp.RC;
item=item
>> 1;
}
}
else
{
if(key==temp.data)
{
return
temp;
}
else
break;
}
}
return
null;
}
public void
insert()
{
int
key=0;
try
{
System.out.println("Enter the element:");
DataInputStream din=new
DataInputStream(System.in);
key=Integer.parseInt(din.readLine());
}
catch(Exception e){}
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
{
node
temp=find(key);
if(temp==null)
{
temp=cptr;
if(temp.tag==0)
{
node
n1=new node();
node
n2=new node();
temp.tag=1;
n1.tag=0;n2.tag=0;
int
k1=temp.data;temp.data=0;
int
k2=key;
int
kk1;
n1.data=k1;
n2.data=k2;
int
lv=1;
while
( (k1 & 1 ) ==(k2 & 1 ))
{
kk1=k1;
k1=k1
>> 1;
k2=k2
>> 1;
if(lv>=temp.level)
{
node
n3=new node();
n3.tag=1; if ( (kk1 &
1)==0)
{
temp.LC=n3;
temp.RC=null;
n3.level=temp.level+1;
}
else
{
temp.RC=n3;
temp.LC=null;
n3.level=temp.level+1;
}
n3.par=temp;
temp=n3;
lv++;
}
else
lv++;
}
if(
(k1 & 1)==0)
{
temp.LC=n1;
temp.RC=n2;
n1.level=n2.level=temp.level+1;
}
else
{
temp.LC=n2;
temp.RC=n1;
n1.level=n2.level=temp.level+1;
}
n1.par=temp;
n2.par=temp;
}
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;
}
}
else
System.out.println("Element already exists");
}
}
public void display()
{
if(root==null)
System.out.println("EMPTY");
else
{
System.out.println("\nIn Order");
dispin(root);
}
}
public void
dispin(node currentnode)
{
if(currentnode!=null)
{
dispin(currentnode.LC);
System.out.println(currentnode.data+" "+"LEVEL- "+currentnode.level+" "+"TAG-"+currentnode.tag);
dispin(currentnode.RC);
}
}
};
class TrieImp
{
public static
void main(String args[ ])throws IOException
{
int
ch=0,cont=0;
trie t = new trie();
do
{
System.out.println("TRIES 1. Insert
");
DataInputStream din = new DataInputStream(System.in);
try
{
ch=Integer.parseInt(din.readLine());
}
catch(Exception e){}
if(ch==1)
{
t.insert();
t.display();
}
else
{
System.out.println("Enter the correct choice");
}
System.out.println("press 1 to continue:");
try
{
cont=Integer.parseInt(din.readLine());
}
catch(Exception e){}
}while(cont==1);
}
}
OUTPUT:
-------
TRIES 1. Insert
1
Enter the element:
1232
In Order
1232 LEVEL-
1 TAG-0
press 1 to continue:
1
TRIES 1. Insert
1
Enter the element:
4451
In Order
1232 LEVEL-
2 TAG-0
0 LEVEL- 1 TAG-1
4451 LEVEL-
2 TAG-0
press 1 to continue:
1
TRIES 1. Insert
1
Enter the element:
1243
In Order
1232 LEVEL-
2 TAG-0
0 LEVEL- 1 TAG-1
0 LEVEL- 2 TAG-1
4451 LEVEL-
5 TAG-0
0 LEVEL- 4 TAG-1
1243 LEVEL-
5 TAG-0
0 LEVEL- 3 TAG-1
press 1 to continue:
1
TRIES 1. Insert
1
Enter the element:
1015
In Order
1232 LEVEL-
2 TAG-0
0 LEVEL- 1 TAG-1
0 LEVEL- 2 TAG-1
4451 LEVEL-
5 TAG-0
0 LEVEL- 4 TAG-1
1243 LEVEL-
5 TAG-0
0 LEVEL- 3 TAG-1
1015 LEVEL-
4 TAG-0
press 1 to continue:
1
TRIES 1. Insert
1
Enter the element:
1942
In Order
1232 LEVEL-
3 TAG-0
0 LEVEL- 2 TAG-1
1942 LEVEL-
3 TAG-0
0 LEVEL- 1 TAG-1
0 LEVEL- 2 TAG-1
4451 LEVEL-
5 TAG-0
0 LEVEL- 4 TAG-1
1243 LEVEL-
5 TAG-0
0 LEVEL- 3 TAG-1
1015 LEVEL-
4 TAG-0
press 1 to continue:
1
TRIES 1. Insert
1
Enter the element:
1941
In Order
1232 LEVEL-
3 TAG-0
0 LEVEL- 2 TAG-1
1942 LEVEL-
3 TAG-0
0 LEVEL- 1 TAG-1
1941 LEVEL-
3 TAG-0
0 LEVEL- 2 TAG-1
4451 LEVEL-
5 TAG-0
0 LEVEL- 4 TAG-1
1243 LEVEL-
5 TAG-0
0 LEVEL- 3 TAG-1
1015 LEVEL-
4 TAG-0
press 1 to continue:
1
TRIES 1. Insert
1
Enter the element:
1055
In Order
1232 LEVEL-
3 TAG-0
0 LEVEL- 2 TAG-1
1942 LEVEL-
3 TAG-0
0 LEVEL- 1 TAG-1
1941 LEVEL-
3 TAG-0
0 LEVEL- 2 TAG-1
4451 LEVEL-
5 TAG-0
0 LEVEL- 4 TAG-1
1243 LEVEL-
5 TAG-0
0 LEVEL- 3 TAG-1
1015 LEVEL-
5 TAG-0
0 LEVEL- 4 TAG-1
1055 LEVEL-
5 TAG-0
press 1 to continue:
1
TRIES 1. Insert
1
Enter the element:
1243
Element already exists
In Order
1232 LEVEL-
3 TAG-0
0 LEVEL- 2
TAG-1
1942 LEVEL-
3 TAG-0
0 LEVEL- 1 TAG-1
1941 LEVEL-
3 TAG-0
0 LEVEL- 2 TAG-1
4451 LEVEL-
5 TAG-0
0 LEVEL- 4 TAG-1
1243 LEVEL-
5 TAG-0
0 LEVEL- 3 TAG-1
1015 LEVEL-
5 TAG-0
0 LEVEL- 4 TAG-1
1055 LEVEL-
5 TAG-0
press 1 to continue:
12
RESULT
Thus the program for tries using Java has been implemented
No comments:
Post a Comment