Implémentation de l'arbre de préfixes Golang

L'arbre de préfixes (Trie) est une structure de données principalement utilisée pour le stockage et la mise en correspondance de chaînes. Dans cet article, nous présenterons comment implémenter une arborescence de préfixes à l'aide de Golang.

1. Qu'est-ce qu'un arbre de préfixes ?

L'arbre de préfixes, également appelé arbre de dictionnaire, est une structure de données en forme d'arbre utilisée pour stocker des collections de chaînes, principalement utilisée pour trouver efficacement une certaine chaîne dans une grande quantité de texte. Par rapport à d'autres structures de données telles que les tables de hachage, la complexité temporelle d'un arbre de préfixes est O(k), où k représente la longueur de la chaîne à trouver.

Le concept de base de l'arborescence des préfixes est "nœud", chaque nœud contient les informations suivantes :

• un caractère c
#🎜 🎜 #Une valeur booléenne isLeaf, indiquant si la chaîne se terminant par ce nœud existe ;
• Une table de hachage enfants, utilisée pour stocker les nœuds enfants, et la clé est le caractère correspondant au nœud enfant.

La figure suivante est un exemple d'arbre de préfixes contenant quatre chaînes (apple, apply, app, banane) :

#🎜 🎜 #

Opérations de base de l'arborescence des préfixes

2. Les opérations de base de l'arborescence des préfixes incluent l'insertion, la recherche et la suppression :

2.1 Insérer# 🎜🎜#

Lors de l'insertion d'une chaîne dans l'arborescence des préfixes, nous devons commencer la traversée à partir du nœud racine.

Les étapes spécifiques sont les suivantes :

Initialiser le nœud actuel en tant que nœud racine

Traverser chaque caractère de la chaîne ; , si le personnage actuel Si le personnage n'est pas dans le nœud enfant du nœud actuel, créez un nouveau nœud et stockez-le dans le nœud enfant
• Si le personnage actuel est dans le nœud enfant du nœud actuel ; nœud, déplacez-vous vers ce nœud ;
• Après avoir parcouru la chaîne, marquez la isLeaf du nœud actuel comme vraie.
• Ce qui suit est un exemple d'insertion de la chaîne "apple" et son processus d'exécution :

2.2 Find# 🎜🎜#Lorsque nous recherchons une chaîne, nous devons commencer la traversée à partir du nœud racine.

Les étapes spécifiques sont les suivantes :

Initialiser le nœud actuel en tant que nœud racine

Traverser chaque caractère de la chaîne ; , si le caractère actuel Si le caractère n'est pas dans le nœud enfant du nœud actuel, cela signifie que la chaîne n'existe pas dans l'arborescence des préfixes

• Si le caractère actuel est dans le nœud enfant du nœud actuel, déplacez-vous vers ce nœud ;
• Après avoir parcouru la chaîne, si la marque isLeaf du nœud actuel est vraie, cela signifie que la chaîne existe dans l'arborescence des préfixes ; existe dans l'arborescence des préfixes, mais la chaîne n'existe pas dans l'arborescence des préfixes.
• Ce qui suit est un exemple de recherche de la chaîne "appl" et de son processus d'exécution :

2.3 Supprimer# 🎜🎜#

Lors de la suppression d'une chaîne, nous devons parcourir à partir du nœud racine.

Les étapes spécifiques sont les suivantes :

Initialiser le nœud actuel en tant que nœud racine

Traverser chaque caractère de la chaîne ; , si le caractère actuel Si le caractère n'est pas dans le nœud enfant du nœud actuel, cela signifie que la chaîne n'existe pas dans l'arborescence des préfixes

Si le caractère actuel est dans le nœud enfant du nœud actuel et que le dernier caractère de la chaîne a été parcouru, marquez la isLeaf du nœud comme false
• Si le caractère actuel est dans le nœud enfant du nœud actuel et le dernier caractère du nœud actuel la chaîne n'a pas été parcourue, déplacez-vous vers ce nœud ; #🎜 🎜#
• Si les enfants du nœud actuel sont vides et isLeaf est faux après la suppression du nœud, continuez à supprimer le nœud parent du nœud.
• Ce qui suit est un exemple de suppression de la chaîne "apple" et de son processus d'exécution :

# 🎜🎜 #Golang implémente l'arbre de préfixes

Selon la description précédente, nous pouvons utiliser Golang pour implémenter l'arbre de préfixes.

Le code est le suivant :

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

3. Dans le code, la fonction NewTrie() est utilisée pour créer un nouveau nœud d'arborescence de préfixes ; insérer un caractère dans l'arborescence des préfixes ; la fonction Search() est utilisée pour savoir si une chaîne existe dans l'arborescence des préfixes ; la fonction Delete() est utilisée pour supprimer une chaîne.

Summary

L'arborescence des préfixes est une structure de données efficace pour stocker et rechercher des chaînes. Cet article présente les concepts de base des arbres de préfixes et leurs opérations de base, et implémente les fonctions d'insertion, de recherche et de suppression des arbres de préfixes via Golang. J'espère que les lecteurs pourront approfondir leur compréhension des arbres de préfixes en étudiant cet article et être capables d'utiliser Golang pour implémenter d'autres structures de données efficaces.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!