Trie: C# ile Autocomplete, Prefix Arama ve Bellek Maliyeti

Sürüm notu: Bu yazıdaki kodlar .NET 10, C# 14 ve ASP.NET Core 10 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile, veritabanı örnekleri PostgreSQL 18.6 ile alınmıştır. Angular bileşeni Angular 22.2 paketlerine karşı TypeScript derleyicisiyle tip kontrolünden geçirilmiştir.

Önce Tahmin Et

macOS'taki /usr/share/dict/words dosyasında küçük harfe çevirip tekrarları atınca 234.456 İngilizce kelime kalıyor; toplam 2.248.668 karakter. Bunları sıralı bir string[]'de tutmak 11,7 MB yer kaplıyor. Aynı kelimeleri autocomplete için bir trie'ye koyuyoruz:

long trieBytes = Measure(() => { Trie t = new(); foreach (string w in words) t.Insert(w); return t; }, out object t1);

Trie ortak prefix'leri paylaşır: "algorithm", "algorithmic" ve "algorism" baştaki "algo" harflerini bir kez saklar. O zaman trie array'den daha az mı yer kaplar? 5 MB mı, 12 MB mı, 50 MB mı? Cevap yazının ortasında ve çoğu kişinin beklediği gibi değil.

Trie Nedir: Karakter Karakter Bir Tree

Trie (adı "retrieval" kelimesinden gelir), key'leri bütün olarak değil karakter karakter saklayan bir tree'dir. Kökten başlayan her yol bir prefix'tir; bir kelimenin bittiği node işaretlenir. "dune" ve "dune messiah" ilk dört node'u paylaşır, "dracula" ise yalnız ilk "d"yi. Bir prefix'in var olup olmadığını bulmak için prefix'in karakterleri kadar adım atarsın: kaç kelime saklandığından bağımsız olarak O(m), m prefix uzunluğu.

public sealed record Suggestion(string Text, int Weight);

public sealed class Trie
{
    private sealed class Node
    {
        public Dictionary<char, Node>? Children;
        public string? Word;   // yalnız bir kelimenin bittiği node'da dolu
        public int Weight;
    }

    private readonly Node _root = new();

    public int Count { get; private set; }
    public int NodeCount { get; private set; } = 1;

    public void Insert(string key, int weight = 0, string? display = null)
    {
        Node node = _root;
        foreach (char c in key)
        {
            node.Children ??= [];
            if (!node.Children.TryGetValue(c, out Node? next))
            {
                next = new Node();
                node.Children.Add(c, next);
                NodeCount++;
            }

            node = next;
        }

        if (node.Word is null)
        {
            Count++;
        }

        node.Word = display ?? key;
        node.Weight = weight;
    }

    public bool Contains(string key) => Find(key)?.Word is not null;

    public bool StartsWith(string prefix) => Find(prefix) is not null;

    private Node? Find(string prefix)
    {
        Node? node = _root;
        foreach (char c in prefix)
        {
            if (node.Children is null || !node.Children.TryGetValue(c, out node))
            {
                return null;
            }
        }

        return node;
    }
}

Üç tasarım kararı var. Node'da kelimenin kendisini (Word) tutuyoruz; böylece öneri listesi üretirken yolu yeniden birleştirmemiz gerekmiyor ve key ile ekranda görünecek metin farklı olabiliyor (birazdan Türkçe karakterlerde işe yarayacak). Children dictionary'si lazy oluşturuluyor; yaprak node'ların çoğu hiç child sahibi olmuyor. Ve Contains("dun") ile StartsWith("dun") farklı şeyler: "dun" bir prefix olarak var ama kelime olarak yok.

En İyi N Öneri

Autocomplete'te "d" yazan kullanıcıya binlerce kelime değil, en olası beş öneriyi göstermek isteriz. Her kelimeye bir ağırlık (satış sayısı, arama sıklığı) veriyoruz; prefix'in node'una inip altındaki subtree'yi geziyor ve bir önceki yazıdaki size-K heap ile en iyi N'i tutuyoruz:

public List<Suggestion> Suggest(string prefix, int limit)
{
    Node? start = Find(prefix);
    if (start is null || limit <= 0)
    {
        return [];
    }

    // Tepede en zayıf aday: ağırlık küçükse, eşitse alfabetik olarak büyükse
    PriorityQueue<Suggestion, (int Weight, string Text)> best = new(
        Comparer<(int Weight, string Text)>.Create((a, b) =>
            a.Weight != b.Weight ? a.Weight.CompareTo(b.Weight) : string.CompareOrdinal(b.Text, a.Text)));
    Stack<Node> stack = new();
    stack.Push(start);
    while (stack.Count > 0)
    {
        Node node = stack.Pop();
        if (node.Word is not null)
        {
            Suggestion s = new(node.Word, node.Weight);
            if (best.Count < limit)
            {
                best.Enqueue(s, (s.Weight, s.Text));
            }
            else if (best.TryPeek(out _, out (int Weight, string Text) min)
                     && (s.Weight > min.Weight || (s.Weight == min.Weight && string.CompareOrdinal(s.Text, min.Text) < 0)))
            {
                best.DequeueEnqueue(s, (s.Weight, s.Text));
            }
        }

        if (node.Children is not null)
        {
            foreach (Node child in node.Children.Values) stack.Push(child);
        }
    }

    List<Suggestion> result = [];
    while (best.TryDequeue(out Suggestion? s, out _)) result.Add(s);
    result.Reverse();
    return result;
}

Eşit ağırlıkta alfabetik sırayı da priority'ye kattık; aksi halde bir önceki yazıda gördüğümüz gibi eşit priority'lerde sonuç sırası belirsiz olur ve testler rastgele kırılır. Subtree'yi recursive değil explicit Stack ile geziyoruz; çok uzun bir kelime listesinde derinlik sorun olmasın (serinin 5. yazısı). Maliyet, prefix'e inmek için O(m) artı subtree'deki node sayısı kadar; "a" gibi kısa bir prefix sözlüğün büyük bir kısmını gezer. Buna ölçüm bölümünde döneceğiz.

Testlerden ikisi:

[Fact]
public void Contains_PrefixOnly_ReturnsFalse()
{
    Trie trie = CreateCatalog();
    Assert.True(trie.Contains("dune"));
    Assert.False(trie.Contains("dun"));
    Assert.True(trie.StartsWith("dun"));
    Assert.False(trie.StartsWith("x"));
}

[Fact]
public void Suggest_ReturnsHighestWeightFirst()
{
    List<Suggestion> result = CreateCatalog().Suggest("d", 3);
    Assert.Equal(["Dune", "Dracula", "Don Quixote"], result.Select(s => s.Text));
}

Bellek Maliyeti: Dictionary mi, Sabit Array mi

Klasik ders kitabı trie'si her node'da alfabe boyunda bir array tutar: İngilizce küçük harf için 26 slot. Lookup tek index işlemi, hash yok:

public sealed class AsciiTrie
{
    private sealed class Node
    {
        public readonly Node?[] Children = new Node?[26];
        public bool IsWord;
    }

    private readonly Node _root = new();

    public int NodeCount { get; private set; } = 1;

    public bool Insert(string word)
    {
        Node node = _root;
        foreach (char c in word)
        {
            int i = c - 'a';
            if ((uint)i >= 26)
            {
                return false; // yalnız 'a'..'z'
            }

            if (node.Children[i] is null)
            {
                node.Children[i] = new Node();
                NodeCount++;
            }

            node = node.Children[i]!;
        }

        node.IsWord = true;
        return true;
    }
}

Şimdi açılıştaki sorunun cevabı. Canlı heap'i ölçmek için her ölçümden önce ve sonra tam bir GC (Garbage Collector) çalıştırıp GC.GetGCMemoryInfo(GCKind.FullBlocking).PromotedBytes'a, yani GC'den sağ çıkan byte'lara baktım (bu makinede GC.GetTotalMemory güvenilir sonuç vermedi, kontrol ölçümünde 240 MB'lık bir array'i 472 MB gösterdi):

static long LiveBytes()
{
    GC.Collect(2, GCCollectionMode.Forced, blocking: true, compacting: true);
    return GC.GetGCMemoryInfo(GCKind.FullBlocking).PromotedBytes;
}

words: 234,456, characters: 2,248,668
sorted string[]               11.7 MB
HashSet<string>               16.1 MB
Trie (Dictionary children)   148.9 MB  nodes=758,897
AsciiTrie (26-slot array)    191.1 MB  nodes=758,880

Trie, aynı kelimeleri tutan sıralı array'den 13 kat fazla bellek kullanıyor. Prefix paylaşımı karakter sayısını 2,25 milyondan 759 bin node'a indiriyor, yani gerçekten tasarruf ediyor; ama bir karakter string içinde 2 byte iken bir node onlarca, yüzlerce byte. AsciiTrie'de her node'un 26 referanslık array'i tek başına 232 byte (16 byte header, 8 byte uzunluk, 26 × 8 byte slot) ve slot'ların büyük kısmı boş. Dictionary'li versiyon daha az yer kaplıyor, çünkü yaprak node'lar hiç dictionary oluşturmuyor; ama dolu bir dictionary'nin kendisi de bucket ve entry array'leriyle pahalı (serinin 6. yazısı).

Bu, trie'nin kötü olduğu anlamına gelmiyor; ne için ödeme yaptığını bilmen gerektiği anlamına geliyor. Daha kompakt varyantlar var: tek child'lı zincirleri tek node'da birleştiren radix tree (compressed trie), node'ları array'lerde tutan double-array trie, ya da paylaşılan suffix'leri de birleştiren DAFSA (Deterministic Acyclic Finite State Automaton). Hepsi implementasyon karmaşıklığı karşılığında belleği düşürür.

Türkçe Karakter ve Case Folding

Bookstore'un kataloğunda "İstanbul Hatırası" var ve kullanıcı arama kutusuna istan ya da ISTAN yazıyor. Key'i küçük harfe çevirmek yeterli mi? Gerçek çıktı:

CultureInfo tr = CultureInfo.GetCultureInfo("tr-TR");
string[] samples = ["İstanbul", "ISTANBUL"];
foreach (string s in samples)
{
    string inv = s.ToLowerInvariant();
    string trLower = s.ToLower(tr);
    Console.WriteLine($"{s,-9} invariant={inv} (len {inv.Length})  tr-TR={trLower} (len {trLower.Length})  fold={SearchKey.Fold(s)}");
}

İstanbul  invariant=İstanbul (len 8)  tr-TR=istanbul (len 8)  fold=istanbul
ISTANBUL  invariant=istanbul (len 8)  tr-TR=ıstanbul (len 8)  fold=istanbul

İki ayrı tuzak. ToLowerInvariant() "İ" harfini (U+0130) hiç değiştirmiyor; çıktıda görüldüğü gibi .NET'in invariant casing'i bu harfe dokunmuyor, yani "İstanbul" trie'de büyük İ ile kalır ve "istan" araması onu bulamaz. ToLower(tr-TR) "İ"yi doğru çeviriyor, ama bu kez ASCII (American Standard Code for Information Interchange) "I" harfini "ı"ya çeviriyor: Türkçe klavyesi olmayan biri "ISTANBUL" yazarsa "ıstanbul" arıyoruz. C# Temelleri serisinin "C# String'ler" yazısındaki Türkçe I tuzağının arama motoru versiyonu bu.

Arama key'leri için çözüm, hem saklarken hem ararken aynı katlama (folding) fonksiyonunu kullanmak: Türkçe kurallarla küçült, Unicode NFD (Normalization Form D) ile harfleri temel harf ve aksan olarak ayır, aksanları at, "ı"yı "i"ye eşle:

public static class SearchKey
{
    private static readonly CultureInfo Turkish = CultureInfo.GetCultureInfo("tr-TR");

    // "İstanbul", "ISTANBUL" ve "istanbul" hepsi "istanbul" olur; "Şiir" de "siir"
    public static string Fold(string text)
    {
        string lower = text.Trim().ToLower(Turkish).Normalize(NormalizationForm.FormD);
        StringBuilder sb = new(lower.Length);
        foreach (char c in lower)
        {
            if (CharUnicodeInfo.GetUnicodeCategory(c) == UnicodeCategory.NonSpacingMark)
            {
                continue; // ş = s + U+0327, ç = c + U+0327, ğ = g + U+0306 gibi aksanlar
            }

            sb.Append(c == 'ı' ? 'i' : c);
        }

        return sb.ToString().Normalize(NormalizationForm.FormC);
    }
}

[Theory]
[InlineData("İstanbul", "istanbul")]
[InlineData("ISTANBUL", "istanbul")]
[InlineData("  Şiir Kitabı ", "siir kitabi")]
[InlineData("Çağlayan", "caglayan")]
public void Fold_TurkishText_ProducesAsciiLikeKey(string input, string expected) =>
    Assert.Equal(expected, SearchKey.Fold(input));

Bu bilinçli bir kayıp: "sık" ile "şık" aynı key'e düşer. Arama ve autocomplete için istediğimiz tam olarak bu, çünkü kullanıcı Türkçe karakterleri yazmayabilir; ama key'i kimlik olarak (unique constraint, eşitlik kontrolü) kullanma. Ekranda gösterilecek metni ayrı tuttuğumuz için (display parametresi) kullanıcı yine "İstanbul Hatırası" görüyor. Trie'nin doğrulama testleri:

Test run summary: Passed!
  total: 10
  failed: 0
  succeeded: 10
  skipped: 0
  duration: 306ms

Uçtan Uca: Minimal API ve Angular Arama Kutusu

Trie'yi uygulama açılırken bir kez kurup singleton olarak kaydediyoruz; endpoint yalnız okuyor, bu yüzden thread-safe olması için ek bir şey gerekmiyor:

using Algorithms.Trees;

var builder = WebApplication.CreateBuilder(args);
builder.Services.AddSingleton(_ => BuildCatalogTrie());

var app = builder.Build();

app.MapGet("/api/suggest", (string? q, Trie trie) =>
{
    if (string.IsNullOrWhiteSpace(q) || q.Length > 50)
    {
        return Results.Ok(Array.Empty<Suggestion>());
    }

    return Results.Ok(trie.Suggest(SearchKey.Fold(q), limit: 5));
});

app.Run();

static Trie BuildCatalogTrie()
{
    // Üretimde: başlıklar ve haftalık satışlar açılışta veritabanından gelir
    (string Title, int Sales)[] catalog =
    [
        ("Dune", 950), ("Dune Messiah", 310), ("Dracula", 720), ("Don Quixote", 400),
        ("Dubliners", 120), ("Şu Çılgın Türkler", 85), ("İstanbul Hatırası", 240), ("Ince Memed", 530),
        ("Emma", 150), ("Middlemarch", 90)
    ];

    Trie trie = new();
    foreach ((string title, int sales) in catalog)
    {
        trie.Insert(SearchKey.Fold(title), sales, display: title);
    }

    return trie;
}

Kestrel'e curl ile sorduğumuzda (URL (Uniform Resource Locator) içinde "İ" UTF (Unicode Transformation Format) 8 kodlamasıyla %C4%B0, "ı" %C4%B1 şeklinde kodlanıyor):

$ curl -s "http://127.0.0.1:5712/api/suggest?q=du"
[{"text":"Dune","weight":950},{"text":"Dune Messiah","weight":310},{"text":"Dubliners","weight":120}]
$ curl -s "http://127.0.0.1:5712/api/suggest?q=d"
[{"text":"Dune","weight":950},{"text":"Dracula","weight":720},{"text":"Don Quixote","weight":400},{"text":"Dune Messiah","weight":310},{"text":"Dubliners","weight":120}]
$ curl -s "http://127.0.0.1:5712/api/suggest?q=%C4%B0stan"
[{"text":"İstanbul Hatırası","weight":240}]
$ curl -s "http://127.0.0.1:5712/api/suggest?q=istan"
[{"text":"İstanbul Hatırası","weight":240}]
$ curl -s "http://127.0.0.1:5712/api/suggest?q=SU"
[{"text":"Şu Çılgın Türkler","weight":85}]
$ curl -s "http://127.0.0.1:5712/api/suggest?q=%C4%B1nce"
[{"text":"Ince Memed","weight":530}]
$ curl -s "http://127.0.0.1:5712/api/suggest?q=xyz"
[]

İstan, istan, SU ve ınce hepsi doğru kitabı buluyor. İstemci tarafında her tuşa bir request atmak istemeyiz. Angular'da input'u bir Subject'e akıtıp RxJS (Reactive Extensions for JavaScript) operatörleriyle yavaşlatıyoruz:

import { Component, inject } from '@angular/core';
import { HttpClient, HttpParams } from '@angular/common/http';
import { toSignal } from '@angular/core/rxjs-interop';
import { Subject, debounceTime, distinctUntilChanged, map, of, switchMap } from 'rxjs';

interface Suggestion {
  text: string;
  weight: number;
}

@Component({
  selector: 'app-book-search',
  template: `
    <input type="search" placeholder="Search books" (input)="query$.next($any($event.target).value)" />
    <ul>
      @for (s of suggestions(); track s.text) {
        <li>{{ s.text }}</li>
      }
    </ul>
  `,
})
export class BookSearchComponent {
  private readonly http = inject(HttpClient);
  protected readonly query$ = new Subject<string>();

  protected readonly suggestions = toSignal(
    this.query$.pipe(
      map(q => q.trim()),
      debounceTime(250),
      distinctUntilChanged(),
      // switchMap: yeni bir tuş önceki request'i iptal eder
      switchMap(q => q.length < 2
        ? of([] as Suggestion[])
        : this.http.get<Suggestion[]>('/api/suggest', { params: new HttpParams().set('q', q) })),
    ),
    { initialValue: [] as Suggestion[] },
  );
}

debounceTime(250) kullanıcı 250 ms durana kadar bekler, distinctUntilChanged aynı sorguyu tekrar göndermez, switchMap de yeni sorgu gelince eski HTTP (Hypertext Transfer Protocol) isteğini iptal eder; böylece geç dönen eski bir cevap yeni sonucun üstüne yazılmaz. Debounce'un kendisini JavaScript İleri serisinin "JavaScript Performans İpuçları" yazısında anlattık.

Alternatiflerle Karşılaştırma ve Ölçüm

Trie'nin en ciddi rakibi, sıralı array ve binary search. Prefix'le başlayan kelimeler sıralı array'de yan yana durur; serinin 10. yazısındaki lower bound ile ilkini bulup prefix bitene kadar ilerlersin:

// words StringComparer.Ordinal ile sıralı olmalı
public static List<string> StartsWith(string[] words, string prefix, int limit)
{
    int lo = 0, hi = words.Length;
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (string.CompareOrdinal(words[mid], prefix) < 0) lo = mid + 1;
        else hi = mid;
    }

    List<string> result = [];
    for (int i = lo; i < words.Length && result.Count < limit && words[i].StartsWith(prefix, StringComparison.Ordinal); i++)
    {
        result.Add(words[i]);
    }

    return result;
}

Üç yaklaşımı aynı işle ölçtüm: 234.456 kelimenin her birine rastgele bir ağırlık verip prefix'le başlayanlar arasından en ağır 10'unu bulmak. Sıralı array versiyonu binary search ile aralığın başını bulup aralığı tarıyor, linear scan bütün listeyi geziyor; ikisi de top-10 için aynı size-K heap'i kullanıyor. "algo" ile başlayan 40, "pre" ile başlayan 3.032 kelime var.

Ölçümler Apple M5 (10 çekirdek), macOS 27.0.1, .NET 10.0.13, BenchmarkDotNet 0.15.8 ile alındı. Benchmark'ları tek tek çalıştırdım ama makinede paralel işler vardı; mutlak sayılara değil oranlara bak.

| Method            | Prefix | Mean         | Ratio | Allocated |
|------------------ |------- |-------------:|------:|----------:|
| Trie_Top10        | algo   |   1,035.9 ns | 0.004 |    2752 B |
| SortedArray_Top10 | algo   |     200.1 ns | 0.001 |     344 B |
| LinearScan_Top10  | algo   | 242,784.8 ns | 1.002 |     296 B |
|                   |        |              |       |           |
| Trie_Top10        | pre    |  68,517.4 ns |  0.28 |   99312 B |
| SortedArray_Top10 | pre    |   7,501.6 ns |  0.03 |     344 B |
| LinearScan_Top10  | pre    | 248,770.7 ns |  1.00 |     296 B |

Linear scan'i ikisi de rahatça geçiyor. Ama sıralı array, trie'yi 5 ile 9 kat farkla yeniyor. Trie, subtree'deki her node'u pointer takip ederek ve dictionary enumerator'larıyla geziyor (her node'da Values üzerinde foreach, "pre" için 97 KB allocation); sıralı array'de aynı 3.032 kelime ardışık bellekte. Ders: bu sözlük gibi bir kez yüklenip hiç değişmeyen veride trie'yi seçmek için "prefix araması" yeterli sebep değil.

Trie'nin gerçekten öne geçtiği yerler başka. Veri sürekli değişiyorsa sıralı array'e insert O(n) kaydırma ister, trie'ye O(m). Kullanıcı her tuşa bastığında aramaya baştan başlamak yerine bir önceki node'dan bir karakter ilerleyebilirsin. Ve her node'da o subtree'nin en iyi N önerisini önceden hesaplayıp saklarsan, Suggest subtree gezmeyi tamamen bırakır ve O(m)'ye iner; büyük arama kutularının kullandığı yöntem bu, karşılığında bellek daha da artar.

Veri zaten veritabanındaysa, prefix araması B+tree index'in tam istediği iştir (serinin 12. yazısı). PostgreSQL'de aynı kelimeleri bir tabloya yükledim. Varsayılan en_US.utf8 collation'ında düz bir index LIKE 'algo%' için kullanılmıyor; planner paralel seq scan seçiyor. text_pattern_ops operator class'ıyla oluşturulan index ise prefix'i bir range'e çeviriyor:

CREATE INDEX ix_words_word_pattern ON words (word text_pattern_ops);
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, BUFFERS) SELECT word FROM words WHERE word LIKE 'algo%';

 Index Only Scan using ix_words_word_pattern on words (actual rows=31.00 loops=1)
   Index Cond: ((word ~>=~ 'algo'::text) AND (word ~<~ 'algp'::text))
   Filter: (word ~~ 'algo%'::text)
   Heap Fetches: 31
   Index Searches: 1
   Buffers: shared hit=1 read=3
 Execution Time: 0.046 ms

'algo' ile 'algp' arasındaki aralık, binary search'teki "lower bound'dan başla, prefix bitene kadar git" fikrinin ta kendisi; 31 satır (tablo büyük/küçük harf ayrımlı), dört page. Elasticsearch gibi arama motorları ise edge n-gram ve completion suggester gibi yapılarla bu işi dağıtık ve typo-toleranslı yapar; onu ilerideki Elasticsearch serisinde ele alacağız.

Üretimde Dikkat

Belleği ölç, tahmin etme. 50.000 kitap başlığı için trie birkaç MB'tır ve sorun değildir; on milyonlarca ürün ve açıklama metni için ise yukarıdaki oranla gigabyte'lara çıkabilir. Container'ın memory limit'ini bil ve trie'yi bir kez gerçek veriyle kurup GC.GetGCMemoryInfo() ile bak.

Güncelleme stratejisi. Trie'yi açılışta kuruyorsak katalog değiştiğinde ne olacak? Basit ve güvenli yol, yeni trie'yi arka planda kurup tek bir referans atamasıyla değiştirmek (Volatile.Write ya da bir holder object'te Interlocked.Exchange); okuyucular kilit beklemeden ya eski ya yeni trie'yi görür. Aynı trie'yi yerinde değiştirmek eşzamanlı okumalarla yarışır.

Input'u sınırla. Endpoint'te q.Length > 50 kontrolü var; çok kısa prefix'ler (tek harf) ise subtree'nin büyük kısmını gezer. İstemcide en az iki karakter beklemek ve sunucuda rate limit uygulamak, autocomplete endpoint'inin en sık çağrılan endpoint olduğu gerçeğine karşı basit önlemler.

Normalizasyonu tek yerde tut. Saklarken ve ararken farklı katlama fonksiyonu kullanmak, "bazen bulamıyor" diye raporlanan ve tekrarlanması zor hataların klasik kaynağı. SearchKey.Fold gibi tek bir fonksiyon ve onun testleri bu riski kapatır.

Sık Düşülen Tuzaklar

Trie'nin bellek maliyetini hafife almak. Ölçümde gördüğümüz gibi prefix paylaşımı node sayısını azaltır ama node'un kendisi karakterden onlarca kat pahalıdır. 13 kat fark, "trie yer kazandırır" sezgisinin tam tersi.

ToLowerInvariant ile Türkçe metin katlamak. "İ" değişmeden kalır ve arama sessizce eksik sonuç verir; hata loglarda görünmez, sadece kullanıcı "bulamadım" der.

Prefix ile kelimeyi karıştırmak. Contains yerine StartsWith kullanan bir doğrulama "dun"u geçerli bir başlık sayar. İkisini ayrı test et.

Unicode surrogate pair'leri. Trie'miz char üzerinde çalışıyor; emoji gibi iki char'lık karakterler iki node'a bölünür. Başlıklarda emoji yoksa sorun değil, ama kullanıcı girdisini key yapıyorsan Rune ile çalışmayı düşün.

Küçük Bir Deneme

★☆☆ Trie'ye Remove(string key) ekle: kelime işaretini kaldır ve artık hiçbir kelimeye yol vermeyen node'ları budayarak yukarı çık. NodeCount'un doğru azaldığını test et.

★★☆ Her node'da o subtree'nin en iyi 5 önerisini saklayan bir varyant yaz (insert sırasında yol boyunca güncelle). Benchmark'ı "pre" prefix'iyle tekrar çalıştır ve bellek ölçümünü de yenile: hız kaç kat arttı, bellek ne kadar büyüdü?

★★★ Tek child'lı zincirleri birleştiren bir radix tree yaz (node'da tek karakter yerine bir string parçası). Aynı 234.456 kelime için node sayısını ve canlı belleği Trie ve sıralı array ile karşılaştır.

Trie ile key'leri bir tree'nin yollarına yaydık. Bir sonraki yazıda tree'nin kısıtlarını tamamen bırakıyoruz: her node'un birden fazla parent'ı olabildiği, döngülerin mümkün olduğu yapılar. Takip ilişkileri, şehirler arası yollar, project bağımlılıkları; hepsi graph. Adjacency list, BFS (Breadth-First Search) ve DFS (Depth-First Search) ile başlıyoruz.