Java Program to Implement Patricia Trie

This is a Java Program to Implement Patricia Trie. A radix tree (also patricia trie or radix trie or compact prefix tree) is a space-optimized trie data structure where each node with only one child is merged with its child.

Here is the source code of the Java Program to Implement Patricia Trie. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/**
 ** Java Program to Implement Patricia Trie
 **/
 
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 PatriciaTrieTest
{
    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 emepty");
            System.out.println("4. make emepty");
 
            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');               
    }
}
Patricia Trie Test
 
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
3
Empty Status : true
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
1
Enter key element to insert
24
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
1
Enter key element to insert
6
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
1
Enter key element to insert
28
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
1
Enter key element to insert
5
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
1
Enter key element to insert
63
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
1
Enter key element to insert
19
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
1
Enter key element to insert
94
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
1
Enter key element to insert
24
Error : key is already present
 
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
2
Enter key element to search
24
Search result : true
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
2
Enter key element to search
5
Search result : true
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
2
Enter key element to search
6
Search result : true
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
2
Enter key element to search
7
Search result : false
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
2
Enter key element to search
19
Search result : true
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
2
Enter key element to search
15
Search result : false
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
2
Enter key element to search
94
Search result : true
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
2
Enter key element to search
97
Search result : false
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
2
Enter key element to search
32
Search result : false
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
2
Enter key element to search
28
Search result : true
 
Do you want to continue (Type y or n)
 
y
 
Patricia Trie Operations
 
1. insert
2. search
3. check emepty
4. make emepty
4
Patricia Trie cleared
 
Do you want to continue (Type y or n)
 
n

Related posts:

Java Program to Implement Sorted Vector
Injecting Prototype Beans into a Singleton Instance in Spring
ArrayList trong java
Java Program to Implement ArrayBlockingQueue API
A Guide to System.exit()
Guide to java.util.concurrent.Future
Java Program to Implement Dijkstra’s Algorithm using Set
Java Program to Check Whether a Directed Graph Contains a Eulerian Cycle
Adding Shutdown Hooks for JVM Applications
Java Program to Use the Bellman-Ford Algorithm to Find the Shortest Path
Một số nguyên tắc, định luật trong lập trình
Set Interface trong Java
Recommended Package Structure of a Spring Boot Project
Batch Processing with Spring Cloud Data Flow
Java Program to Perform integer Partition for a Specific Case
Java Program to Implement Hash Tables Chaining with Binary Trees
Java Program to Implement Max-Flow Min-Cut Theorem
Java Program to Implement Suffix Array
Cài đặt và sử dụng Swagger UI
Java Program to Find the Longest Subsequence Common to All Sequences in a Set of Sequences
Java Program to Implement Hash Trie
Java Program to Create a Balanced Binary Tree of the Incoming Data
Java Program to Implement Binomial Heap
Map Serialization and Deserialization with Jackson
Java Program to Implement Skip List
Error Handling for REST with Spring
Java Program to Implement HashTable API
Constructor Injection in Spring with Lombok
Validations for Enum Types
Từ khóa static và final trong java
Custom HTTP Header with the HttpClient
Java Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm