Introduction to Trie Data Structure - The Coding Shala
In this post, we will learn what is Trie Data Structure and how to implement Trie in Java.
Introduction to Trie Data Structure
Trie is a special form of an N-ary tree, also called prefix tree. Tries are an extremely special and useful data-structure are based on the prefix of a string. They are used to represent the Retrieval of data and thus the name Trie.
A Trie is a special data structure used to store strings that can be visualized like a graph. It consists of nodes and edges. Each node consists of at max 26 children and edges connect each parent to its children. These 26 pointers are nothing but pointers for each of the 26 letters of the English alphabet.
Note: Root node is null in Trie.
Strings are stored in a top to bottom manner on the basis of their prefix in a trie. All prefixes of length 1 are stored until level 1, all prefixes of length 2 are sorted until level 2, and so on.
In the above example, if we start from the root node and choose the second path 'b' then choose the first child 'a' and choose child 'd' then we finally make the string "bad".
One important property of Trie is that all the descendants of a node have a common prefix of the string associated with that node. That's why Trie is also called prefix tree.
Now the question comes to mind how do we represent Trie?
We can use the array to store children nodes. We can declare an array whose size is 26 in each node to store its children nodes. The following code explains it:
The second method is to use a hashMap to store children nodes. We can declare a hashMap in each node. The key of the hashMap are children and the value is the corresponding child node.
The following code explains it:
Insertion in Trie
Search in Trie
Basic Implementation of Trie Data Structure
Java Program to Implement Trie using Array
Java Program to Implement Trie using HashMap
- Introduction to Binary Tree
- Introduction to Binary Search Tree
- Introduction to N-ary Tree
- Search in a Binary Search Tree
- Delete Node in a Binary Search Tree