Trie Nedir?

Bir trie ("try" olarak okunur, retrieval kelimesinin kısaltmasıdır), dizeleri karakterlerine göre depolamak ve aramak için oluşturulmuş ağaç şeklinde bir veri yapısıdır. Ağaçtaki her kenar tek bir karakterle etiketlenir ve kökten işaretli bir düğüme kadar inen her yol, depolanan bir kelimeyi oluşturur.

Bu yapı, önek (prefix) sorularını son derece hızlı hale getirir. Trie'nin "car" ile başlayan herhangi bir kelime içerip içermediğini kontrol etmek, kaç bin kelime depolanmış olursa olsun, kökten itibaren sadece üç karakter araması yapmaktır. Trie'ler; otomatik tamamlama, yazım denetimi ve IP yönlendirme tabloları gibi özelliklerin arkasındaki motordur.

Trie'deki her düğüm (node) iki parça durum bilgisi tutar:

• children: bir karakterden bir sonraki TrieNode'a giden bir eşleme (map).
• isEndOfWord: kökten bu düğüme giden yol, eklenmiş olan tam bir kelimeyi oluşturduğunda true olan bir bayrak.

Bir trie üzerindeki beş ana işlem şunlardır:

1. Insert: Yol boyunca eksik düğümleri oluşturarak bir kelime ekler.
2. Search: Tam bir kelimenin depolanıp depolanmadığını kontrol eder.
3. StartsWith: Depolanan herhangi bir kelimenin verilen öneke sahip olup olmadığını kontrol eder.
4. Delete: Bir kelimeyi kaldırır ve ölü dalları budar.
5. WordCount: Kaç tane farklı kelimenin depolandığını sayar.

Hadi bir Trie sınıfı oluşturalım!