Implementing Patricia Trie in Java
A Patricia trie (a radix trie or compact prefix tree) is a compressed trie data structure that stores strings for efficient retrieval and search operations. It is a type of trie that stores strings in a compressed form, which makes it more efficient than other types of tries.
Algorithm to implement Patricia Trie
Step 1: Define a class PatriciaNode to represent nodes in the Patricia Trie. Include fields for the bit number, data, left and right child.
Step 2: Define a class PatriciaTrie to represent Patricia Trie. Include a root node as a member variable and a constant MaxBits to limit the number of bits in the keys.
Step 3: Implement a method isEmpty to check if the trie is empty.
Step 4: Implement a method makeEmpty to clear the trie.
Step 5: Implement a method bit to get the value of the ith bit in a binary representation of a number.
Step 6: Implement a method search to search for an element in the trie. Use bitwise operations to determine the number of bits required to represent the element. Call the private search method to find the node containing the element.
Step 7: Implement a private method search to perform the search operation recursively. Traverse the trie to find the node where the element should be located.
Step 8: Implement a method insert to insert an element into the trie. Use bitwise operations to determine the number of bits required to represent the element. Call the private insert method to insert the element.
Step 9: Implement a private method insert to perform the insertion operation recursively. Traverse the trie to find the appropriate location to insert the element. Compare bits to find the first differing bit and split the trie accordingly.
Let us understand this from the following Java program.
File name: Patricia.java
import java.util.Scanner;
/** Class PatriciaNode **/
class PatriciaNode
{
int bitNumber;
int data;
PatriciaNode leftChild, rightChild;
}
/* Class PatriciaTrie */
class PatriciaTrie
{
private PatriciaNode root;
private static final int MaxBits = 10;
/** Constructor **/
public PatriciaTrie()
{
root = null;
}
/** function to check if empty **/
public boolean isEmpty()
{
return root == null;
}
/** function to clear **/
public void makeEmpty()
{
root = null;
}
/** function to get ith bit of key k from left **/
private boolean bit(int k, int i)
{
String binary = Integer.toString(k, 2);
while (binary.length() != MaxBits)
binary = "0" + binary;
if (binary.charAt(i - 1) == '1')
return true ;
return false;
}
/** function to search for an element **/
public boolean search(int k)
{
int numOfBits = (int) (Math.log(k)/Math.log(2)) + 1;
if (numOfBits > MaxBits)
{
System.out.println("Error : Number too large");
return false;
}
PatriciaNode searchNode = search(root, k);
if (searchNode.data == k)
return true;
else
return false;
}
/** function to search for an element **/
private PatriciaNode search(PatriciaNode t, int k)
{
PatriciaNode currentNode, nextNode;
if (t == null)
{
return null;
}
nextNode = t.leftChild;
currentNode = t;
while (nextNode.bitNumber > currentNode.bitNumber)
{
currentNode = nextNode;
nextNode = (bit(k, nextNode.bitNumber)) ? nextNode.rightChild : nextNode.leftChild;
}
return nextNode;
}
/** function to insert and element **/
public void insert(int ele)
{
int numOfBits = (int) (Math.log(ele)/Math.log(2)) + 1;
if (numOfBits > MaxBits)
{
System.out.println("Error : Number too large");
return;
}
root = insert(root, ele);
}
/** function to insert and element **/
private PatriciaNode insert(PatriciaNode t, int ele)
{
PatriciaNode current, parent, lastNode, newNode;
int i;
if (t == null)
{
t = new PatriciaNode();
t.bitNumber = 0;
t.data = ele;
t.leftChild = t;
t.rightChild = null;
return t;
}
lastNode = search(t, ele);
if (ele == lastNode.data)
{
System.out.println("Error : key is already present\n");
return t;
}
for (i = 1; bit(ele, i) == bit(lastNode.data, i); i++);
current = t.leftChild; parent = t;
while (current.bitNumber > parent.bitNumber && current.bitNumber < i)
{
parent = current;
current = (bit(ele, current.bitNumber)) ? current.rightChild : current.leftChild;
}
newNode = new PatriciaNode();
newNode.bitNumber = i;
newNode.data = ele;
newNode.leftChild = bit(ele, i) ? current : newNode;
newNode.rightChild = bit(ele, i) ? newNode : current;
if (current == parent.leftChild)
parent.leftChild = newNode;
else
parent.rightChild = newNode;
return t;
}
}
/* Class PatriciaTrie Test */
public class Patricia
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of PatriciaTrie */
PatriciaTrie pt = new PatriciaTrie();
System.out.println("Patricia Trie Test\n");
char ch;
/* Perform trie operations */
do
{
System.out.println("\nPatricia Trie Operations\n");
System.out.println("1. insert ");
System.out.println("2. search");
System.out.println("3. check empty");
System.out.println("4. make empty");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter key element to insert");
pt.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter key element to search");
System.out.println("Search result : "+ pt.search( scan.nextInt() ));
break;
case 3 :
System.out.println("Empty Status : "+ pt.isEmpty() );
break;
case 4 :
System.out.println("Patricia Trie cleared");
pt.makeEmpty();
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Output:
Patricia Trie Test
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
3
Empty Status : true
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
1
Enter key element to insert
25
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
1
Enter key element to insert
10
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
1
Enter key element to insert
30
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
1
Enter key element to insert
7
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
1
Enter key element to insert
70
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
1
Enter key element to insert
91
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
1
Enter key element to insert
49
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
1
Enter key element to insert
49
Error : key is already present
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
2
Enter key element to search
7
Search result : true
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
2
Enter key element to search
30
Search result : true
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
2
Enter key element to search
99
Search result : false
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
2
Enter key element to search
44
Search result : false
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
3
Empty Status : false
Do you want to continue (Type y or n)
y
Patricia Trie Operations
1. insert
2. search
3. check empty
4. make empty
4
Patricia Trie cleared
Do you want to continue (Type y or n)
n