Tree ve Binary Search Tree: C# ile Insert, Delete ve Traversal

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 alınmıştır.

Önce Tahmin Et

Bookstore'un stok servisi ürün ID'lerini kendi yazdığı bir binary search tree'de tutuyor. Aynı 10.000 ID iki farklı şekilde yükleniyor: bir gün rastgele sırayla, ertesi gün veritabanından ORDER BY Id ile sıralı gelerek. İki tree'de de aynı 10.000 ID var.

İki tree'nin yüksekliği ne olur? Rastgele sırayla kurulan tree'de 1.000 arama 20 µs civarında sürüyorsa, sıralı kurulan tree'de ne kadar sürer?

Tree Terimleri ve BST Kuralı

Tree, her node'un sıfır ya da daha fazla çocuğu olduğu, döngü içermeyen hiyerarşik bir yapı. En üstteki node root, çocuğu olmayan node'lar leaf. Bir node'un depth'i root'tan ona kadar olan kenar sayısı; tree'nin height'ı en derin leaf'e kadar olan seviye sayısı. Binary tree'de her node'un en fazla iki çocuğu var: left ve right.

Binary search tree (BST) bunlara tek bir kural ekliyor: her node için sol alt tree'deki bütün değerler node'dan küçük, sağ alt tree'deki bütün değerler büyük. "Bütün" kelimesi önemli; yalnızca doğrudan çocuklar değil, alt tree'nin tamamı. Bu kural sayesinde arama, binary search gibi her adımda bir yarıyı eliyor: aranan değer node'dan küçükse sağ alt tree'ye hiç bakmaya gerek yok.

namespace Algorithms.Trees;

public sealed class TreeNode<T>(T value)
{
    public T Value { get; set; } = value;
    public TreeNode<T>? Left { get; set; }
    public TreeNode<T>? Right { get; set; }
}

Insert ve Find

// her node için: sol alt tree < node < sağ alt tree; tekrar eden değerler yok sayılır
public sealed class BinarySearchTree<T>(IComparer<T>? comparer = null)
{
    private readonly IComparer<T> _comparer = comparer ?? Comparer<T>.Default;

    public TreeNode<T>? Root { get; private set; }
    public int Count { get; private set; }

    public bool Insert(T value)
    {
        if (Root is null)
        {
            Root = new TreeNode<T>(value);
            Count = 1;
            return true;
        }
        // iterative: dejenere bir tree binlerce seviye derin olabilir
        TreeNode<T> node = Root;
        while (true)
        {
            int cmp = _comparer.Compare(value, node.Value);
            if (cmp == 0) return false;
            if (cmp < 0)
            {
                if (node.Left is null) { node.Left = new TreeNode<T>(value); break; }
                node = node.Left;
            }
            else
            {
                if (node.Right is null) { node.Right = new TreeNode<T>(value); break; }
                node = node.Right;
            }
        }
        Count++;
        return true;
    }

    public bool Contains(T value)
    {
        TreeNode<T>? node = Root;
        while (node is not null)
        {
            int cmp = _comparer.Compare(value, node.Value);
            if (cmp == 0) return true;
            node = cmp < 0 ? node.Left : node.Right;
        }
        return false;
    }
}

İkisi de root'tan başlayıp her adımda sola ya da sağa inen tek bir yol izliyor; maliyet tree'nin yüksekliği kadar, O(h). Tree dengeliyse h ≈ log₂ n ve 1 milyon node'da yaklaşık 20 adım. Insert'i iterative yazdık, çünkü h'nin ne olacağı insert sırasına bağlı; birazdan bunun neden önemli olduğunu göreceğiz. Tekrar eden değerleri yok saymak bir tasarım kararı. SortedSet<T> de aynısını yapıyor ve Add false dönüyor. Tekrarlara izin vermek isteseydik her node'da bir sayaç tutardık.

Delete'in Üç Durumu

Silme, BST'nin en çok hata yapılan işlemi, çünkü silinen node'un çocuk sayısına göre üç ayrı durum var:

public bool Remove(T value)
{
    int before = Count;
    Root = Remove(Root, value);
    return Count < before;
}

// bu alt tree'nin yeni root'unu döner
private TreeNode<T>? Remove(TreeNode<T>? node, T value)
{
    if (node is null) return null;
    int cmp = _comparer.Compare(value, node.Value);
    if (cmp < 0) { node.Left = Remove(node.Left, value); return node; }
    if (cmp > 0) { node.Right = Remove(node.Right, value); return node; }

    // bulundu
    if (node.Left is null) { Count--; return node.Right; }   // durum 1 ve 2: çocuk yok ya da yalnız sağ
    if (node.Right is null) { Count--; return node.Left; }   // durum 2: yalnız sol

    // durum 3: iki çocuk. In-order successor (sağ alt tree'nin en küçüğü) yerine geçer.
    TreeNode<T> successor = node.Right;
    while (successor.Left is not null) successor = successor.Left;
    node.Value = successor.Value;
    node.Right = Remove(node.Right, successor.Value); // successor'ın sol çocuğu yok: durum 1 ya da 2
    return node;
}

Leaf silinirken node'u parent'ından koparmak yetiyor. Tek çocuklu node silinirken çocuğu node'un yerine geçiyor; BST kuralı bozulmuyor, çünkü o çocuğun bütün alt tree'si zaten node'un parent'ına göre doğru tarafta. İki çocuklu node'da ise node'un yerine geçebilecek tek değer, kendisinden büyük en küçük değer: in-order successor, yani sağ alt tree'nin en solundaki node. Onun değeri silinen node'a kopyalanıyor, sonra successor sağ alt tree'den siliniyor. Successor'ın sol çocuğu olamayacağı için bu ikinci silme her zaman durum 1 ya da 2. Simetrik olarak in-order predecessor (sol alt tree'nin en büyüğü) da kullanılabilirdi.

"Bu alt tree'nin yeni root'unu dön" tarzı, parent'a ayrı bir referans tutmadan bütün durumları tek bir method'da çözüyor; serinin linked list yazısındaki sentinel fikrinin tree karşılığı. Testler üç durumu yazının örnek tree'si üzerinde ayrı ayrı doğruluyor ve ardından 5.000 rastgele insert/remove işlemini SortedSet<int> ile karşılaştırıyor:

//         50
//       /    \
//     30      70
//    /  \    /  \
//  20   40  60   80
//            \
//             65
private static BinarySearchTree<int> Sample() => Build(50, 30, 70, 20, 40, 60, 80, 65);

[Fact]
public void Remove_NodeWithTwoChildren_UsesInOrderSuccessor()
{
    BinarySearchTree<int> tree = Sample();

    Assert.True(tree.Remove(50));

    Assert.Equal(60, tree.Root!.Value);
    Assert.Equal(65, tree.Root.Right!.Left!.Value);
    Assert.Equal([20, 30, 40, 60, 65, 70, 80], Traversal.InOrderIterative(tree.Root));
    Assert.True(BstValidator.IsValid(tree.Root));
    Assert.Equal(7, tree.Count);
}

[Fact]
public void RandomOperations_MatchSortedSet()
{
    BinarySearchTree<int> tree = new();
    SortedSet<int> reference = [];
    Random random = new(5);
    for (int i = 0; i < 5_000; i++)
    {
        int value = random.Next(300);
        if (random.Next(3) == 0) Assert.Equal(reference.Remove(value), tree.Remove(value));
        else Assert.Equal(reference.Add(value), tree.Insert(value));
    }

    Assert.Equal(reference, Traversal.InOrderIterative(tree.Root));
    Assert.True(BstValidator.IsValid(tree.Root));
}

50 silinince successor 60 root'a çıkıyor ve 60'ın tek çocuğu 65, 70'in sol çocuğu oluyor; testin ikinci assert'i tam bunu kontrol ediyor.

Traversal: In, Pre, Post ve Level-Order

Bir tree'yi gezmenin dört klasik yolu var ve her birinin farklı bir kullanımı var. In-order (sol, node, sağ) bir BST'nin değerlerini sıralı veriyor. Pre-order (node, sol, sağ) tree'yi kopyalamak ya da serialize etmek için; node'u çocuklarından önce yazdığın için aynı sırayla insert edince aynı tree çıkıyor. Post-order (sol, sağ, node) çocukları node'dan önce işlemek gerektiğinde: klasör boyutu hesaplamak, bir tree'yi aşağıdan yukarı silmek. Level-order seviye seviye gezmek için; queue kullanıyor ve serinin graph yazısındaki BFS'in (Breadth-First Search) tree hâli.

public static List<T> InOrderRecursive<T>(TreeNode<T>? root)
{
    List<T> result = [];
    Visit(root);
    return result;

    void Visit(TreeNode<T>? node)
    {
        if (node is null) return;
        Visit(node.Left);
        result.Add(node.Value);
        Visit(node.Right);
    }
}

public static List<T> InOrderIterative<T>(TreeNode<T>? root)
{
    List<T> result = [];
    Stack<TreeNode<T>> stack = new();
    TreeNode<T>? node = root;
    while (node is not null || stack.Count > 0)
    {
        while (node is not null) // olabildiğince sola in, yolu hatırla
        {
            stack.Push(node);
            node = node.Left;
        }
        node = stack.Pop();
        result.Add(node.Value);
        node = node.Right;
    }
    return result;
}

public static List<T> PostOrder<T>(TreeNode<T>? root)
{
    // çocuklar yer değiştirmiş pre-order (node, sağ, sol), tersten okununca (sol, sağ, node)
    List<T> result = [];
    if (root is null) return result;
    Stack<TreeNode<T>> stack = new([root]);
    while (stack.TryPop(out TreeNode<T>? node))
    {
        result.Add(node.Value);
        if (node.Left is not null) stack.Push(node.Left);
        if (node.Right is not null) stack.Push(node.Right);
    }
    result.Reverse();
    return result;
}

public static List<List<T>> LevelOrder<T>(TreeNode<T>? root)
{
    List<List<T>> levels = [];
    if (root is null) return levels;
    Queue<TreeNode<T>> queue = new([root]);
    while (queue.Count > 0)
    {
        List<T> level = [];
        for (int i = queue.Count; i > 0; i--)
        {
            TreeNode<T> node = queue.Dequeue();
            level.Add(node.Value);
            if (node.Left is not null) queue.Enqueue(node.Left);
            if (node.Right is not null) queue.Enqueue(node.Right);
        }
        levels.Add(level);
    }
    return levels;
}

Iterative in-order, serinin beşinci yazısındaki dönüşümün daha incelikli bir örneği: recursive versiyonda "sol alt tree bitince node'u yaz" bilgisini call stack tutuyor. Iterative versiyonda aynı bilgiyi açık stack'teki node'lar tutuyor; olabildiğince sola inerken yolu push ediyor, sol bitince pop edip yazıyor ve sağa geçiyor. Level-order'daki for (int i = queue.Count; ...) döngüsü, queue'nun o anki boyutunu bir kez okuyup tam bir seviyeyi işliyor; seviyeleri ayrı listelere ayırmanın standart yolu. Sıralar testte tek tek yazılı:

[Fact]
public void Traversals_ReturnExpectedOrders()
{
    BinarySearchTree<int> tree = Sample();

    Assert.Equal([20, 30, 40, 50, 60, 65, 70, 80], Traversal.InOrderRecursive(tree.Root));
    Assert.Equal(Traversal.InOrderRecursive(tree.Root), Traversal.InOrderIterative(tree.Root));
    Assert.Equal([50, 30, 20, 40, 70, 60, 65, 80], Traversal.PreOrder(tree.Root));
    Assert.Equal([20, 40, 30, 65, 60, 80, 70, 50], Traversal.PostOrder(tree.Root));
    Assert.Equal([[50], [30, 70], [20, 40, 60, 80], [65]], Traversal.LevelOrder(tree.Root));
    Assert.Equal(4, tree.Height());
}

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.BinarySearchTreeTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (600ms)

Test run summary: Passed!
  total: 8
  failed: 0
  succeeded: 8

Sıralı Insert ve Dejenere Tree

Açılıştaki soruya dönelim. 1, 2, 3, ... sırasıyla insert edilen her değer bir öncekinden büyük, yani hep sağa ekleniyor. Sonuç, her node'un yalnızca sağ çocuğu olan bir tree; aslında bir linked list. Test bunu ölçüyor:

[Fact]
public void SortedInserts_ProduceDegenerateTree()
{
    BinarySearchTree<int> sorted = Build([.. Enumerable.Range(1, 1_000)]);
    Random random = new(3);
    BinarySearchTree<int> shuffled = Build([.. Enumerable.Range(1, 1_000).OrderBy(_ => random.Next())]);

    Assert.Equal(1_000, sorted.Height());
    Assert.InRange(shuffled.Height(), 10, 30);
}

Aynı 1.000 değer: sıralı sırayla yükseklik 1.000, rastgele sırayla 10 ile 30 arası. Rastgele insert edilen bir BST'nin beklenen yüksekliği O(log n), ama dengeli değil; en iyi durumdaki log₂ 1.000 ≈ 10'un birkaç katı. Benchmark aynı 1.000 aramayı iki tree'de yapıyor:

BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
  [Host] : .NET 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a

| Method            | N     | Mean        | Ratio  | Allocated |
|------------------ |------ |------------:|-------:|----------:|
| RandomInsertOrder | 1000  |    12.09 us |   1.00 |         - |
| SortedInsertOrder | 1000  |   327.69 us |  27.10 |         - |
|                   |       |             |        |           |
| RandomInsertOrder | 10000 |    18.41 us |   1.00 |         - |
| SortedInsertOrder | 10000 | 4,071.32 us | 221.23 |         - |

10.000 ID'de rastgele sırayla kurulan tree'de 1.000 arama 18 µs, sıralı kurulan tree'de 4,1 ms: 221 kat. N 10 kat büyüyünce rastgele tree'nin süresi yalnızca yüzde 50 artıyor (log n büyüme), dejenere tree'ninki 12 kat (n büyüme). Aynı veri, aynı kod; fark yalnızca insert sırası. Ölçüm makinede başka işler çalışırken alındı.

Dejenere tree'nin ikinci bir bedeli daha var: recursive traversal'lar ve recursive Remove derinlik kadar call stack frame'i kullanıyor. 1 milyon sıralı ID ile kurulmuş bir tree'de InOrderRecursive çağırmak, serinin beşinci yazısındaki stack overflow'un ta kendisi. Bu yüzden Insert, Contains ve Height'ı iterative yazdık. Asıl çözüm tree'yi dengede tutmak: AVL (Adelson-Velsky ve Landis) ve red-black tree'ler her insert ve delete'ten sonra rotation'larla yüksekliği O(log n)'de tutuyor. .NET'in SortedSet<T> ve SortedDictionary<TKey, TValue>'i red-black tree; serinin bir sonraki yazısının konusu.

Gerçek Senaryo: Düz Kategori Tablosundan Tree

Production'da en sık kurduğun tree bir BST değil, veritabanındaki düz bir tablodan gelen hiyerarşi. Bookstore'un kategorileri Categories(Id, ParentId, Name) tablosunda; root kategorilerin ParentId'si null. Admin paneli ve mağaza menüsü bu satırları iç içe bir JSON (JavaScript Object Notation) tree olarak istiyor.

İlk akla gelen çözüm her kategori için bütün satırları gezip çocuklarını bulmak; n kategori için n² karşılaştırma. Doğru çözüm bir Dictionary ile iki geçiş: önce her satır için bir node oluştur ve Id'ye göre sakla, sonra her node'u parent'ının çocuk listesine ekle. Satırların sırası önemsiz; çocuk parent'tan önce gelse bile çalışıyor.

namespace Algorithms.Trees;

// Categories tablosunun bir satırı
public sealed record CategoryRow(int Id, int? ParentId, string Name);

public sealed class CategoryNode(int id, string name)
{
    public int Id { get; } = id;
    public string Name { get; } = name;
    public List<CategoryNode> Children { get; } = [];
}

public sealed class InvalidCategoryTreeException(string message) : Exception(message);

public static class CategoryTreeBuilder
{
    // O(n): bir geçişte node'ları oluştur, bir geçişte her node'u parent'ına bağla
    public static List<CategoryNode> Build(IReadOnlyList<CategoryRow> rows)
    {
        Dictionary<int, CategoryNode> byId = new(rows.Count);
        foreach (CategoryRow row in rows)
            byId.Add(row.Id, new CategoryNode(row.Id, row.Name));

        List<CategoryNode> roots = [];
        foreach (CategoryRow row in rows)
        {
            CategoryNode node = byId[row.Id];
            if (row.ParentId is null)
                roots.Add(node);
            else if (byId.TryGetValue(row.ParentId.Value, out CategoryNode? parent))
                parent.Children.Add(node);
            else
                throw new InvalidCategoryTreeException($"Category {row.Id} points to missing parent {row.ParentId}.");
        }

        // her node bir root'tan ulaşılabilir olmalı; ParentId cycle'ındaki node'lar değil
        int reachable = 0;
        Stack<CategoryNode> pending = new(roots);
        while (pending.TryPop(out CategoryNode? node))
        {
            reachable++;
            foreach (CategoryNode child in node.Children) pending.Push(child);
        }
        if (reachable != rows.Count)
        {
            int[] stuck = [.. rows.Select(r => r.Id).Except(Reachable(roots))];
            throw new InvalidCategoryTreeException($"ParentId cycle among categories: {string.Join(", ", stuck)}.");
        }
        return roots;
    }
}

Son blok, verinin kendisine güvenmemenin karşılığı. Bir admin yanlışlıkla 7'nin parent'ını 8, 8'in parent'ını 7 yaparsa bu iki kategori hiçbir root'a bağlı olmayan bir cycle oluşturuyor. Recursive bir menü çizimi o cycle'a girerse ya sonsuza kadar döner ya da stack overflow ile ölür. Root'lardan iterative bir gezinti ile ulaşılan node sayısını saymak cycle'ı O(n)'de yakalıyor. Reachable, aynı gezintiyi yield return ile Id'leri dönecek şekilde yapan küçük bir yardımcı.

[Fact]
public void Build_ParentIdCycle_Throws()
{
    CategoryRow[] rows = [new(1, null, "Books"), new(7, 8, "Loop A"), new(8, 7, "Loop B")];

    InvalidCategoryTreeException ex = Assert.Throws<InvalidCategoryTreeException>(() => CategoryTreeBuilder.Build(rows));
    Assert.Equal("ParentId cycle among categories: 7, 8.", ex.Message);
}

Bunu bir ASP.NET Core minimal API (Application Programming Interface) endpoint'inden vermek birkaç satır. Repository tek bir düz sorgu çalıştırıyor (veritabanında recursive sorgu yok), tree bellekte kuruluyor:

using Algorithms.Trees;

WebApplicationBuilder builder = WebApplication.CreateBuilder(args);
builder.Services.AddSingleton<ICategoryRepository, InMemoryCategoryRepository>();
WebApplication app = builder.Build();

app.MapGet("/api/categories/tree", async (ICategoryRepository repository, CancellationToken ct) =>
{
    IReadOnlyList<CategoryRow> rows = await repository.GetAllAsync(ct); // tek bir düz sorgu, SQL'de recursion yok
    try
    {
        return Results.Ok(CategoryTreeBuilder.Build(rows));
    }
    catch (InvalidCategoryTreeException ex)
    {
        return Results.Problem(ex.Message, statusCode: StatusCodes.Status500InternalServerError);
    }
});

app.Run();

$ curl -i http://127.0.0.1:5311/api/categories/tree
HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Date: Sun, 08 Nov 2026 09:06:50 GMT
Server: Kestrel
Transfer-Encoding: chunked

[{"id":1,"name":"Books","children":[{"id":2,"name":"Fiction","children":[{"id":4,"name":"Science Fiction","children":[]}]},{"id":3,"name":"Non-Fiction","children":[{"id":5,"name":"Software","children":[]}]}]},{"id":6,"name":"Gifts","children":[]}]

Örnekteki InMemoryCategoryRepository sabit altı satır dönüyor; gerçek uygulamada bu, Entity Framework Core (EF Core) ya da Dapper ile tek bir SELECT Id, ParentId, Name FROM Categories. Ortaya çıkan JSON'un her node'u aynı şekle sahip (id, name, children); Angular tarafında kendini çocukları için tekrar çağıran recursive bir tree component'ine doğrudan uyuyor. Endpoint tasarımının ayrıntıları ASP.NET Core Web API serisinin ".NET 6 ile ASP.NET Core Minimal API: MapGet, MapPost ve Controller Karşılaştırması" yazısında. Dictionary ile kurulumu n² versiyonla karşılaştıran benchmark:

| Method     | N     | Mean         | Ratio | Allocated  |
|----------- |------ |-------------:|------:|-----------:|
| Dictionary | 1000  |     30.58 us |  1.00 |  132.38 KB |
| Quadratic  | 1000  |    391.34 us | 12.81 |  101.79 KB |
|            |       |              |       |            |
| Dictionary | 10000 |    733.92 us |  1.00 | 1287.22 KB |
| Quadratic  | 10000 | 72,151.19 us | 98.49 | 1010.08 KB |

1.000 kategoride fark 13 kat, 10.000'de 98 kat: Dictionary'li versiyon 0,73 ms, n² versiyon 72 ms. Kategori sayısı 10 kat büyüdü, n² versiyonun süresi 184 kat büyüdü. Dictionary'nin bedeli yaklaşık yüzde 27 fazla bellek; her istekte bir kez kurulan bir tree için ihmal edilebilir. Ölçüm makinede başka işler çalışırken alındı. Kategori tablosu sık değişmiyorsa kurulan tree'yi cache'lemek her istekteki bu maliyeti de ortadan kaldırır.

Üretimde Dikkat

Kendi BST'ni production'a koyma; dengesiz bir BST'nin performansı tamamen insert sırasına bağlı ve insert sırası genelde senin kontrolünde değil. Sıralı bir set ya da sözlük gerekiyorsa SortedSet<T> ve SortedDictionary<TKey, TValue>; ikisi de dengeli ve en kötü durumda O(log n). Seçim C# Koleksiyonlar serisinin "C# Sıralı Collection'lar: SortedList, SortedDictionary, SortedSet ve IComparer" yazısında.

Hiyerarşik veride derinliğe bir üst sınır koy. Kategori menüsü 5 seviyeyi geçmemeli; import sırasında 20'nci seviyeyi gören bir kayıt reddedilmeli. Bu, hem kullanıcı deneyimi kararı hem de recursive kodun call stack'ini koruyan bir güvenlik sınırı.

Tree'yi veritabanında mı uygulamada mı kuracağına bilinçli karar ver. Bütün tree birkaç bin satırsa tek sorgu + Dictionary en basit ve en hızlı yol. Tablo büyükse ve yalnız bir alt tree gerekiyorsa veritabanının recursive CTE (Common Table Expression) desteği ya da materialized path gibi modeller daha uygun; bunlar EF Core ve SQL (Structured Query Language) serilerinin konusu.

Sık Düşülen Tuzaklar

BST doğrulamasında yalnız komşulara bakmak. Her node'u sadece doğrudan çocuklarıyla karşılaştıran bir validator bozuk tree'leri kabul ediyor:

// yanlış: her node'u yalnızca doğrudan çocuklarıyla karşılaştırır
public static bool IsValidNaive(TreeNode<int>? node) =>
    node is null ||
    (node.Left is null || node.Left.Value < node.Value) &&
    (node.Right is null || node.Right.Value > node.Value) &&
    IsValidNaive(node.Left) && IsValidNaive(node.Right);

// doğru: her node, bütün atalarından miras aldığı (min, max) penceresine sığmalı
public static bool IsValid(TreeNode<int>? node, long min = long.MinValue, long max = long.MaxValue) =>
    node is null ||
    node.Value > min && node.Value < max &&
    IsValid(node.Left, min, node.Value) &&
    IsValid(node.Right, node.Value, max);

[Fact]
public void NaiveValidator_AcceptsInvalidTree()
{
    // 50 -> sol 30 -> sağ 60: 60, 50'nin SOL alt tree'sinde, bu geçersiz
    TreeNode<int> root = new(50) { Left = new TreeNode<int>(30) { Right = new TreeNode<int>(60) }, Right = new TreeNode<int>(70) };

    Assert.True(BstValidator.IsValidNaive(root));
    Assert.False(BstValidator.IsValid(root));
}

60, 30'dan büyük olduğu için 30'un sağında durabilir gibi görünüyor ama 50'nin sol alt tree'sinde olduğu için 50'den küçük olmak zorunda. Doğru validator her node'a atalarından gelen bir alt ve üst sınır taşıyor. Sınırları long tutmamızın nedeni, int.MinValue ve int.MaxValue değerlerini de doğru doğrulayabilmek.

Cycle'lı ParentId verisi. Veritabanı foreign key'i bir cycle'ı engellemiyor; tree kuran kod bunu kendisi kontrol etmeli, yoksa recursive menü çizimi sonsuz döngüye girer.

Recursive traversal'ı dejenere tree'de çalıştırmak. Test verisinde dengeli görünen tree, sıralı import edilen production verisinde derinliği n olan bir zincire dönüşür. Derinliği veriye bağlı her traversal'ı iterative yaz ya da derinliği sınırla.

Delete'te successor'ı silmeyi unutmak. Successor'ın değerini kopyalayıp onu sağ alt tree'den silmezsen aynı değer tree'de iki kez kalır ve Count yanlış olur. SortedSet ile karşılaştıran rastgele test bu hatayı ilk birkaç yüz adımda yakalıyor.

Küçük Bir Deneme

★☆☆ BinarySearchTree<T>'e Min(), Max() ve Floor(T value) (value'dan küçük ya da eşit en büyük değer) ekle. Hepsi O(h); Floor'u serinin binary search yazısındaki upper bound ile karşılaştır.

★★☆ Remove'u iterative yaz: silinecek node'u parent'ıyla birlikte bul, üç durumu parent'ın Left ya da Right'ını güncelleyerek çöz. Rastgele testi yeni versiyonla da çalıştır.

★★★ Sıralı bir array'den dengeli bir BST kuran BuildBalanced(int[] sorted) yaz: ortadaki eleman root, sol ve sağ yarılar recursive alt tree'ler. 1.000.000 sıralı ID için yüksekliği ne oluyor ve recursion derinliği neden sorun değil?

Dejenere tree sorununu gördük; çözümü tree'yi her değişiklikten sonra yeniden dengelemek. Bir sonraki yazıda AVL'nin rotation'larına, .NET'in SortedSet'inin altındaki red-black tree'nin kurallarına ve veritabanı index'lerinin neden binary tree değil de yüksek fanout'lu B+tree olduğuna bakıyoruz.