Trie (Prefix Tree) Veri Yapısı

1// Trie (Prefix Tree) JavaScript implementasyonu
2class TrieNode {
3  constructor() {
4    // Her düğüm için karakter-düğüm eşlemesi
5    this.children = new Map();
6    // Bu düğümde bir kelime bitip bitmediğini belirten flag
7    this.isEndOfWord = false;
8    // Opsiyonel: kelimenin kendisini saklamak için
9    this.value = null;
10    // Opsiyonel: kelime sayısını takip etmek için
11    this.count = 0;
12  }
13}
14
15class Trie {
16  constructor() {
17    // Kök düğüm - boş karakter temsil eder
18    this.root = new TrieNode();
19    // Toplam benzersiz kelime sayısı
20    this.wordCount = 0;
21  }
22
23  // Yeni kelime ekleme işlemi - O(m) zaman karmaşıklığı
24  insert(word) {
25    if (!word || word.length === 0) return;
26
27    let currentNode = this.root;
28    const normalizedWord = word.toLowerCase();
29
30    // Her karakter için düğüm oluştur veya mevcut düğüme git
31    for (const char of normalizedWord) {
32      if (!currentNode.children.has(char)) {
33        currentNode.children.set(char, new TrieNode());
34      }
35      currentNode = currentNode.children.get(char);
36    }
37
38    // Kelime sonu işaretleme ve sayaç güncelleme
39    if (!currentNode.isEndOfWord) {
40      this.wordCount++;
41    }
42    currentNode.isEndOfWord = true;
43    currentNode.value = word;
44    currentNode.count = (currentNode.count || 0) + 1;
45  }
46
47  // Kelime arama işlemi - O(m) zaman karmaşıklığı
48  search(word) {
49    if (!word || word.length === 0) return false;
50
51    const node = this.findNode(word.toLowerCase());
52    return node !== null && node.isEndOfWord;
53  }
54
55  // Prefix varlığı kontrolü - O(m) zaman karmaşıklığı
56  startsWith(prefix) {
57    if (!prefix || prefix.length === 0) return true;
58
59    return this.findNode(prefix.toLowerCase()) !== null;
60  }
61
62  // Belirli prefix ile başlayan tüm kelimeleri bulma
63  getWordsWithPrefix(prefix) {
64    const words = [];
65    const prefixNode = this.findNode(prefix.toLowerCase());
66
67    if (prefixNode) {
68      this.collectWords(prefixNode, prefix.toLowerCase(), words);
69    }
70
71    return words;
72  }
73
74  // Autocomplete öneriler - en çok kullanılan kelimeler öncelikli
75  getAutocompleteSuggestions(prefix, maxSuggestions = 10) {
76    const words = this.getWordsWithPrefix(prefix);
77    
78    // Count'a göre sırala ve en çok kullanılanları döndür
79    return words
80      .map(word => ({
81        word,
82        count: this.getWordCount(word)
83      }))
84      .sort((a, b) => b.count - a.count)
85      .slice(0, maxSuggestions)
86      .map(item => item.word);
87  }
88
89  // Kelime silme işlemi - O(m) zaman karmaşıklığı
90  delete(word) {
91    if (!word || word.length === 0) return false;
92
93    return this.deleteHelper(this.root, word.toLowerCase(), 0);
94  }
95
96  // Trie'daki tüm kelimeleri alma
97  getAllWords() {
98    const words = [];
99    this.collectWords(this.root, '', words);
100    return words;
101  }
102
103  // Toplam benzersiz kelime sayısını döndürme
104  getWordCount() {
105    return this.wordCount;
106  }
107
108  // Belirli bir kelimenin kaç kez eklendiğini öğrenme
109  getWordFrequency(word) {
110    const node = this.findNode(word.toLowerCase());
111    return node && node.isEndOfWord ? node.count : 0;
112  }
113
114  // En uzun ortak prefix bulma
115  getLongestCommonPrefix() {
116    let current = this.root;
117    let prefix = '';
118
119    // Tek bir çocuk varsa ve kelime sonu değilse devam et
120    while (current.children.size === 1 && !current.isEndOfWord) {
121      const char = Array.from(current.children.keys())[0];
122      prefix += char;
123      current = current.children.get(char);
124    }
125
126    return prefix;
127  }
128
129  // Trie'ın istatistiklerini döndürme
130  getStatistics() {
131    let nodeCount = 0;
132    let maxDepth = 0;
133    let totalPaths = 0;
134
135    const traverse = (node, depth) => {
136      nodeCount++;
137      maxDepth = Math.max(maxDepth, depth);
138      
139      if (node.isEndOfWord) {
140        totalPaths++;
141      }
142
143      for (const child of node.children.values()) {
144        traverse(child, depth + 1);
145      }
146    };
147
148    traverse(this.root, 0);
149
150    return {
151      nodeCount,
152      maxDepth,
153      totalWords: this.wordCount,
154      totalPaths,
155      avgDepth: totalPaths > 0 ? maxDepth / totalPaths : 0
156    };
157  }
158
159  // Yardımcı metod: belirli kelime/prefix için düğüm bulma
160  findNode(word) {
161    let currentNode = this.root;
162
163    for (const char of word) {
164      if (!currentNode.children.has(char)) {
165        return null;
166      }
167      currentNode = currentNode.children.get(char);
168    }
169
170    return currentNode;
171  }
172
173  // Belirli düğümden başlayarak tüm kelimeleri toplama
174  collectWords(node, prefix, words) {
175    if (node.isEndOfWord && node.value) {
176      words.push(node.value);
177    }
178
179    // Tüm çocukları dolaş ve kelimeleri topla
180    node.children.forEach((childNode, char) => {
181      this.collectWords(childNode, prefix + char, words);
182    });
183  }
184
185  // Rekursif silme yardımcı metodu
186  deleteHelper(node, word, index) {
187    if (index === word.length) {
188      // Kelimenin sonuna ulaştık
189      if (!node.isEndOfWord) {
190        return false; // Kelime mevcut değil
191      }
192
193      node.isEndOfWord = false;
194      node.value = null;
195      this.wordCount--;
196
197      // Düğümün çocuğu yoksa silinebilir
198      return node.children.size === 0;
199    }
200
201    const char = word[index];
202    const childNode = node.children.get(char);
203
204    if (!childNode) {
205      return false; // Kelime mevcut değil
206    }
207
208    const shouldDeleteChild = this.deleteHelper(childNode, word, index + 1);
209
210    // Çocuk düğümü silinmeli mi kontrol et
211    if (shouldDeleteChild) {
212      node.children.delete(char);
213      // Mevcut düğüm de silinebilir mi kontrol et
214      return !node.isEndOfWord && node.children.size === 0;
215    }
216
217    return false;
218  }
219
220  // Belirli kelimenin count değerini döndürme
221  getWordCount(word) {
222    const node = this.findNode(word.toLowerCase());
223    return node && node.isEndOfWord ? node.count : 0;
224  }
225}
226
227// Kullanım örneği ve test
228const trie = new Trie();
229
230// Kelime ekleme
231const words = ['cat', 'cats', 'car', 'card', 'care', 'careful', 'cars', 'carry'];
232words.forEach(word => trie.insert(word));
233
234// Arama işlemleri
235console.log('Search "car":', trie.search('car')); // true
236console.log('Search "care":', trie.search('care')); // true
237console.log('Search "caring":', trie.search('caring')); // false
238
239// Prefix kontrolü
240console.log('StartsWith "car":', trie.startsWith('car')); // true
241console.log('StartsWith "dog":', trie.startsWith('dog')); // false
242
243// Autocomplete
244console.log('Words with prefix "car":', trie.getWordsWithPrefix('car'));
245// ['car', 'card', 'care', 'careful', 'cars', 'carry']
246
247// İstatistikler
248console.log('Trie statistics:', trie.getStatistics());