Definition and Algorithms of Trie

Trie Algorithm

Definition of Trie

  • Prefix Tree, also called Dictionary Tree or Key Tree, is a tree-based data structure, a variant of the hash tree.
  • Usage: Efficiently store and sort a large number of strings, often used in search engines for word frequency counting.
  • Advantages: Reduces unnecessary string comparisons by leveraging common prefixes.
  • Core Idea: Trade space for time, using shared prefixes to speed up lookups.

Three Basic Properties of a Trie

  1. The root node contains no character; each other node contains exactly one character.
  2. The path from the root to a node forms the string represented by that node.
  3. All child nodes of a node have distinct characters.

Comparison with Hash Lookup

  • Hash tree explanation: Merkle tree
  • Trie complexity: O(L)O(L), where LL is the string length.
  • Hash lookup complexity: O(1)O(1)
  • Hash tables do not support dynamic queries (queries can only be made after full input is provided).
  • Trie supports dynamic queries, but may consume more memory.

Trie Data Structure

Java Implementation

  • Trie Node Initialization
public class TrieNode {
    int count;
    int prefix;
    TrieNode[] nextNode = new TrieNode[26];

    public TrieNode() {
        count = 0;
        prefix = 0;
    }
}
  • Insert a Word
public static void insert(TrieNode root, String str) {
    if (root == null || str.length() == 0) return;

    char[] c = str.toCharArray();
    for (int i = 0; i < str.length(); i++) {
        if (root.nextNode[c[i] - 'a'] == null) {
            root.nextNode[c[i] - 'a'] = new TrieNode();
        }
        root = root.nextNode[c[i] - 'a'];
        root.prefix++;
    }
    root.count++;
}
  • Search Word Count / Prefix Count
public static int search(TrieNode root, String str) {
    if (root == null || str.length() == 0) return -1;

    char[] c = str.toCharArray();
    for (int i = 0; i < str.length(); i++) {
        if (root.nextNode[c[i] - 'a'] == null) return -1;
        root = root.nextNode[c[i] - 'a'];
    }
    return root.count == 0 ? -1 : root.count;
}

public static int searchPrefix(TrieNode root, String str) {
    if (root == null || str.length() == 0) return -1;

    char[] c = str.toCharArray();
    for (int i = 0; i < str.length(); i++) {
        if (root.nextNode[c[i] - 'a'] == null) return -1;
        root = root.nextNode[c[i] - 'a'];
    }
    return root.prefix;
}

C++ Implementation

class Trie {
public:
    int count;       // Number of words ending at this node
    int prefix;      // Number of words with this prefix
    Trie* nextNode[26];

    Trie() {
        count = 0;
        prefix = 0;
        for(int i = 0; i < 26; i++) nextNode[i] = nullptr;
    }

    void insert(string word) {
        if(word.empty()) return;
        Trie* p = this;
        for(char c : word) {
            if(p->nextNode[c - 'a'] == nullptr)
                p->nextNode[c - 'a'] = new Trie();
            p = p->nextNode[c - 'a'];
            p->prefix++;
        }
        p->count++;
    }

    bool search(string word) {
        if(word.empty()) return false;
        Trie* p = this;
        for(char c : word) {
            if(p->nextNode[c - 'a'] == nullptr) return false;
            p = p->nextNode[c - 'a'];
        }
        return p->count != 0;
    }

    bool startsWith(string prefix) {
        if(prefix.empty()) return false;
        Trie* p = this;
        for(char c : prefix) {
            if(p->nextNode[c - 'a'] == nullptr) return false;
            p = p->nextNode[c - 'a'];
        }
        return p->prefix != 0;
    }
};

/**
 * Usage:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool exists = obj->search(word);
 * bool hasPrefix = obj->startsWith(prefix);
 */

Reference: Trie Tree

pythonData-structure