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 Find MST (Minimum Spanning Tree) using Prim’s Algorithm
Guava CharMatcher
Jackson Annotation Examples
Java Optional as Return Type
Hướng dẫn Java Design Pattern – Adapter
Java Program to Find Shortest Path Between All Vertices Using Floyd-Warshall’s Algorithm
HttpClient 4 – Follow Redirects for POST
Remove All Occurrences of a Specific Value from a List
@Before vs @BeforeClass vs @BeforeEach vs @BeforeAll
OAuth2 Remember Me with Refresh Token
File Upload with Spring MVC
Entity To DTO Conversion for a Spring REST API
Java Program to Perform Searching in a 2-Dimension K-D Tree
Daemon Threads in Java
Performance Difference Between save() and saveAll() in Spring Data
Java Program to Implement Fibonacci Heap
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
Java – InputStream to Reader
Tìm hiểu cơ chế Lazy Evaluation của Stream trong Java 8
Queue và PriorityQueue trong Java
Java Program to Find Inverse of a Matrix
Guide to System.gc()
Java Program to Construct an Expression Tree for an Infix Expression
Tạo chương trình Java đầu tiên sử dụng Eclipse
Spring WebClient and OAuth2 Support
Introduction to PCollections
Send email with SMTPS (eg. Google GMail)
Jackson – Marshall String to JsonNode
The XOR Operator in Java
Spring Cloud AWS – S3
Java Program to Implement Quick Hull Algorithm to Find Convex Hull
Filtering a Stream of Optionals in Java