Trie (Önek Ağacı)

Ağaçlar O(L) O(Σ · N)

Karakterlerle anahtarlanan ağaç: her kök-düğüm yolu bir önek yazar, böylece ekleme ve arama yalnızca kelime uzunluğu kadar maliyetlidir.

KelimelerAra

1/25

"cat" ekleniyor: 'c' için düğüm oluşturuluyor.

DeğişmezKökten gelen yol bir ön ek yazar; bir düğümün torunları tam olarak onu uzatan kelimelerdir.

mevcutkarşılaştıreklesildöndür

trie.c

#define R 26
typedef struct Trie {
    struct Trie *next[R];
    int end;
} Trie;
 
void insert(Trie *root, const char *w) {
    Trie *node = root;
    for (int i = 0; w[i]; i++) {
        int c = w[i] - 'a';
        if (!node->next[c])
            node->next[c] = newTrie();
        node = node->next[c];
    }
    node->end = 1;
}
 
int search(Trie *root, const char *w) {
    Trie *node = root;
    for (int i = 0; w[i]; i++) {
        int c = w[i] - 'a';
        if (!node->next[c]) return 0;
        node = node->next[c];
    }
    return node->end;
}

Trie (Önek Ağacı) nasıl çalışır?

Karakter başına bir ağaç düğümü; kelime bir kök-düğüm yoludur. Aynı öneki paylaşan tüm kelimeler o yolu paylaşır; arama maliyeti sözlük boyutuna değil kelime uzunluğuna bağlıdır.

Ne zaman kullanılır?

Otomatik tamamlama, önek arama, yazım denetleyiciler, IP yönlendirme tabloları.