Einführung in Trie (Präfixbaum)

Ein Trie ist eine baumartige Datenstruktur, die zum effizienten Speichern und Durchsuchen von Zeichenfolgen verwendet wird, insbesondere in Anwendungen wie Autovervollständigung, Rechtschreibprüfung und IP-Routing.

---

Schlüsseleigenschaften eines Versuchs:

1. Knoten: Jeder Knoten repräsentiert ein Zeichen.
2. Wurzel: Der Wurzelknoten ist leer und dient als Ausgangspunkt.
3. Untergeordnete Elemente: Jeder Knoten hat bis zu 26 untergeordnete Elemente (für englische Kleinbuchstaben) oder mehr, je nach Zeichensatz.
4. Wortende-Markierung: Einige Knoten sind markiert, um das Ende eines Wortes anzuzeigen.

---

Grundlegende Trie-Operationen:

1. Einfügung

Das Einfügen eines Wortes erfordert das Durchlaufen des Tries und das Erstellen neuer Knoten für nicht vorhandene Zeichen.

2. Suchen

Die Suche prüft, ob ein Wort im Versuch vorhanden ist, indem es seine Knoten durchläuft.

3. Präfixsuche

Dadurch wird überprüft, ob ein Wort im Versuch mit einem bestimmten Präfix beginnt.

---

Implementierung von 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

---

Erweiterte Trie-Operationen:

1. Ein Wort löschen:

Das Löschen eines Wortes erfordert einen rekursiven Ansatz, bei dem wir Knoten entfernen, die nicht mehr benötigt werden.

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. Wörter mit Präfix zählen:

Zählen Sie, wie viele Wörter mit einem bestimmten Präfix beginnen.

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. Vorschläge zur automatischen Vervollständigung:

Gibt bei einem gegebenen Präfix alle Wörter zurück, die damit beginnen.

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;
}

---

Zeitkomplexität:

1. Einfügen: O(L) (L = Länge des Wortes)
2. Suche: O(L)
3. Präfixsuche: O(L)
4. Löschen: O(L)

---

Anwendungen von Trie:

1. Autovervollständigungssysteme (z. B. Suchleisten, Texteditoren).
2. Rechtschreibprüfung.
3. IP-Routing (längste Präfixübereinstimmung).
4. Wortspiele (z. B. Boggle).
5. DNA-Sequenzabgleich.

Das obige ist der detaillierte Inhalt vonEinführung in Trie (Präfixbaum). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!