Präfixbaum-Golang-Implementierung

Präfixbaum (Trie) ist eine Datenstruktur, die hauptsächlich zum Speichern und Abgleichen von Zeichenfolgen verwendet wird. In diesem Artikel stellen wir vor, wie man mit Golang einen Präfixbaum implementiert.

1. Was ist ein Präfixbaum?

Präfixbaum, auch Wörterbuchbaum genannt, ist eine baumförmige Datenstruktur zum Speichern von Zeichenfolgensammlungen, die hauptsächlich zum effizienten Auffinden einer bestimmten Zeichenfolge in einer großen Textmenge verwendet wird. Im Vergleich zu anderen Datenstrukturen wie Hash-Tabellen beträgt die zeitliche Komplexität eines Präfixbaums O(k), wobei k die Länge der zu findenden Zeichenfolge darstellt.

Das Kernkonzept des Präfixbaums ist „Knoten“. Jeder Knoten enthält die folgenden Informationen:

• ein Zeichen c;
• ein boolescher Wert istBlatt, der angibt, ob die Zeichenfolge, die mit diesem Knoten endet, vorhanden ist; Tabellenkinder werden zum Speichern untergeordneter Knoten verwendet, und der Schlüssel ist das Zeichen, das dem untergeordneten Knoten entspricht.
• Die folgende Abbildung ist ein Beispiel für einen Präfixbaum mit vier Zeichenfolgen (Apfel, Anwenden, App, Banane):

Grundoperationen des Präfixbaums

2. Zu den Grundoperationen des Präfixbaums gehört das Einfügen und suchen Und löschen:

2.1 Einfügen

Beim Einfügen einer Zeichenfolge in den Präfixbaum müssen wir mit dem Durchlaufen vom Wurzelknoten aus beginnen.

Die spezifischen Schritte sind wie folgt:

Initialisieren Sie den aktuellen Knoten als Wurzelknoten.

• Durchlaufen Sie jedes Zeichen in der Zeichenfolge. Erstellen Sie einen neuen Knoten Speichern Sie es im untergeordneten Knoten.
• Wenn sich das aktuelle Zeichen im untergeordneten Knoten des aktuellen Knotens befindet, verschieben Sie es zu diesem Knoten.
• Nachdem Sie die Zeichenfolge durchlaufen haben, markieren Sie das isLeaf des aktuellen Knotens als wahr.
• Das Folgende ist ein Beispiel für das Einfügen der Zeichenfolge „apple“ und den Ausführungsprozess:

2.2 Suchen

Bei der Suche nach einer Zeichenfolge müssen wir mit der Traversierung vom Wurzelknoten aus beginnen.

Die spezifischen Schritte sind wie folgt:

Initialisieren Sie den aktuellen Knoten als Wurzelknoten.

• Durchlaufen Sie jedes Zeichen in der Zeichenfolge. Dies bedeutet, dass die Zeichenfolge nicht im untergeordneten Knoten enthalten ist existiert nicht im Präfixbaum;
• Wenn sich das aktuelle Zeichen im untergeordneten Knoten des aktuellen Knotens befindet, wechseln Sie zu diesem Knoten.
• Wenn nach dem Durchlaufen der Zeichenfolge die isLeaf-Markierung des aktuellen Knotens wahr ist, bedeutet dies, dass dies der Fall ist Die Zeichenfolge ist im Präfixbaum vorhanden. Andernfalls bedeutet dies, dass das Präfix im Präfixbaum vorhanden ist, die Zeichenfolge jedoch nicht im Präfixbaum.
• Das Folgende ist ein Beispiel für die Suche nach der Zeichenfolge „appl“ und ihren Ausführungsprozess:

2.3 Löschen

Wenn wir eine Zeichenfolge löschen, müssen wir mit der Traversierung vom Wurzelknoten aus beginnen.

Die spezifischen Schritte sind wie folgt:

Initialisieren Sie den aktuellen Knoten als Wurzelknoten.

• Durchlaufen Sie jedes Zeichen in der Zeichenfolge. Dies bedeutet, dass sich die Zeichenfolge nicht im untergeordneten Knoten befindet existiert nicht im Präfixbaum;
• Wenn sich das aktuelle Zeichen im untergeordneten Knoten des aktuellen Knotens befindet und das letzte Zeichen der Zeichenfolge durchlaufen wurde, markieren Sie das isLeaf des Knotens als falsch;
• Wenn das aktuelle Zeichen befindet sich im untergeordneten Knoten des aktuellen Knotens und wurde noch nicht bis zum letzten Zeichen der Zeichenfolge durchlaufen und dann zum Knoten verschoben.
• Wenn nach dem Löschen des Knotens die untergeordneten Knoten des aktuellen Knotens leer sind und isLeaf vorhanden ist false, löschen Sie weiterhin den übergeordneten Knoten des Knotens.
• Das Folgende ist ein Beispiel für das Löschen der Zeichenfolge „apple“ und seinen Ausführungsprozess:

Golang implementiert den Präfixbaum

3. Gemäß der vorherigen Beschreibung können wir Golang verwenden, um den Präfixbaum zu implementieren.

Der Code lautet wie folgt:

type Trie struct {
    children map[byte]*Trie
    isLeaf   bool
}

func NewTrie() *Trie {
    return &Trie{children: make(map[byte]*Trie)}
}

func (t *Trie) Insert(word string) {
    curr := t
    for i := 0; i < len(word); i++ {
        c := word[i]
        if _, ok := curr.children[c]; !ok {
            curr.children[c] = NewTrie()
        }
        curr = curr.children[c]
    }
    curr.isLeaf = true
}

func (t *Trie) Search(word string) bool {
    curr := t
    for i := 0; i < len(word); i++ {
        c := word[i]
        if _, ok := curr.children[c]; !ok {
            return false
        }
        curr = curr.children[c]
    }
    return curr.isLeaf
}

func (t *Trie) Delete(word string) {
    nodes := make([]*Trie, 0)
    curr := t
    for i := 0; i < len(word); i++ {
        c := word[i]
        if _, ok := curr.children[c]; !ok {
            return
        }
        nodes = append(nodes, curr)
        curr = curr.children[c]
    }
    curr.isLeaf = false
    if len(curr.children) > 0 {
        return
    }

    for i := len(nodes) - 1; i >= 0; i-- {
        node := nodes[i]
        delete(node.children, word[i])
        if len(node.children) > 0 || node.isLeaf {
            return
        }
    }
}

Im Code wird die Funktion NewTrie() verwendet, um einen neuen Präfixbaumknoten zu erstellen; die Funktion Insert() wird verwendet, um eine Zeichenfolge in den Präfixbaum einzufügen; Die Funktion wird verwendet, um eine Zeichenfolge zu finden. Unabhängig davon, ob sie im Präfixbaum vorhanden ist. Die Funktion „Delete()“ wird zum Löschen einer Zeichenfolge verwendet.

Zusammenfassung

4. Der Präfixbaum ist eine effiziente Datenstruktur zum Speichern und Durchsuchen von Zeichenfolgen. In diesem Artikel werden die Grundkonzepte von Präfixbäumen und ihre Grundoperationen vorgestellt und die Einfügungs-, Such- und Löschfunktionen von Präfixbäumen über Golang implementiert. Ich hoffe, dass die Leser nach dem Studium dieses Artikels ihr Verständnis von Präfixbäumen vertiefen und Golang verwenden können, um andere effiziente Datenstrukturen zu implementieren.

Das obige ist der detaillierte Inhalt vonPräfixbaum-Golang-Implementierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!