Introduction à l'arbre de préfixes

L'arbre de préfixes, communément appelé Trie, est une structure de données arborescente spécialisée dans la gestion et la recherche de chaînes de caractères. Contrairement à une table de hachage classique, le Trie exploite les préfixes communs entre les clés pour optimiser l'espace mémoire et la vitesse de recherche. Il est massivement utilisé dans les moteurs de recherche pour l'autocomplétion, les correcteurs orthographiques et les statistiques de fréquence de mots.

Dans cette structure :

• Chaque nœud représente un état ou un point de jonction.
• Chaque arête est étiquetée par un caractère.
• Le chemin allant de la racine à un nœud spécifique compose une chaîne de caractères.
• Un marqueur est souvent ajouté aux nœuds pour indiquer si une chaîne valide se termine à cet endroit.

Algorithme d'insertion

L'insertion consiste à parcourir l'arbre caractère par caractère à partir de la racine. Si le caractère suivant n'existe pas dans les fils du nœud actuel, un nouveau nœud est créé. À la fin du processus, le dernier nœud est marqué pour signaler la fin d'un mot.

const int MAX_CAPACITY = 100000;
int trieNodes[MAX_CAPACITY][26]; // Pour les lettres de 'a' à 'z'
int wordEndCount[MAX_CAPACITY];
int nodePointer = 1;

void insertString(const string& word) {
    int current = 1;
    for (char c : word) {
        int idx = c - 'a';
        if (!trieNodes[current][idx]) {
            trieNodes[current][idx] = ++nodePointer;
        }
        current = trieNodes[current][idx];
    }
    wordEndCount[current]++;
}

Algorithme de recherche

La recherche suit une logique similaire à l'insertion. On descend dans l'arbre selon les caractères de la requête. Si un caractère est absent ou si, après avoir parcouru toute la chaîne, le nœud final n'est pas marqué comme terminal, alors la chaîne n'existe pas dans le Trie.

bool checkExistence(const string& query) {
    int cursor = 1;
    for (char c : query) {
        int idx = c - 'a';
        if (!trieNodes[cursor][idx]) {
            return false;
        }
        cursor = trieNodes[cursor][idx];
    }
    return wordEndCount[cursor] > 0;
}

Application pratique : Recherche du chemin XOR maximum

Le Trie n'est pas limité aux chaînes de caractères. Une application classique en algorithmique est la recherche de la valeur XOR maximale entre deux nombres dans un ensemble. En stockant les représentations binaires des nombres dans un Trie (Binary Trie), on peut gloutonnement chercher le bit opposé à chaque position pour maximiser le résultat.

Problématique

Étant donné un arbre pondéré avec n nœuds, trouver le chemin entre deux nœuds u et v dont le XOR des poids des arêtes est maximal.

Propriété mathématique

Soit d(u) la valeur XOR du chemin allant de la racine au nœud u. La valeur XOR du chemin entre u et v est définie par : d(u) XOR d(v). Cela est dû au fait que le chemin commun entre la racine et l'ancêtre commun le plus proche de u et v s'annule (puisque x XOR x = 0).

int binaryTrie[MAX_CAPACITY * 31][2];
int trieIdx = 1;

void insertBinary(long long val) {
    int current = 1;
    for (int i = 30; i >= 0; --i) {
        int bit = (val >> i) & 1;
        if (!binaryTrie[current][bit]) {
            binaryTrie[current][bit] = ++trieIdx;
        }
        current = binaryTrie[current][bit];
    }
}

long long getBestMatch(long long val) {
    int current = 1;
    long long bestXor = 0;
    for (int i = 30; i >= 0; --i) {
        int bit = (val >> i) & 1;
        // On tente de prendre le chemin inverse pour maximiser le XOR
        int desired = !bit;
        if (binaryTrie[current][desired]) {
            bestXor |= (1LL << i);
            current = binaryTrie[current][desired];
        } else {
            current = binaryTrie[current][bit];
        }
    }
    return bestXor;
}

Cette approche permet de résoudre le problème en une complexité temporelle de O(N log M), où N est le nombre d'éléments et M la valeur maximale des poids, ce qui est bien plus performant qu'une approche brute en O(N²).