Trie (Önek Ağacı)
Son güncelleme
Bir trie ("tray" olarak okunur) veya önek ağacı, bir dize kümesini karakterlerine göre saklar: her kenar bir karakterle etiketlenir ve kökten bir yol bir öneki heceler. Bir öneki paylaşan kelimeler aynı düğümleri paylaşır, dolayısıyla "car", "card" ve "care" hepsi c-a-r yolunu yeniden kullanır. Kelimelerin bir seferde tek karakter eklenerek yalnızca farklılaştıkları yerde dallandığını görmek için yukarıdaki oynat düğmesine basın.
Aramalar karakter başına bir düğüm gezdiğinden, m uzunluğundaki bir kelimeyi aramak, trie'nin kaç kelime tuttuğundan bağımsız olarak O(m) sürer. Bu, trie'leri otomatik tamamlama, yazım denetimi ve önek araması için ideal kılar.
Zaman ve alan karmaşıklığı
| İşlem | Karmaşıklık | Notlar |
|---|---|---|
| Ekleme | O(m) | m = kelimenin uzunluğu |
| Arama | O(m) | Karakter başına bir adım |
| Önek sorgusu | O(m) | Önek düğümüne kadar gez |
| Alan | O(total chars) | Paylaşılan önekler bir kez saklanır |
Adım adım (ekleme)
| Adım | Ne olur |
|---|---|
| 1 | Kök düğümde başla. |
| 2 | Kelimedeki her karakter için eşleşen bir çocuk kenarı ara. |
| 3 | Varsa onu izle (paylaşılan öneki yeniden kullanarak). |
| 4 | Yoksa o karakter için yeni bir çocuk düğüm oluştur. |
| 5 | Son karakterden sonra o düğümü kelime sonu olarak işaretle. |
Çözümlü örnek
Boş bir trie'ye ["car", "card", "care"] ekleniyor:
| Adım | Yapı | İşlem |
|---|---|---|
car ekle | root → c → a → r✓ | Eşleşen çocuk yok, bu yüzden c, a, r oluştur ve r'yi kelime sonu olarak işaretle. |
card ekle | root → c → a → r✓ → d✓ | Mevcut c-a-r yolunu yeniden kullan, ardından yeni bir d çocuğu oluştur ve kelime sonu olarak işaretle. |
care ekle | root → c → a → r✓ → {d✓, e✓} | c-a-r'ı yeniden kullan, r'den yeni bir e çocuğuyla dallan ve e'yi kelime sonu olarak işaretle. |
care ara | root → c → a → r → e✓ | c, a, r, e boyunca gez; son düğüm kelime sonu olarak işaretli, dolayısıyla care mevcut. |
ca ara | root → c → a | Yol var ama a kelime sonu olarak işaretli değil, dolayısıyla ca bir önek ama saklanan bir kelime değil. |
Bir trie ne zaman kullanılır
| Şu durumda kullan | Şu durumda kaçın |
|---|---|
| Bir dize kümesi üzerinde önek sorguları veya otomatik tamamlamaya ihtiyacın olduğunda. | Yalnızca tam anahtar aramalarına ihtiyacın olduğunda - bir karma tablo daha hızlı ve hafiftir. |
| Saklanan birçok kelime ortak önekler paylaşıp düğümler yeniden kullanıldığında. | Anahtarlar uzun ve nadiren örtüştüğünde, karakter başına bir düğüm boşa gider. |
| Anahtarların bir gezinme ile sıralı olarak döndürülmesini istediğinde. | Bellek kısıtlı olduğunda - düğüm başına çocuk işaretçileri önemli ek yük getirir. |
| Arama maliyeti veri kümesi boyutuna değil anahtar uzunluğuna bağlı olmalıysa. | Alfabe çok büyük (örneğin tüm Unicode) ve çocuklar yoğun saklandığında. |
Trie (Prefix Tree) kodu
Python, JavaScript, Java, C++, C dillerinde temiz ve çalıştırılabilir bir Trie (Prefix Tree) uygulaması. Bir dil seçin, kodu kopyalayın veya Coddy Playground'da hazır yüklenmiş olarak açın.
Python ile Trie (Prefix Tree) kodu
Python
1class TrieNode:2 def __init__(self):3 self.children = {}4 self.is_word = False5
6
7class Trie:8 def __init__(self):9 self.root = TrieNode()10
11 def insert(self, word):12 node = self.root13 for ch in word:14 node = node.children.setdefault(ch, TrieNode())15 node.is_word = True16
17 def search(self, word):18 node = self._walk(word)19 return node is not None and node.is_word20
21 def starts_with(self, prefix):22 return self._walk(prefix) is not None23
24 def _walk(self, s):25 node = self.root26 for ch in s:27 if ch not in node.children:28 return None29 node = node.children[ch]30 return node31
32
33trie = Trie()34for word in ["car", "card", "care", "dog"]:35 trie.insert(word)36
37print("search(card): ", trie.search("card"))38print("search(ca): ", trie.search("ca"))39print("starts_with(ca): ", trie.starts_with("ca"))40print("starts_with(do): ", trie.starts_with("do"))41print("starts_with(cat): ", trie.starts_with("cat"))JavaScript ile Trie (Prefix Tree) kodu
JavaScript
1class TrieNode {2 constructor() {3 this.children = {};4 this.isEnd = false;5 }6}7
8class Trie {9 constructor() {10 this.root = new TrieNode();11 }12
13 insert(word) {14 let node = this.root;15 for (const ch of word) {16 if (!node.children[ch]) node.children[ch] = new TrieNode();17 node = node.children[ch];18 }19 node.isEnd = true;20 }21
22 // Walk the prefix; null when a character is missing23 findNode(prefix) {24 let node = this.root;25 for (const ch of prefix) {26 node = node.children[ch];27 if (!node) return null;28 }29 return node;30 }31
32 search(word) {33 const node = this.findNode(word);34 return node !== null && node.isEnd;35 }36
37 startsWith(prefix) {38 return this.findNode(prefix) !== null;39 }40}41
42const trie = new Trie();43for (const word of ["car", "card", "care", "dog"]) trie.insert(word);44console.log("search(\"card\"):", trie.search("card"));45console.log("search(\"ca\"):", trie.search("ca"));46console.log("startsWith(\"ca\"):", trie.startsWith("ca"));Java ile Trie (Prefix Tree) kodu
Java
1public class Main {2 static class Node {3 Node[] children = new Node[26];4 boolean isWord;5 }6
7 static Node root = new Node();8
9 static void insert(String word) {10 Node cur = root;11 for (char c : word.toCharArray()) {12 int i = c - 'a';13 if (cur.children[i] == null) cur.children[i] = new Node();14 cur = cur.children[i];15 }16 cur.isWord = true;17 }18
19 // Follow the path for s; null means no word has this prefix20 static Node walk(String s) {21 Node cur = root;22 for (char c : s.toCharArray()) {23 cur = cur.children[c - 'a'];24 if (cur == null) return null;25 }26 return cur;27 }28
29 static boolean search(String word) {30 Node node = walk(word);31 return node != null && node.isWord;32 }33
34 static boolean startsWith(String prefix) {35 return walk(prefix) != null;36 }37
38 public static void main(String[] args) {39 insert("code");40 insert("coder");41 insert("cool");42 System.out.println("search code: " + search("code"));43 System.out.println("search cod: " + search("cod"));44 System.out.println("startsWith cod: " + startsWith("cod"));45 System.out.println("startsWith cat: " + startsWith("cat"));46 }47}C++ ile Trie (Prefix Tree) kodu
C++
1#include <iostream>2#include <string>3#include <unordered_map>4
5struct TrieNode {6 std::unordered_map<char, TrieNode*> children;7 bool isEnd = false;8};9
10struct Trie {11 TrieNode* root = new TrieNode();12
13 void insert(const std::string& word) {14 TrieNode* node = root;15 for (char c : word) {16 if (!node->children.count(c)) node->children[c] = new TrieNode();17 node = node->children[c];18 }19 node->isEnd = true;20 }21
22 // Follow the path for s; nullptr if a link is missing23 TrieNode* walk(const std::string& s) const {24 TrieNode* node = root;25 for (char c : s) {26 auto it = node->children.find(c);27 if (it == node->children.end()) return nullptr;28 node = it->second;29 }30 return node;31 }32
33 bool search(const std::string& word) const {34 TrieNode* node = walk(word);35 return node != nullptr && node->isEnd;36 }37
38 bool startsWith(const std::string& prefix) const {39 return walk(prefix) != nullptr;40 }41};42
43int main() {44 Trie trie;45 for (const std::string& word : {"car", "card", "care", "dog"}) {46 trie.insert(word);47 }48 std::cout << std::boolalpha;49 std::cout << "search(card): " << trie.search("card") << "\n";50 std::cout << "search(ca): " << trie.search("ca") << "\n";51 std::cout << "startsWith(ca): " << trie.startsWith("ca") << "\n";52 std::cout << "startsWith(dot): " << trie.startsWith("dot") << "\n";53 return 0;54}C ile Trie (Prefix Tree) kodu
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct TrieNode {6 struct TrieNode* children[26];7 bool isEnd;8} TrieNode;9
10TrieNode* newNode(void) {11 return calloc(1, sizeof(TrieNode)); // zeroed links and isEnd12}13
14void insert(TrieNode* root, const char* word) {15 for (; *word; word++) {16 int i = *word - 'a';17 if (root->children[i] == NULL) root->children[i] = newNode();18 root = root->children[i];19 }20 root->isEnd = true;21}22
23// Follow the path for s; NULL if a link is missing24TrieNode* walk(TrieNode* root, const char* s) {25 for (; *s; s++) {26 root = root->children[*s - 'a'];27 if (root == NULL) return NULL;28 }29 return root;30}31
32bool search(TrieNode* root, const char* word) {33 TrieNode* node = walk(root, word);34 return node != NULL && node->isEnd;35}36
37bool startsWith(TrieNode* root, const char* prefix) {38 return walk(root, prefix) != NULL;39}40
41int main(void) {42 TrieNode* root = newNode();43 const char* words[] = {"car", "card", "care", "dog"};44 for (int i = 0; i < 4; i++) insert(root, words[i]);45 printf("search(card): %s\n", search(root, "card") ? "true" : "false");46 printf("search(ca): %s\n", search(root, "ca") ? "true" : "false");47 printf("startsWith(ca): %s\n", startsWith(root, "ca") ? "true" : "false");48 printf("startsWith(dot): %s\n", startsWith(root, "dot") ? "true" : "false");49 return 0;50}Trie SSS
Bir trie ne için kullanılır?
Trie'ler önek tabanlı özellikleri güçlendirir: otomatik tamamlama ve arama önerileri, yazım denetleyicileri, IP yönlendirme tabloları ve sözlük aramaları. "Saklanan herhangi bir kelime bu önekle başlıyor mu?" sorgularına hızlı yanıt gerektiren her yerde bir trie parlar.
Bir trie'nin zaman karmaşıklığı nedir?
Ekleme, arama ve önek sorguları, kaç kelimenin saklandığından bağımsız olarak,
m kelimenin veya önekin uzunluğu olmak üzere hepsi O(m) sürede çalışır. Ödünleşim bellektir: bir trie çok alan kullanabilir, ancak paylaşılan önekler yalnızca bir kez saklanır.Bir trie ile karma tablo arasındaki fark nedir?
Bir karma tablo tam anahtarların ortalama
O(1) aramasını sunar ancak önek sorgularını yanıtlayamaz. Bir trie arama başına biraz daha yavaştır ama önek araması, sıralı gezinme ve otomatik tamamlamayı doğal olarak destekler - bu durumlarda tercih edilmesinin nedeni budur.İkili arama ağacı yerine ne zaman trie kullanmalıyım?
Anahtarların dize olduğunda ve önek aramalarına ihtiyacın olduğunda bir trie kullan: anahtar uzunluğu üzerinden işlem başına
O(m) çalışır, oysa dengeli bir BST O(m log n) maliyetlidir çünkü her karşılaştırma dizeyi tarar ve bunlardan log n tane vardır. Anahtarlar dize benzeri değilse veya bellek ek yükü önek hızından daha önemliyse BST daha iyi bir seçimdir.Bir trie'de bir kelimenin sonu nasıl ele alınır?
Her düğüm, yalnızca eklenen tam bir kelime orada bittiğinde ayarlanan bir kelime sonu bayrağı taşır. Bu olmadan, saklanan bir kelimeyi salt bir önekten ayıramazsın - örneğin
card ekledikten sonra car düğümü vardır ama yalnızca car da eklendiyse kelime olarak bildirilmelidir.Trie'ler önekleri paylaşarak her zaman bellek tasarrufu sağlar mı?
Her zaman değil. Paylaşım yalnızca birçok anahtar örtüştüğünde yardımcı olur; uzun, birbirinden farklı anahtarlarla bir trie, bir karma kümeden çok daha fazla bellek kullanabilir, çünkü her karakter çocuk işaretçileriyle kendi düğümü olur. Sorun alansa, sıkıştırılmış bir radix ağacı tek çocuklu zincirleri birleştirerek bu ek yükü azaltır.
İlgili kaynaklar
Daha fazla görselleştirme
