İkili Arama Ağacı Binary Search Tree (BST)

BST oluşturma, eleman ekleme-arama-silme (yaprak, tek çocuk, iki çocuk), min/max bulma, BST doğrulama — adım adım görseller, karşılaştırma tabloları ve C kodu.

🗂️ Veri Yapıları 📅 21 February 2026 👁️ 2 görüntülenme

BST Nedir?

İkili Arama Ağacı (BST), her düğüm için sol alt ağaçtaki tüm değerler küçük, sağ alt ağaçtaki tüm değerler büyük kuralını sağlayan özel bir ikili ağaçtır. Bu basit kural sayesinde arama, ekleme ve silme operasyonları ağacın yüksekliğine bağlı olarak O(h)'de çalışır — dengeli bir BST'de bu O(log n) demektir.

BST Kuralı (BST Property): Her düğüm x için:
• Sol alt ağaçtaki tüm değerler < x.data
• Sağ alt ağaçtaki tüm değerler > x.data
• Sol ve sağ alt ağaçlar da birer BST'dir (özyinelemeli tanım)

Not: Bu seride yinelenen (duplicate) anahtarlar kabul edilmez.

Genel İkili Ağaç vs BST

✗ BST Değil (kural ihlali)

✓ Geçerli BST

Yapı ve Referans BST

BST'nin yapı tanımı sıradan ikili ağaçla aynıdır — fark kurallarda, yapıda değil:

bst.c — yapı
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int           data;
    struct Node*  left;
    struct Node*  right;
} Node;

Node* yeniDugum(int data) {
    Node* n = (Node*)malloc(sizeof(Node));
    if (!n) { perror("malloc"); exit(1); }
    n->data  = data;
    n->left  = NULL;
    n->right = NULL;
    return n;
}

Bu bölüm boyunca şu BST'yi kullanacağız (ekleme sırası: 50, 30, 70, 20, 40, 60, 80):

Referans BST — Dengeli, 7 Düğüm

Inorder: 20 30 40 50 60 70 80 — sıralı! ✓

Eleman Ekleme (Insert)

BST'ye ekleme her zaman bir yaprak pozisyonuna yapılır. Yeni değer kökten başlayarak karşılaştırılır: küçükse sola, büyükse sağa gidilir. NULL'a ulaşıldığında yeni düğüm o pozisyona eklenir.

Ekleme algoritması (özyinelemeli):
1. Düğüm NULL ise → yeni düğüm oluştur ve döndür.
2. Değer < düğüm.data ise → sol alt ağaca ekle.
3. Değer > düğüm.data ise → sağ alt ağaca ekle.
4. Eşitse → yok say (duplicate kabul etmiyoruz).
5. Güncellenmiş düğümü döndür.

Adım Adım — BST'yi Sıfırdan Kurma

Ekleme sırası: 50, 30, 70, 20, 40, 60, 80

7 Ekleme Adımı — BST Büyümesi

① +50

kök

② +30

30<50 → sol

③ +70

70>50 → sağ

④ +20

20<50→sol, 20<30→sol

⑤⑥⑦ Kalan eklemeler:

+40: 40<50→sol, 40>30→sağ → 30'un sağ çocuğu

+60: 60>50→sağ, 60<70→sol → 70'in sol çocuğu

+80: 80>50→sağ, 80>70→sağ → 70'in sağ çocuğu

Sonuç: Referans BST oluştu ✓

Ekleme Kodu

bstEkle() — özyinelemeli
Node* bstEkle(Node* node, int deger) {
    if (!node)
        return yeniDugum(deger);    // NULL → yeni yaprak

    if (deger < node->data)
        node->left  = bstEkle(node->left, deger);
    else if (deger > node->data)
        node->right = bstEkle(node->right, deger);
    // else: eşit → yok say (duplicate)

    return node;
}

/* Kullanım:
   Node* root = NULL;
   root = bstEkle(root, 50);
   root = bstEkle(root, 30);
   root = bstEkle(root, 70);
   ...
*/

Ekleme Sırası Ağacın Şeklini Belirler

Aynı Veri, Farklı Sıra → Farklı Ağaç

Sıra: 50,30,70,20,40,60,80

h=2 — dengeli ✓

Sıra: 20,30,40,50,60,70,80

h=6 — dejenere ✗

Sıralı veri eklemek BST'yi bağlı listeye dönüştürür → arama O(n). Çözüm: AVL/Red-Black ile dengeleme.

Eleman Arama (Search)

BST'de arama, ikili arama (binary search) mantığıyla çalışır: her karşılaştırmada aday küme yarıya iner. Kökten başla, aranan değer küçükse sola, büyükse sağa git. Eşleşme bulursan döndür, NULL'a ulaşırsan bulunamadı.

Arama algoritması:
1. Düğüm NULL ise → bulunamadı (return NULL).
2. Değer == düğüm.data → bulundu! (return düğüm).
3. Değer < düğüm.data → sol alt ağaçta ara.
4. Değer > düğüm.data → sağ alt ağaçta ara.

Arama Görseli — Başarılı ve Başarısız

Arama: 40 (Bulundu ✓) ve 35 (Bulunamadı ✗)

search(40) → 3 adımda bulundu

search(35) → NULL'a ulaştı

Her adımda ağacın yarısı eleniyor → dengeli BST'de O(log n)

Arama Kodu — Özyinelemeli ve İteratif

bstAra() — iki versiyon
/* ── Özyinelemeli arama ── */
Node* bstAra(Node* node, int deger) {
    if (!node || node->data == deger)
        return node;

    if (deger < node->data)
        return bstAra(node->left, deger);
    else
        return bstAra(node->right, deger);
}

/* ── İteratif arama (stack overflow riski yok) ── */
Node* bstAraIteratif(Node* node, int deger) {
    while (node && node->data != deger) {
        if (deger < node->data)
            node = node->left;
        else
            node = node->right;
    }
    return node;  // NULL veya bulunan düğüm
}

/* Kullanım:
   Node* sonuc = bstAra(root, 40);
   if (sonuc) printf("Bulundu: %d\n", sonuc->data);
   else       printf("Bulunamadı!\n");
*/

Minimum ve Maksimum Değer Bulma

BST kuralı gereği minimum değer her zaman en soldaki yapraktadır (sürekli sola git), maksimum değer her zaman en sağdaki yapraktadır (sürekli sağa git). Hiçbir karşılaştırma gerekmez — sadece yön bilgisi yeterli.

Minimum ve Maksimum — Tek Yönlü Yürüyüş

Min: 50→30→20 (sürekli sol) | Max: 50→70→80 (sürekli sağ) | Her ikisi O(h)

bstMin() / bstMax()
/* ── En küçük: sürekli sola git ── */
Node* bstMin(Node* node) {
    if (!node) return NULL;
    while (node->left)
        node = node->left;
    return node;
}

/* ── En büyük: sürekli sağa git ── */
Node* bstMax(Node* node) {
    if (!node) return NULL;
    while (node->right)
        node = node->right;
    return node;
}
// bstMin(root)->data = 20
// bstMax(root)->data = 80
// Karmaşıklık: O(h) — yükseklik kadar adım

Inorder Successor (Sıralı Ardıl): Bir düğümün inorder'daki bir sonraki elemanı = sağ alt ağacın minimumu. Örneğin 50'nin ardılı → sağ alt ağaç(70)'ın minimumu = 60. Bu kavram silme operasyonunda kritik rol oynar.

Eleman Silme (Delete)

BST'de silme en karmaşık operasyondur çünkü silinen düğümün BST kuralını bozmaması gerekir. Silinecek düğümün çocuk sayısına göre 3 farklı durum vardır:

Durum 1 — Yaprak

Çocuğu yok. Basitçe kaldır.

Durum 2 — Tek Çocuk

Düğümü çocuğuyla değiştir.

Durum 3 — İki Çocuk

Inorder successor ile değiştir, sonra successor'ı sil.

Durum 1 — Yaprak Düğüm Silme: delete(20)

Yaprak Silme — En Basit Durum

Önce:

→

Sonra: 20 kaldırıldı, free()

İşlem: ebeveynin (30) sol pointer'ını NULL yap → free(20). BST kuralı korundu ✓

Durum 2 — Tek Çocuklu Düğüm Silme: delete(30)

Silinecek düğümün tek çocuğu var → düğümü çocuğuyla değiştir. Çocuk, düğümün pozisyonunu devralır.

Tek Çocuklu Silme — Çocuk Yukarı Çıkar

Önce: (20 zaten silinmiş)

→

Sonra: 40, 30'un yerini aldı

İşlem: 30'un tek çocuğu (40) → 50'nin sol pointer'ına bağla → free(30). Kural: 40<50 ✓

Durum 3 — İki Çocuklu Düğüm Silme: delete(50)

En karmaşık durum. Silinecek düğümün iki çocuğu var — doğrudan kaldırmak ağacı bozar. Strateji: inorder successor (sıralı ardıl = sağ alt ağacın minimumu) ile veriyi değiştir, sonra successor'ı sil (ki o yaprak veya tek çocuklu olacak).

İki çocuklu silme adımları:
1. Sağ alt ağacın minimumunu bul → inorder successor
2. Silinecek düğümün verisini successor'ın verisiyle değiştir.
3. Successor'ı sağ alt ağaçtan sil (Durum 1 veya 2'ye düşer).

Alternatif: Inorder predecessor (sol alt ağacın maksimumu) da kullanılabilir.

delete(50) — Kök Silme (İki Çocuklu) — 3 Adım

① Inorder successor bul: 50'nin sağ alt ağacı (70)'ın minimumu = 60

② Swap: 50'nin verisini 60 ile değiştir

Artık 60'ı silmek gerek — ama 60 yaprak! → Durum 1'e düştü

③ Successor'ı sil (yaprak — Durum 1) → Sonuç

Inorder: 20 30 40 60 70 80 — hâlâ sıralı ✓ BST kuralı korundu ✓

Silme Kodu

bstSil() — özyinelemeli, 3 durum
Node* bstSil(Node* node, int deger) {
    if (!node) return NULL;  // bulunamadı

    // Arama: sola veya sağa in
    if (deger < node->data) {
        node->left = bstSil(node->left, deger);
    } else if (deger > node->data) {
        node->right = bstSil(node->right, deger);
    } else {
        // BULUNDU — 3 durum:

        /* Durum 1: Yaprak (çocuk yok)
           Durum 2a: Sadece sağ çocuk var */
        if (!node->left) {
            Node* sag = node->right;
            free(node);
            return sag;  // NULL (yaprak) veya sağ çocuk
        }

        /* Durum 2b: Sadece sol çocuk var */
        if (!node->right) {
            Node* sol = node->left;
            free(node);
            return sol;
        }

        /* Durum 3: İki çocuk var
           → Inorder successor = sağ alt ağacın minimumu */
        Node* successor = bstMin(node->right);
        node->data = successor->data;   // veriyi kopyala
        // Successor'ı sağ alt ağaçtan sil (Durum 1 veya 2'ye düşer)
        node->right = bstSil(node->right, successor->data);
    }
    return node;
}
// Karmaşıklık: O(h) — arama O(h) + successor bulma O(h)

Kodun zarafeti: Durum 1 (yaprak) ve Durum 2 (tek çocuk) aynı if (!node->left) bloğunda birleştirilmiş. Yaprak için node->right zaten NULL döner, tek sağ çocuklu için gerçek çocuğu döner. Sol çocuklu durum da simetrik. İki çocuklu Durum 3 ise successor bulup kendini recursive çağırarak Durum 1/2'ye indirger.

BST Doğrulama (Validation)

Bir ikili ağacın gerçekten BST olup olmadığını nasıl doğrularız? Bu soru mülakatlarda en sık sorulan ağaç problemidir — ve en yaygın hata, sadece her düğümde "sol < kök < sağ" kontrolü yapmaktır.

Yanlış Yaklaşım — Sadece Yerel Kontrol

Bu Ağaç BST mi? — Tuzak!

Yerel kontrol: her düğümde sol<kök<sağ ✓ — ama ağaç BST DEĞİL!

60, düğüm 30'un sağ çocuğu olarak yerel kuralı geçiyor (60>30 ✓).
Ama 60 aynı zamanda 50'nin sol alt ağacında — ve 60>50 → BST kuralı ihlali!

Yaygın hata: Sadece node->left->data < node->data < node->right->data kontrolü yetersizdir. BST kuralı tüm sol alt ağaç < kök < tüm sağ alt ağaç der — sadece doğrudan çocuklar değil, torunlar da dahil.

Doğru Yaklaşım — Min/Max Aralık Takibi

Her düğümün geçerli olabileceği bir aralık (range) vardır. Kök: (-∞, +∞). Sola indiğimizde üst sınır güncellenir (ebeveynin değeri), sağa indiğimizde alt sınır güncellenir. Düğüm bu aralığın dışındaysa BST değildir.

Aralık algoritması:
isBST(node, min, max)
1. NULL ise → true (boş ağaç BST'dir).
2. node.data ≤ min veya node.data ≥ max ise → false.
3. Sol alt ağaç: isBST(left, min, node.data) — üst sınır daralır.
4. Sağ alt ağaç: isBST(right, node.data, max) — alt sınır daralır.
5. Her ikisi true ise → true.

Geçerli BST — Aralık Takibi

Referans BST — Her Düğümde Geçerli Aralık

Tüm düğümler aralıklarında → geçerli BST ✓

Geçersiz Ağaç — Hata Yakalama

Tuzaklı Ağaçta Aralık Kontrolü

60, aralığı (30, 50) olmalı — ama 60 ≥ 50 → BST değil! Aralık kontrolü hatayı yakaladı.

Doğrulama Kodu

isBST() — min/max aralık yaklaşımı
#include <limits.h>   // INT_MIN, INT_MAX
#include <stdbool.h>

bool isBSTHelper(Node* node, int min, int max) {
    if (!node) return true;  // boş ağaç → BST

    // Aralık kontrolü: min < node->data < max olmalı
    if (node->data <= min || node->data >= max)
        return false;

    // Sol: üst sınır = node->data
    // Sağ: alt sınır = node->data
    return isBSTHelper(node->left,  min, node->data)
        && isBSTHelper(node->right, node->data, max);
}

bool isBST(Node* root) {
    return isBSTHelper(root, INT_MIN, INT_MAX);
}

/* Kullanım:
   if (isBST(root)) printf("Geçerli BST ✓\n");
   else             printf("BST değil ✗\n");
*/

Alternatif Yöntem — Inorder Kontrolü

BST'nin inorder dolaşması sıralı (ascending) dizi üretir. Eğer inorder sırasında bir önceki eleman mevcut elemandan büyük veya eşitse → BST değildir.

isBSTInorder() — önceki elemanla karşılaştır
bool isBSTInorder(Node* node, int* prev) {
    if (!node) return true;

    // Sol alt ağaç
    if (!isBSTInorder(node->left, prev))
        return false;

    // Mevcut düğüm: öncekinden büyük olmalı
    if (node->data <= *prev)
        return false;
    *prev = node->data;

    // Sağ alt ağaç
    return isBSTInorder(node->right, prev);
}

/* Kullanım:
   int prev = INT_MIN;
   if (isBSTInorder(root, &prev))
       printf("Geçerli BST ✓\n");
*/

Min/Max Aralık

✓ Sezgisel: her düğümün aralığı görünür
✓ Erken çıkış: ilk ihlalde false
✓ Mülakatlarda favori yöntem
O(n) zaman, O(h) alan

Inorder Kontrolü

✓ Zarif: "sıralı mı?" sorusuna indirgeme
✓ Tek değişken (prev) yeterli
✗ Tüm sol alt ağaç bitmeden çıkamaz
O(n) zaman, O(h) alan

Tam Demo Program

main() — tüm BST operasyonları
void inorder(Node* n) {
    if (!n) return;
    inorder(n->left);
    printf("%d ", n->data);
    inorder(n->right);
}

int main() {
    Node* root = NULL;
    int degerler[] = {50, 30, 70, 20, 40, 60, 80};

    // ── Ağacı kur ──
    printf("=== BST Demo ===\n\n");
    for (int i = 0; i < 7; i++) {
        root = bstEkle(root, degerler[i]);
        printf("insert(%d) → inorder: ", degerler[i]);
        inorder(root);
        printf("\n");
    }

    // ── Arama ──
    printf("\n--- Arama ---\n");
    Node* s1 = bstAra(root, 40);
    printf("search(40): %s\n", s1 ? "Bulundu ✓" : "Yok");
    Node* s2 = bstAra(root, 35);
    printf("search(35): %s\n", s2 ? "Bulundu" : "Bulunamadı ✗");

    // ── Min / Max ──
    printf("\n--- Min / Max ---\n");
    printf("Minimum: %d\n", bstMin(root)->data);
    printf("Maksimum: %d\n", bstMax(root)->data);

    // ── BST Doğrulama ──
    printf("\n--- Doğrulama ---\n");
    printf("BST geçerli mi? %s\n", isBST(root) ? "Evet ✓" : "Hayır ✗");

    // ── Silme: 3 durum ──
    printf("\n--- Silme ---\n");
    root = bstSil(root, 20);
    printf("delete(20) yaprak:     "); inorder(root); printf("\n");

    root = bstSil(root, 30);
    printf("delete(30) tek çocuk:  "); inorder(root); printf("\n");

    root = bstSil(root, 50);
    printf("delete(50) iki çocuk:  "); inorder(root); printf("\n");

    printf("\nBST hâlâ geçerli mi? %s\n", isBST(root) ? "Evet ✓" : "Hayır ✗");

    return 0;
}

çıktı
=== BST Demo ===

insert(50) → inorder: 50
insert(30) → inorder: 30 50
insert(70) → inorder: 30 50 70
insert(20) → inorder: 20 30 50 70
insert(40) → inorder: 20 30 40 50 70
insert(60) → inorder: 20 30 40 50 60 70
insert(80) → inorder: 20 30 40 50 60 70 80

--- Arama ---
search(40): Bulundu ✓
search(35): Bulunamadı ✗

--- Min / Max ---
Minimum: 20
Maksimum: 80

--- Doğrulama ---
BST geçerli mi? Evet ✓

--- Silme ---
delete(20) yaprak:     30 40 50 60 70 80
delete(30) tek çocuk:  40 50 60 70 80
delete(50) iki çocuk:  40 60 70 80

BST hâlâ geçerli mi? Evet ✓

Karmaşıklık Analizi

Operasyon	Ortalama	En İyi	En Kötü (dejenere)
Ekleme (insert)	O(log n)	O(1) — boş ağaç	O(n)
Arama (search)	O(log n)	O(1) — kökte	O(n)
Silme (delete)	O(log n)	O(1) — yaprak	O(n)
Min / Max	O(log n)	O(1) — tek düğüm	O(n)
Doğrulama (isBST)	O(n)	O(1) — boş	O(n)
Inorder (sıralı çıktı)	O(n)	O(n)	O(n)

h = O(log n) vs h = O(n): Tüm operasyonlar O(h)'dir. Dengeli BST'de h = ⌊log₂ n⌋ → O(log n). Ama sıralı veri eklenirse h = n-1 → O(n). Bu BST'nin temel zayıflığıdır. Çözüm: kendini dengeleyen ağaçlar (AVL, Red-Black).

BST vs Diğer Yapılar

Operasyon	Sıralı Dizi	Bağlı Liste	BST (dengeli)
Arama	O(log n) — ikili arama	O(n)	O(log n)
Ekleme	O(n) — kaydırma	O(1) — başa	O(log n)
Silme	O(n) — kaydırma	O(n) — arama	O(log n)
Min / Max	O(1) — ilk/son	O(n)	O(log n)
Sıralı çıktı	O(n) — zaten sıralı	O(n log n) — sort	O(n) — inorder

BST'nin gücü: Sıralı dizi arama için iyi ama ekleme/silme yavaş (O(n) kaydırma). Bağlı liste ekleme için hızlı ama arama yavaş (O(n)). BST her ikisini birleştirir: hem arama hem ekleme/silme O(log n) — ama dengeye bağlı.

Sonuç

BST, "sol < kök < sağ" kuralıyla sıralı veri saklama ve hızlı arama imkânı sunar. Ekleme her zaman yaprak pozisyonuna yapılır, arama ikili arama mantığıyla çalışır, silme ise 3 durum (yaprak, tek çocuk, iki çocuk) gerektirir. Min/max bulma tek yönlü yürüyüştür, BST doğrulama ise min/max aralık takibi ile yapılır.

BST'nin Aşil topuğu dengesizliktir: sıralı veri eklenmesi ağacı bağlı listeye dönüştürür ve O(n) performansa düşürür. Bir sonraki bölümde bu sorunu çözen AVL ağacı'nı tanıyacağız: her eklemede/silmede otomatik dengeleme (rotation) ile h = O(log n) garantisi.

Bölüm 6.3 özeti: BST kuralı: sol alt ağaç < kök < sağ alt ağaç (tüm torunlar dahil). Ekleme: sola/sağa inerek yaprak pozisyonuna O(h). Arama: ikili arama mantığı O(h). Silme: 3 durum — yaprak (kaldır), tek çocuk (çocukla değiştir), iki çocuk (inorder successor ile swap). Min = en sol, Max = en sağ. Doğrulama: min/max aralık takibi veya inorder sıra kontrolü. Tüm operasyonlar O(h) — dengeli ise O(log n), dejenere ise O(n). Çözüm → AVL.

← Veri Yapıları