Trie Trees in Java

A Trie tree is a type of data structure used to store and retrieve data in an efficient manner. It is an advanced form of a tree data structure, which organizes data into a hierarchy of parent-child relationships. The Trie tree is particularly useful for storing and retrieving strings of characters. In this article, we will discuss how a Trie tree works, its time and space complexity for various operations, and how to use it in Java.

What is a Trie Tree?

A Trie tree is a specialized tree used to store strings of characters. It is composed of nodes, which represent a single character in the string. Each node is linked to its parent and child nodes, forming a hierarchy. The root node is the start of the tree and has no parent node. Each subsequent node is linked to its parent and children nodes, forming a tree-like structure.

The trie tree is an efficient data structure for storing and retrieving strings. It is optimized for searching for strings of characters, and can be used for a variety of tasks such as:

• Spell checking
• Autocompletion
• Pattern matching
• Text search
• Dictionary operations

Time Complexity

The time complexity of a Trie tree is dependent on the number of characters in the string being stored.

Searching

Searching a Trie tree has an average time complexity of O(m), where m is the number of characters in the input string. In the worst case, the time complexity is O(n), where n is the number of nodes in the tree.

Insertion

Inserting a string into a Trie tree has an average time complexity of O(m), where m is the number of characters in the string. In the worst case, the time complexity is O(n), where n is the number of nodes in the tree.

Deletion

Deleting a string from a Trie tree has an average time complexity of O(m), where m is the number of characters in the string. In the worst case, the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity

The space complexity of a Trie tree is dependent on the number of strings being stored. The worst case space complexity is O(n*m), where n is the number of nodes and m is the number of characters in the longest string.

Using Trie Trees in Java

Now that we have discussed the time and space complexity of a Trie tree, let us look at how to implement one in Java.

Creating a Trie Tree

The following class creates a TrieNode, which will be the basis of the Trie tree. The TrieNode class stores the characters stored in the Trie tree, as well as a boolean indicating whether the node is the end of a string.

public class TrieNode {
    char data;
    boolean isEndOfString;
    TrieNode[] children;

    public TrieNode(char data) {
        this.data = data;
        this.isEndOfString = false;
        this.children = new TrieNode[26];
    }
}

The following class creates the Trie tree. The Trie class stores the root node of the Trie tree, and provides methods for searching, insertion, and deletion.

public class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode(' ');
    }

    //Search a string in the trie
    public boolean search(String str) {
        //Start from the root node
        TrieNode currentNode = root;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int index = c - 'a';
            //Check if the character exists in the node
            if (currentNode.children[index] == null) {
                return false;
            }
            currentNode = currentNode.children[index];
        }
        //Check if the last node is the end of a string
        return currentNode.isEndOfString;
    }

    //Insert a string in the trie
    public void insert(String str) {
        //Start from the root node
        TrieNode currentNode = root;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int index = c - 'a';
            //Check if the character exists in the node
            if (currentNode.children[index] == null) {
                currentNode.children[index] = new TrieNode(c);
            }
            currentNode = currentNode.children[index];
        }
        //Mark the last node as the end of a string
        currentNode.isEndOfString = true;
    }

    //Delete a string from the trie
    public void delete(String str) {
        //Start from the root node
        TrieNode currentNode = root;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int index = c - 'a';
            //Check if the character exists in the node
            if (currentNode.children[index] == null) {
                return;
            }
            currentNode = currentNode.children[index];
        }
        //Mark the last node as not the end of a string
        currentNode.isEndOfString = false;
    }
}

Conclusion

In this article, we discussed how a Trie tree works, its time and space complexity for various operations, and how to use it in Java. The Trie tree is an optimized tree data structure for searching for strings of characters, and can be used for a variety of tasks such as spell checking, autocompletion, pattern matching, text search, and dictionary operations. The time complexity for searching, insertion, and deletion is O(m), where m is the number of characters in the input string. The space complexity is O(n*m), where n is the number of nodes and m is the number of characters in the longest string.

Exercises

public class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode(' ');
    }

    //Search a string in the trie
    public boolean search(String str) {
        //Start from the root node
        TrieNode currentNode = root;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int index = c - 'a';
            //Check if the character exists in the node
            if (currentNode.children[index] == null) {
                return false;
            }
            currentNode = currentNode.children[index];
        }
        //Check if the last node is the end of a string
        return currentNode.isEndOfString;
    }

    //Insert a string in the trie
    public void insert(String str) {
        //Start from the root node
        TrieNode currentNode = root;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int index = c - 'a';
            //Check if the character exists in the node
            if (currentNode.children[index] == null) {
                currentNode.children[index] = new TrieNode(c);
            }
            currentNode = currentNode.children[index];
        }
        //Mark the last node as the end of a string
        currentNode.isEndOfString = true;
    }

    //Delete a string from the trie
    public void delete(String str) {
        //Start from the root node
        TrieNode currentNode = root;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int index = c - 'a';
            //Check if the character exists in the node
            if (currentNode.children[index] == null) {
                return;
            }
            currentNode = currentNode.children[index];
        }
        //Mark the last node as not the end of a string
        currentNode.isEndOfString = false;
    }
}

public boolean search(String str) {
    //Start from the root node
    TrieNode currentNode = root;
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        int index = c - 'a';
        //Check if the character exists in the node
        if (currentNode.children[index] == null) {
            return false;
        }
        currentNode = currentNode.children[index];
    }
    //Check if the last node is the end of a string
    return currentNode.isEndOfString;
}

public void insert(String str) {
    //Start from the root node
    TrieNode currentNode = root;
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        int index = c - 'a';
        //Check if the character exists in the node
        if (currentNode.children[index] == null) {
            currentNode.children[index] = new TrieNode(c);
        }
        currentNode = currentNode.children[index];
    }
    //Mark the last node as the end of a string
    currentNode.isEndOfString = true;
}

public void delete(String str) {
    //Start from the root node
    TrieNode currentNode = root;
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        int index = c - 'a';
        //Check if the character exists in the node
        if (currentNode.children[index] == null) {
            return;
        }
        currentNode = currentNode.children[index];
    }
    //Mark the last node as not the end of a string
    currentNode.isEndOfString = false;
}

public void traverseTrie(TrieNode node) {
    for (int i = 0; i < 26; i++) {
        if (node.children[i] != null) {
            System.out.print(node.children[i].data);
            traverseTrie(node.children[i]);
        }
    }
}