TrieNode Sınıfı: Ekleme ve Arama
Çocuk sözlüğü ve is_end bayrağı içeren bir TrieNode oluşturun, ekleme ve tam eşleşme aramasını uygulayın; m’nin sözcük uzunluğu olduğu işlem başına O(m) zamanı inceleyin.
TrieNode Sınıfı: Ekleme ve Arama, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Trie Nedir?
Trie (önek ağacı), her düğümün bir karakteri temsil ettiği ağaç biçimli bir veri yapısıdır. Sözcükler, kökten yaprağa kadar karakterler zincirlenerek saklanır. Kök, boş bir dizeyi temsil eder. Kökten is_end = True olan bir düğüme giden her yol, saklanan bir sözcüğü oluşturur. Trie yapıları; otomatik tamamlama, yazım denetimi ve IP yönlendirmesi gibi önek tabanlı sorgular için idealdir ve bu kullanım alanlarında karma tablolardan daha iyi performans gösterir.
TrieNode Sınıf Tasarımı
Bir TrieNode iki alana sahiptir: children — karakterleri alt TrieNode'lara eşleyen bir sözlük — ve is_end — bu düğümün saklanan bir sözcüğün sonu olup olmadığını belirten bir boole değeri. Sabit 26 karakterlik bir dizi yerine sözlük kullanmak, yapıyı herhangi bir karakter kümesine geneller ve seyrek Trie yapılarında bellek tasarrufu sağlar. Trie içindeki her düğüm, kendisinin altındaki sözcüklerde tam olarak bir karakter konumunu temsil eder.
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False # True if a word ends here
class Trie:
def __init__(self):
self.root = TrieNode()
def __repr__(self):
return f'Trie(root with {len(self.root.children)} children)'
t = Trie()
print(t) # Trie(root with 0 children)Ekleme İşlemi
Bir sözcüğü eklemek için kökten başlayarak ilerleyin ve geçerli düğümün children alanında henüz bulunmayan her karakter için yeni bir TrieNode oluşturun. Tüm karakterleri işledikten sonra son düğümde is_end = True değerini ayarlayın. 'apple' ve 'app' sözcüklerini eklemek a→p→p→l→e zincirini oluşturur ('apple' için son düğüm işaretlenir); 3. konumdaki p de 'app' için sözcük sonu olarak işaretlenir.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
t = Trie()
t.insert('apple')
t.insert('app')
print('Inserted apple and app')
print('app is_end:', t.root.children['a'].children['p'].children['p'].is_end)Arama İşlemi
Tam bir sözcüğü aramak için her karakteri izleyerek Trie içinde ilerleyin. Geçerli düğümün children alanında herhangi bir karakter eksikse Yanlış döndürün. Tüm karakterler bulunursa node.is_end değerini döndürün — bu değer yalnızca sözcük tam olarak burada bitiyorsa Doğru olur, yalnızca bir önek mevcutsa olmaz. «Önek mevcut» ile «tam sözcük mevcut» arasındaki bu ayrım kritik öneme sahiptir ve sıkça sınanır.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.is_end # must be a complete word
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False (app not inserted)
print(t.search('orange')) # FalseÖnekle Başlama (Önek Araması)
starts_with yöntemi, eklenmiş herhangi bir sözcüğün verilen önekle başlayıp başlamadığını denetler. Aramayla aynı şekilde ilerler, ancak is_end değerini denetlemek yerine, tüm önek karakterleri başarıyla izlendiğinde hemen Doğru döndürür — yani önek yolu Trie içinde mevcuttur.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children: return False
node = node.children[c]
return node.is_end
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return False
node = node.children[c]
return True # prefix path exists
t = Trie()
t.insert('apple')
print(t.starts_with('app')) # True
print(t.starts_with('ape')) # False
print(t.search('app')) # False (not inserted)Zaman ve Alan Karmaşıklığı
Her Trie işlemi (insert, search, starts_with), sözcük uzunluğu m olduğunda O(m) zaman alır; en fazla m düğüm boyunca ilerleriz. Alan: O(alfabe boyutu × N × M); burada N sözcük sayısı, M ise ortalama sözcük uzunluğudur. Uygulamada ortak önekler alan kullanımını önemli ölçüde azaltır. Karma tablo tabanlı bir children sözlüğü, seyrek Trie yapılarında sabit 26 karakterlik bir diziden daha az alan kullanır; bunun karşılığında her aramada biraz daha yüksek sabit ek yük getirir.
Sözlük Yerine Dizi Kullanma
Yalnızca küçük İngilizce harfler için children = [None] * 26 biçiminde sabit boyutlu bir dizi kullanın; dizin ord(c) - ord('a') ile hesaplanır. Bu yaklaşım daha hızlıdır (karma tabloya kıyasla O(1) alt düğüm araması) ve öngörülebilir bir bellek düzenine sahiptir. Karakter kümesi büyük veya bilinmiyorsa (örneğin Unicode) sözlük sürümünü, yalnızca küçük harflerin bulunduğu yarışma tarzı problemlerde ise dizi sürümünü kullanın.
class TrieNodeArray:
def __init__(self):
self.children = [None] * 26
self.is_end = False
class TrieArray:
def __init__(self):
self.root = TrieNodeArray()
def insert(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = TrieNodeArray()
node = node.children[idx]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None: return False
node = node.children[idx]
return node.is_end
t = TrieArray()
t.insert('cat')
print(t.search('cat')) # True
print(t.search('car')) # FalseSilme İşlemi
Trie'den silme işlemi üç durumu ele almalıdır: (1) sözcük mevcut değilse — hiçbir şey yapmayın; (2) sözcük mevcut, ancak başka bir sözcüğün önekıyse — yalnızca is_end değerini kaldırın; (3) sözcük mevcut ve başka bir sözcüğün öneki değilse — düğümleri aşağıdan yukarıya silin, bir düğümün başka alt düğümleri olduğu veya başka bir sözcüğün sonu olduğu noktada durun. Silme işlemi mülakatlarda nadiren sınanır, ancak kavramsal olarak bilinmesi yararlıdır.
Önekle Başlayan Sözcükleri Sayma
Her düğüme bir count alanı ekleyin ve her ekleme geçişinde bu alanı artırın. Verilen bir önekle başlayan sözcükleri saymak için öneğin son düğümüne ilerleyin ve onun sayısını döndürün. Bu yöntem, tüm alt düğümler boyunca ilerlemeden O(m) süreli otomatik tamamlama sorgularını mümkün kılar ve gerçek dünyadaki otomatik tamamlama sistemleri için yararlı bir genişletmedir.
class TrieNodeCount:
def __init__(self):
self.children = {}
self.is_end = False
self.count = 0 # words passing through this node
class TrieCount:
def __init__(self):
self.root = TrieNodeCount()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNodeCount()
node = node.children[c]
node.count += 1 # increment on each level
node.is_end = True
def count_with_prefix(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return 0
node = node.children[c]
return node.count
t = TrieCount()
for w in ['apple','app','application','apply']:
t.insert(w)
print(t.count_with_prefix('app')) # 4
print(t.count_with_prefix('appl')) # 3Trie ile Karma Tablo Karşılaştırması
Bir karma tablo, ortalama O(m) sürede tam arama yapabilir, ancak önek sorgularını verimli biçimde yanıtlayamaz (tüm anahtarların taranması gerekir). Bir Trie, önek uzunluğu p olduğunda önek sorgularını O(p) sürede yanıtlar, sözcükleri ortak öneklere göre doğal biçimde gruplar ve karma işlemi gerektirmez. Şu durumlarda Trie kullanın: sık önek sorguları, otomatik tamamlama, yazım denetimi. Şu durumda karma tablo kullanın: yalnızca tam aramalar gerekiyorsa.
Gerçek Dünya Sistemlerinde Trie Yapıları
Trie yapılarının gerçek dünyadaki kullanım alanları arasında otomatik tamamlama (Google arama önerileri), yazım denetleyicileri (en yakın eşleşen sözcükleri bulma), IP yönlendirmesi (yönlendiricilerde en uzun önek eşleştirmesi), T9 tahmine dayalı metin (karakterlerin belirsizliğini giderme) ve DNS çözümleyicileri (alan adlarını hiyerarşik olarak arama) bulunur. Her durumda, işlem başına O(m) maliyet ve O(ALPHABET × düğüm) alan kullanımı arasındaki ödünleşim, Trie'yi büyük ölçekte hızlı ve önek farkındalıklı aramalar için doğru araç hâline getirir.
Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayışınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: bir TrieNode, children sözlüğü ile is_end boole değerine sahiptir, insert karakter karakter ilerler, gerektiğinde düğümler oluşturur ve sonunda is_end değerini ayarlar ve search is_end değerini denetlerken starts_with yalnızca önek yolunun mevcut olup olmadığını denetler. Sırada önek tabanlı otomatik tamamlamayı ve starts_with yöntemini daha ayrıntılı biçimde ekleyeceğiz.
Sıkça Sorulan Sorular
“TrieNode Sınıfı: Ekleme ve Arama” dersi ücretsiz mi?
Evet — “TrieNode Sınıfı: Ekleme ve Arama” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“TrieNode Sınıfı: Ekleme ve Arama” dersinde ne öğreneceğim?
Çocuk sözlüğü ve is_end bayrağı içeren bir TrieNode oluşturun, ekleme ve tam eşleşme aramasını uygulayın; m’nin sözcük uzunluğu olduğu işlem başına O(m) zamanı inceleyin. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.
“TrieNode Sınıfı: Ekleme ve Arama” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- TrieNode Sınıfı: Ekleme ve Arama
- Ön Ek Araması ve Şununla Başlar
- Trie’da Joker ve Düzenli İfade Araması
- Sözcük Araması II: Trie + Izgarada Geri İzleme