Kırmızı-Siyah Ağaç Red-Black Tree

Kırmızı-Siyah ağaç 5 renklendirme kuralı, ekleme düzeltmeleri (3 durum), silme düzeltmeleri (4 durum) — adım adım görseller, akış diyagramları ve C kodu.

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

Neden Kırmızı-Siyah Ağaç?

AVL ağacı sıkı denge tutar — her düğümde |BF| ≤ 1. Bu, arama için harikadır ama her ekleme/silmede birden fazla rotasyon gerektirebilir. Kırmızı-Siyah ağaç daha gevşek bir denge tanımı kullanır: en uzun yol, en kısa yolun en fazla 2 katı olabilir. Bu gevşeklik daha az rotasyon → daha hızlı yazma operasyonları sağlar.

Nerelerde kullanılır?

Linux çekirdeği — CFS zamanlayıcı, bellek yönetimi
Java — TreeMap, TreeSet
C++ — std::map, std::set
.NET — SortedDictionary

AVL'den farkı

AVL: sıkı denge, arama hızlı, rotasyon çok
RB: gevşek denge, rotasyon az, yazma hızlı
Ekleme: RB max 2 rotasyon, AVL max 2
Silme: RB max 3 rotasyon, AVL max O(log n)

5 Renklendirme Kuralı

Kırmızı-Siyah ağaç, her düğümün kırmızı veya siyah olduğu bir BST'dir. Aşağıdaki 5 kural aynı anda sağlandığında ağaç dengeli kalır:

1

Her düğüm ya kırmızı ya da siyah renktedir.

2

Kök (root) her zaman siyahtır.

3

Tüm yapraklar (NIL düğümleri) siyahtır. (Gerçek veri taşımayan sentinel düğümler.)

4

Kırmızı düğümün çocukları siyah olmalıdır.
(Art arda iki kırmızı düğüm yasak — "no double-red" kuralı.)

5

Herhangi bir düğümden, onun altındaki tüm NIL'lere giden yollardaki siyah düğüm sayısı aynıdır.
(Bu sayıya siyah yükseklik / black-height denir.)

En kritik 2 kural: Kural 4 (art arda kırmızı yasak) ve Kural 5 (siyah yükseklik eşitliği) birlikte çalışır. Kural 5 siyah düğüm sayısını sabitler; Kural 4 kırmızı düğümleri serpiştirilmeye zorlar → en uzun yol (siyah-kırmızı-siyah-kırmızı...) en kısa yolun (hep siyah) en fazla 2 katı olur.

Geçerli Kırmızı-Siyah Ağaç Örneği

7 Düğümlü RB Ağaç — Black-Height = 2

Siyah Yükseklik (Black-Height): Bir düğümden herhangi bir NIL'e giden yoldaki siyah düğüm sayısı (düğümün kendisi hariç). Kural 5 gereği bu sayı tüm yollar için aynıdır. Yukarıdaki ağaçta kökün siyah yüksekliği = 2. Kırmızı düğümler sayılmaz — bu yüzden "siyah yükseklik" adını alır.

Düğüm Yapısı

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

typedef enum { RED, BLACK } Color;

typedef struct Node {
    int            data;
    Color          color;   // RED veya BLACK
    struct Node*   left;
    struct Node*   right;
    struct Node*   parent;  // ← ebeveyn pointer (RB için gerekli)
} Node;

/* NIL sentinel — tüm yapraklar bunu gösterir */
Node NIL_NODE = {0, BLACK, NULL, NULL, NULL};
Node* NIL = &NIL_NODE;

Node* yeniDugum(int data) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data   = data;
    n->color  = RED;     // yeni düğüm her zaman KIRMIZI
    n->left   = NIL;
    n->right  = NIL;
    n->parent = NIL;
    return n;
}

AVL'den yapısal farklar:
1. color alanı (height yerine) — 1 bit yeterli.
2. parent pointer — rotasyon ve düzeltme sırasında ebeveyne erişim gerekir.
3. NIL sentinel — NULL yerine özel siyah düğüm kullanılır; kodda NULL kontrolü gereksizleşir.
4. Yeni düğüm her zaman kırmızı eklenir — Kural 5'i (siyah yükseklik) bozmamak için.

Rotasyon Yardımcıları

RB ağacındaki rotasyonlar AVL ile aynı mantıktadır — tek fark parent pointer'larının da güncellenmesi gerektiğidir.

solaRotasyon() / sagaRotasyon() — parent güncellemeli
void solaRotasyon(Node** root, Node* x) {
    Node* y = x->right;
    x->right = y->left;           // T2'yi taşı
    if (y->left != NIL)
        y->left->parent = x;

    y->parent = x->parent;        // y, x'in yerine geçer
    if (x->parent == NIL)
        *root = y;                 // x kökse → y yeni kök
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;

    y->left  = x;                  // x aşağı iner
    x->parent = y;
}

void sagaRotasyon(Node** root, Node* x) {
    Node* y = x->left;
    x->left = y->right;
    if (y->right != NIL)
        y->right->parent = x;

    y->parent = x->parent;
    if (x->parent == NIL)
        *root = y;
    else if (x == x->parent->right)
        x->parent->right = y;
    else
        x->parent->left = y;

    y->right = x;
    x->parent = y;
}

Ekleme (Insert)

RB ekleme iki aşamadan oluşur: önce standart BST ekleme (yeni düğüm kırmızı), sonra kural ihlali varsa düzeltme (fixup).

Neden kırmızı ekleriz? Siyah eklersek Kural 5'i (siyah yükseklik) anında bozarız — çünkü sadece bir yolda siyah düğüm artar. Kırmızı ekleyince Kural 5 korunur; olası tek ihlal Kural 4'tür (art arda kırmızı). Kural 4'ü düzeltmek Kural 5'i düzeltmekten çok daha kolaydır.

rbEkle() — BST ekleme + fixup çağrısı
void rbEkle(Node** root, int data) {
    Node* z = yeniDugum(data);   // kırmızı düğüm

    // ── Standart BST ekleme ──
    Node* y = NIL;               // ebeveyn adayı
    Node* x = *root;
    while (x != NIL) {
        y = x;
        if (z->data < x->data)
            x = x->left;
        else
            x = x->right;
    }
    z->parent = y;
    if (y == NIL)
        *root = z;               // ağaç boştu
    else if (z->data < y->data)
        y->left = z;
    else
        y->right = z;

    // ── Kural ihlallerini düzelt ──
    eklemeDuzelt(root, z);
}

Ekleme Düzeltmeleri — 3 Durum

Yeni kırmızı düğüm (z) eklendiğinde, ebeveyni de kırmızıysa Kural 4 bozulur. Düzeltme, amca (uncle) düğümün rengine göre 3 duruma ayrılır. Her durum ebeveynin büyükebeveynin (grandparent) sol çocuğu olduğu varsayımıyla anlatılır — sağ çocuk olması tam simetriktir.

Terminoloji: z = yeni düğüm, P = ebeveyn (parent), G = büyükebeveyn (grandparent), U = amca (uncle). G'nin P olmayan çocuğu = U.

Durum 1 — Amca Kırmızı → Yeniden Renklendir

Hem ebeveyn (P) hem amca (U) kırmızı. Çözüm basit: P ve U'yu siyaha, G'yi kırmızıya boya. Sonra z = G yapıp yukarı doğru kontrol et (G'nin ebeveyni de kırmızıysa tekrar düzelt).

Durum 1: Amca Kırmızı → Renk Değişimi

Önce (Kural 4 ihlali)

→

Sonra (renk değişimi)

İşlem: P→siyah, U→siyah, G→kırmızı, z=G. Siyah yükseklik değişmedi ✓ Rotasyon yok — sadece renk.

Durum 2 — Amca Siyah, z İç Çocuk (Zikzak) → Rotasyon ile Durum 3'e Dönüştür

Amca siyah ve z bir "iç çocuk" (P sol çocuksa z sağda veya tersi — zikzak). Bu durumu düzeltmek için P'de rotasyon yaparak Durum 3'e dönüştürürüz.

Durum 2 → Durum 3'e Dönüşüm (Sola Rotasyon P'de)

Durum 2 (zikzak)

Sola rot.

⟲→

(P'de)

Durum 3'e dönüştü

Rotasyon z'yi dış çocuk yaparak Durum 3 kalıbını oluşturdu. z ve P rolleri değişti.

Durum 3 — Amca Siyah, z Dış Çocuk → Rotasyon + Renklendir

Amca siyah ve z bir "dış çocuk" (P sol çocuksa z da solda — düz çizgi). G'de rotasyon yapılır ve renkler değiştirilir.

Durum 3: Sağa Rotasyon G'de + Renk Değişimi

Durum 3 (düz çizgi)

Sağa rot.(G)

⟳→

+ renklendir

Dengeli ✓

İşlem: P→siyah, G→kırmızı, G'de sağa rotasyon. Art arda kırmızı çözüldü, siyah yükseklik korundu. Düzeltme biter.

Ekleme Düzeltme Kodu

eklemeDuzelt() — 3 durum (+ simetrik karşılıkları)
void eklemeDuzelt(Node** root, Node* z) {
    while (z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            Node* amca = z->parent->parent->right;

            if (amca->color == RED) {
                /* Durum 1: amca kırmızı → renk değiştir */
                z->parent->color = BLACK;
                amca->color      = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;  // yukarı çık
            } else {
                if (z == z->parent->right) {
                    /* Durum 2: iç çocuk → rotasyonla D3'e */
                    z = z->parent;
                    solaRotasyon(root, z);
                }
                /* Durum 3: dış çocuk → rotasyon + renk */
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                sagaRotasyon(root, z->parent->parent);
            }
        } else {
            /* ── Simetrik: ebeveyn sağ çocuksa ── */
            Node* amca = z->parent->parent->left;
            if (amca->color == RED) {
                z->parent->color = BLACK;
                amca->color      = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    sagaRotasyon(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                solaRotasyon(root, z->parent->parent);
            }
        }
    }
    (*root)->color = BLACK;  // Kural 2: kök her zaman siyah
}

Ekleme düzeltme garantisi: Durum 1 yukarı tırmanır (en fazla O(log n) kez). Durum 2→3 dönüşümü ve Durum 3 düzeltmeyi bitirir. Toplamda en fazla 2 rotasyon ve O(log n) renk değişikliği.

Adım Adım — RB Ağaç Büyümesi

Ekleme sırası: 10, 20, 30, 15, 25, 5, 1 — her adımda ihlali ve düzeltmeyi göreceğiz.

7 Ekleme — Kurallar ve Düzeltmeler

① +10

Kırmızı ekle → Kural 2 ihlali (kök kırmızı) → kökü siyaha boya. Bitti.

② +20

20>10 → sağa ekle (kırmızı). Ebeveyn siyah → ihlal yok ✓

③ +30 → Kural 4 ihlali → Durum 3

→

30 eklendi (kırmızı). P=20 kırmızı, U=NIL (siyah), dış çocuk → Durum 3: sola rotasyon(10), P(20)→siyah, G(10)→kırmızı. 20 yeni kök.

④ +15 → Kural 4 ihlali → Durum 1

→

P=10 kırmızı, U=30 kırmızı → Durum 1: P,U→siyah, G(20)→kırmızı. Ama G kök → tekrar siyaha boya. Rotasyon yok.

⑤ +25 → Durum 2→3 (çift rotasyon)

P=30 siyah? Hayır — 30 siyah! Ebeveyn siyahsa ihlal yok. Ama bekle: 25, 30'un sol çocuğu; P=30 siyah olduğu için ihlal yok ✓. (Bu adım düzeltme gerektirmez.)

⑥ +5 ⑦ +1

+5: 5<10→sol, ebeveyn(10) kırmızı, amca(15) siyah, dış çocuk → Durum 3: sağa rotasyon + renk. Sonra +1: ebeveyn(5) siyah → ihlal yok ✓

Ekleme Durumları Özet

Durum	Koşul	İşlem	Sonuç
1	Amca kırmızı	P, U → siyah; G → kırmızı; z=G	Yukarı tırman (tekrar kontrol)
2	Amca siyah, z iç çocuk	P'de rotasyon	→ Durum 3'e dönüşür
3	Amca siyah, z dış çocuk	P→siyah, G→kırmızı, G'de rotasyon	Düzeltme biter

Silme (Delete)

RB silme, ağaçtaki en karmaşık operasyondur. BST silme uygulanır, ardından siyah düğüm kaldırıldıysa siyah yükseklik bozulur → düzeltme gerekir. Kırmızı düğüm silinirse hiçbir kural bozulmaz — düzeltme gerekmez.

Çift-siyah (double-black) problemi: Siyah bir düğüm silindiğinde, onun yerini alan düğüm "ekstra siyah" taşır. Bu kavramsal düğüm "çift-siyah" olarak adlandırılır. Düzeltme, bu ekstra siyahı yukarı doğru iletir veya rotasyon/renk değişikliğiyle absorbe eder.

Yardımcı: Transplant

transplant() — düğüm değiştirme
/* u'yu v ile değiştir (sadece ebeveyn bağlantısı) */
void transplant(Node** root, Node* u, Node* v) {
    if (u->parent == NIL)
        *root = v;
    else if (u == u->parent->left)
        u->parent->left = v;
    else
        u->parent->right = v;
    v->parent = u->parent;
}

Silme Kodu

rbSil() — BST silme + fixup çağrısı
void rbSil(Node** root, int data) {
    Node* z = bstAra(*root, data);
    if (z == NIL) return;

    Node* y = z;            // silinecek/taşınacak düğüm
    Color orijRenk = y->color;
    Node* x;                // y'nin yerine geçen düğüm

    if (z->left == NIL) {
        x = z->right;
        transplant(root, z, z->right);
    } else if (z->right == NIL) {
        x = z->left;
        transplant(root, z, z->left);
    } else {
        // İki çocuklu: inorder successor
        y = z->right;
        while (y->left != NIL) y = y->left;
        orijRenk = y->color;
        x = y->right;

        if (y->parent == z) {
            x->parent = y;
        } else {
            transplant(root, y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        transplant(root, z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }
    free(z);

    // Orijinal renk SİYAHsa → siyah yükseklik bozulmuş olabilir
    if (orijRenk == BLACK)
        silmeDuzelt(root, x);
}

Silme Düzeltmeleri — 4 Durum

Çift-siyah düğüm (x) oluştuğunda, kardeş (sibling = w) ve yeğenlerin (w'nin çocukları) rengine göre 4 durum ortaya çıkar. x'in sol çocuk olduğu varsayılır — sağ çocuk olması simetriktir.

Durum 1 — Kardeş (w) Kırmızı

w kırmızı ise → w'yi siyah, P'yi kırmızı yap, P'de sola rotasyon. Bu, w'nin siyah çocuğunu yeni kardeş yapar → Durum 2, 3 veya 4'e dönüşür.

Durum 1: Kardeş kırmızı → Dönüştürme

→

w→siyah, P→kırmızı, sol rot.(P)

Yeni w siyah → D2/D3/D4'e geç

Durum 2 — Kardeş Siyah, İki Yeğen de Siyah

w siyah, her iki çocuğu da siyah → w'yi kırmızıya boya, ekstra siyahı P'ye aktar. Eğer P kırmızıysa siyaha boyanır ve biter. P siyahsa P yeni çift-siyah olur → yukarı tırman.

Durum 2: Her şey siyah → Ekstra siyahı yukarı taşı

→

w → kırmızı
x'in ekstra siyahı P'ye geçer.
P kırmızıysa → siyah ol, bitti.
P siyahsa → P yeni çift-siyah, tekrar.

Durum 3 — Kardeş Siyah, Yakın Yeğen Kırmızı, Uzak Yeğen Siyah

w siyah, sol çocuğu (yakın yeğen) kırmızı, sağ çocuğu (uzak yeğen) siyah → yakın yeğeni siyah, w'yi kırmızı yap, w'de sağa rotasyon. Durum 4'e dönüşür.

Durum 3 → Durum 4'e Dönüşüm

→

Yakın yeğen→siyah, w→kırmızı
Sağa rotasyon (w'de)
→ Durum 4 oluştu
(yeni w'nin uzak yeğeni kırmızı)

Durum 4 — Kardeş Siyah, Uzak Yeğen Kırmızı → Son Düzeltme

w siyah, sağ çocuğu (uzak yeğen) kırmızı → w P'nin rengini alır, P→siyah, uzak yeğen→siyah, P'de sola rotasyon. Çift-siyah çözüldü — düzeltme biter.

Durum 4: Uzak yeğen kırmızı → Rotasyon + Renk → BİTTİ

→

w→P'nin rengi, P→siyah
uzak yeğen→siyah
Sola rotasyon (P'de)
✓ Çift-siyah çözüldü!

Silme Düzeltme Kodu

silmeDuzelt() — 4 durum (+ simetri)
void silmeDuzelt(Node** root, Node* x) {
    while (x != *root && x->color == BLACK) {
        if (x == x->parent->left) {
            Node* w = x->parent->right;  // kardeş

            /* Durum 1: kardeş kırmızı */
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                solaRotasyon(root, x->parent);
                w = x->parent->right;
            }

            /* Durum 2: iki yeğen de siyah */
            if (w->left->color == BLACK
             && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;  // yukarı tırman
            } else {
                /* Durum 3: yakın yeğen kırmızı */
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    sagaRotasyon(root, w);
                    w = x->parent->right;
                }
                /* Durum 4: uzak yeğen kırmızı → BİTTİ */
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color  = BLACK;
                solaRotasyon(root, x->parent);
                x = *root;  // döngüden çık
            }
        } else {
            /* ── Simetrik: x sağ çocuksa ── */
            Node* w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                sagaRotasyon(root, x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK
             && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    solaRotasyon(root, w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color   = BLACK;
                sagaRotasyon(root, x->parent);
                x = *root;
            }
        }
    }
    x->color = BLACK;
}

Silme Durumları Özet

Durum	Kardeş (w)	Yeğenler	İşlem	Sonuç
1	Kırmızı	—	w→S, P→K, rot.(P)	→ D2/D3/D4'e dönüş
2	Siyah	İkisi de siyah	w→K, x=P	Yukarı tırman
3	Siyah	Yakın K, uzak S	Yakın→S, w→K, rot.(w)	→ D4'e dönüş
4	Siyah	Uzak kırmızı	w→P rengi, P→S, uzak→S, rot.(P)	Bitti ✓

Karmaşıklık Analizi

Operasyon	Zaman	Max Rotasyon	Renk Değişikliği
Ekleme	O(log n)	2	O(log n)
Silme	O(log n)	3	O(log n)
Arama	O(log n)	0	0
Min / Max	O(log n)	0	0
Alan (düğüm başı)	data + color (1 bit) + left + right + parent = 5 alan

RB yükseklik sınırı: n düğümlü RB ağacının yüksekliği en fazla 2 × log₂(n+1)'dir. AVL'nin sınırı 1.44 × log₂(n+2) idi — RB biraz daha uzun ama rotasyon sayısı sabit (ekleme max 2, silme max 3).

AVL vs Red-Black — Detaylı Karşılaştırma

Özellik	AVL Ağacı	Red-Black Ağacı
Denge kriteri	\|BF\| ≤ 1 (sıkı)	En uzun yol ≤ 2× en kısa (gevşek)
Max yükseklik	~1.44 log₂ n (daha kısa)	~2 log₂ n
Arama hızı	Biraz daha hızlı (daha kısa h)	Biraz daha yavaş
Ekleme rotasyonu	Max 2	Max 2 (benzer)
Silme rotasyonu	Max O(log n)	Max 3 (sabit!)
Ek bellek	int height (4 byte)	1 bit color (+ parent ptr)
Implementasyon	Daha basit	Daha karmaşık (özellikle silme)
Kullanım alanı	Veritabanı indeksleme	İşletim sistemi, standart kütüphaneler

AVL tercih et:

Okuma ağırlıklı iş yüklerinde
Arama/sorgulama oranı >> ekleme/silme
Veritabanı indeksleri, sözlük yapıları

Red-Black tercih et:

Yazma ağırlıklı veya karma iş yüklerinde
Silme sıklığı yüksekse (max 3 rot. garantisi)
İşletim sistemi çekirdeği, standart kütüphaneler

Ekleme ve Silme Akış Özeti

Ekleme Düzeltme Akışı

START: Yeni düğüm kırmızı eklendi
├─ Ebeveyn siyah? → BİTTİ ✓
├─ Ebeveyn kırmızı?
│  ├─ Amca kırmızı? → D1: Renk değiştir, yukarı tırman ↑
│  └─ Amca siyah?
│     ├─ İç çocuk? → D2: Rotasyon → D3'e dönüştür
│     └─ Dış çocuk? → D3: Rotasyon + renk → BİTTİ ✓
└─ Kökü siyah yap (Kural 2)

Silme Düzeltme Akışı

START: Siyah düğüm silindi → çift-siyah (x)
├─ x kırmızı? → siyaha boya → BİTTİ ✓
├─ x kök? → BİTTİ ✓
├─ Kardeş (w) kırmızı? → D1: Dönüştür → D2/D3/D4
├─ w siyah, iki yeğen siyah? → D2: w→kırmızı, yukarı ↑
├─ w siyah, yakın yeğen K? → D3: Rot. → D4'e dönüştür
└─ w siyah, uzak yeğen K? → D4: Rot.+renk → BİTTİ ✓

Gerçek Dünya Kullanımları

Sistem / Kütüphane	Kullanım
Linux Kernel — CFS	Süreç zamanlayıcı: görevleri "sanal çalışma süresi"ne göre RB ağaçta tutar
Linux Kernel — vm_area	Sanal bellek alanlarını RB ağaçla yönetir
Java — TreeMap / TreeSet	Sıralı anahtar-değer eşleştirmesi
C++ STL — std::map / std::set	Sıralı konteynerler
.NET — SortedDictionary	Sıralı sözlük implementasyonu
Nginx	Timer yönetimi için RB ağaç kullanır

Sonuç

Kırmızı-Siyah ağaç, 5 basit renklenme kuralı ile "en uzun yol ≤ 2× en kısa yol" garantisi sağlar. Ekleme düzeltmesi 3 durum (amca kırmızı/iç çocuk/dış çocuk), silme düzeltmesi 4 durum (kardeş rengi + yeğen renkleri) içerir. Rotasyon sayısı sabit üst sınırlıdır: ekleme max 2, silme max 3.

AVL'ye göre arama biraz yavaş olsa da yazma operasyonlarında daha az rotasyon gerektirir. Bu yüzden Linux çekirdeği, Java ve C++ standart kütüphaneleri gibi yazma-yoğun sistemlerde tercih edilir.

Bölüm 6.4.2 özeti: RB ağaç = BST + 5 renklendirme kuralı. Yeni düğüm kırmızı eklenir → "art arda kırmızı" ihlali amca rengine göre 3 durumda düzeltilir (max 2 rot.). Siyah düğüm silinince "çift-siyah" problemi kardeş/yeğen renklerine göre 4 durumda düzeltilir (max 3 rot.). Tüm operasyonlar garanti O(log n). Yükseklik ≤ 2 × log₂(n+1). AVL okuma için, RB yazma için optimize.

← Veri Yapıları