Introduction to Trie (Prefix Tree)

A Trie is a tree-like data structure that is used for efficiently storing and searching strings, especially in applications like autocomplete, spell checking, and IP routing.

---

Key Properties of a Trie:

1. Nodes: Each node represents a character.
2. Root: The root node is empty and serves as the starting point.
3. Children: Each node has up to 26 children (for lowercase English letters) or more, depending on the character set.
4. End-of-Word Marker: Some nodes are marked to indicate the end of a word.

---

Basic Trie Operations:

1. Insertion

Inserting a word involves traversing the trie and creating new nodes for characters that don’t exist.

2. Search

Search checks whether a word exists in the trie by traversing its nodes.

3. Prefix Search

This checks whether any word in the trie starts with a given prefix.

---

Implementation of Basic Trie in JavaScript:

class TrieNode {
    constructor() {
        this.children = {}; // Stores child nodes
        this.isEndOfWord = false; // Marks the end of a word
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // Insert a word
    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true; // Mark the end of the word
    }

    // Search for a word
    search(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

    // Check if any word starts with the given prefix
    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return true;
    }
}

// Example usage
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));   // true
console.log(trie.search("app"));     // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app"));     // true

---

Advanced Trie Operations:

1. Delete a Word:

Deleting a word involves a recursive approach, where we remove nodes that are no longer needed.

delete(word, node = this.root, depth = 0) {
    if (depth === word.length) {
        if (!node.isEndOfWord) return false; // Word doesn't exist
        node.isEndOfWord = false;
        return Object.keys(node.children).length === 0; // Check if node has children
    }

    const char = word[depth];
    if (!node.children[char]) return false;

    const shouldDeleteChild = this.delete(word, node.children[char], depth + 1);

    if (shouldDeleteChild) {
        delete node.children[char];
        return Object.keys(node.children).length === 0 && !node.isEndOfWord;
    }

    return false;
}

2. Count Words with a Prefix:

Count how many words start with a given prefix.

countWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return 0;
        node = node.children[char];
    }
    return this._countWords(node);
}

_countWords(node) {
    let count = node.isEndOfWord ? 1 : 0;
    for (let char in node.children) {
        count += this._countWords(node.children[char]);
    }
    return count;
}

3. Autocomplete Suggestions:

Given a prefix, return all words that start with it.

getWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return [];
        node = node.children[char];
    }
    return this._collectWords(node, prefix);
}

_collectWords(node, prefix) {
    let results = [];
    if (node.isEndOfWord) results.push(prefix);

    for (let char in node.children) {
        results = results.concat(this._collectWords(node.children[char], prefix + char));
    }

    return results;
}

---

Time Complexity:

1. Insert: O(L) (L = length of the word)
2. Search: O(L)
3. Prefix Search: O(L)
4. Delete: O(L)

---

Applications of Trie:

1. Autocomplete Systems (e.g., search bars, text editors).
2. Spell Checkers.
3. IP Routing (longest prefix matching).
4. Word Games (e.g., Boggle).
5. DNA Sequence Matching.

The above is the detailed content of Introduction to Trie (Prefix Tree). For more information, please follow other related articles on the PHP Chinese website!