TRIE data structure Part 1: The TRIE ADT in Java

• 1
• 2
• 3
• 4
• 5
• 6
• 7

TRIE is an interesting data-structure used mainly for manipulating with Words in a language. This word is got from the word retrieve. TRIE (pronounced as 'try') has a wide variety of applications in

• Spell checking
• Data compression
• Computational biology
• Routing table for IP addresses
• Storing/Querying XML documents etc.,

We shall see how to construct a basic TRIE data structure in Java.

The main abstract methods of the TRIE ADT are,

public void insert(String s);
public boolean search(String s);

In this data-structure, each node holds a character instead of a String. Each node has something called as 'marker' to mark the end of a word. And each node has a Collection of child nodes. This Collection can be either a Set or a List based on the speed vs space criterion.

The basic element - Node of a TRIE data structure looks like this,

char content;
boolean marker;
Collection<Node> child;

A TRIE tree would typically look like the following

The above TRIE is constructed by inserting the words ball, bat, doll, dork, do, dorm, send, sense. The markers are denoted on the Node using a red star(*). We shall look into more about the TRIE data structure in depth in the next post.