Einführung

Ein Trie, auch Präfixbaum genannt, ist eine spezielle baumbasierte Datenstruktur, die zum effizienten Abrufen von Informationen verwendet wird.

Es ist besonders nützlich für Anwendungsfälle, die die Suche und den Präfixabgleich innerhalb von Zeichenfolgen beinhalten.

1. Wenn ich Ihnen vom Trie-Algorithmus erzähle, könnten Sie an diesem Algorithmus interessiert sein oder auch nicht

2. Aber wenn ich Ihnen sagen würde, dass Sie damit einen Autovervollständigungsalgorithmus erstellen können. Sie werden mehr Freude daran haben, dies zu lernen.

Anwendungsfall dieses Algorithmus

1. Automatische Vervollständigung:

A. In Suchmaschinen oder Texteditoren werden häufig Versuche verwendet, um die Autovervollständigungsfunktion zu implementieren.
B. Wenn Sie mit der Eingabe beginnen, schlägt die Anwendung basierend auf dem von Ihnen eingegebenen Präfix mögliche Vervollständigungen vor.

2. Rechtschreibprüfung:

A. Versuche können zur Implementierung von Rechtschreibprüfungen verwendet werden. Wenn ein Wort im Versuch nicht vorkommt, ist es wahrscheinlich falsch geschrieben.
B. Der Versuch kann auch Korrekturen vorschlagen, indem er ähnliche Wörter findet.

3. IP-Routing:

A. Versuche werden in Routern verwendet, um Routing-Tabellen zu speichern.
B. Der Router verwendet einen Versuch, um das längste Präfix zu finden, das den nächsten Hop für ein Paket bestimmt.

4. Effizientes Speichern und Suchen nach Zeichenfolgen:

A. Wenn Sie einen Datensatz mit Zeichenfolgen haben, in dem es viele gemeinsame Präfixe gibt, kann ein Trie diese Zeichenfolgen platzsparender speichern als sie einzeln zu speichern.
B. Der Suchvorgang ist ebenfalls effizient, da die zeitliche Komplexität proportional zur Länge der gesuchten Zeichenfolge ist.

class Node {
    constructor() {
        this.end = false;
        this.children = {}
    }
}

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

    insert(word) {
        let head = this.root;

        for (let i = 0; i ', current.children);

        console.log('Possible Auto Complete Values are --->');
        for (let key in current.children) {
            console.log('---> ', word key);
        }
    }
}

const test = new Trie();
test.insert('ant');
test.insert('any');
console.log(test.search('ant'));
console.log(test.search('any'));
console.log(test.search('anj'));
test.autoComplete('an')
/*
true
true
false
children =--->  {
  t: Node { end: true, children: {} },
  y: Node { end: true, children: {} }
}
Possible Auto Complete Values are --->
--->  ant
--->  any
*/

Wenn Sie Bedenken/Fragen haben, können Sie sich gerne an mich wenden.