AVL Ağacı Kendini Dengeleyen BST

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int           data;
    struct Node*  left;
    struct Node*  right;
    int           height;   // ← AVL ek alanı
} Node;

/* ── Yardımcı fonksiyonlar ── */
int height(Node* n) {
    return n ? n->height : -1;
}

int maxOf(int a, int b) {
    return a > b ? a : b;
}

int getBF(Node* n) {
    return n ? height(n->left) - height(n->right) : 0;
}

void updateHeight(Node* n) {
    n->height = 1 + maxOf(height(n->left), height(n->right));
}

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;
    n->height = 0;  // yaprak: h=0
    return n;
}

/*      z             y
 *     / \           / \
 *    y   T3  →    T1   z
 *   / \               / \
 *  T1  T2           T2   T3
 */
Node* sagaRotasyon(Node* z) {
    Node* y  = z->left;       // ① y = sol çocuk
    Node* T2 = y->right;      // T2'yi kaydet

    y->right = z;             // ② y'nin sağı = z (z aşağı)
    z->left  = T2;            // ③ z'nin solu = T2

    updateHeight(z);           // önce z (artık alt düğüm)
    updateHeight(y);           // sonra y (yeni kök)

    return y;                  // yeni kök
}

/*    z                 y
 *   / \              / \
 *  T1  y    →      z   T3
 *     / \         / \
 *    T2  T3     T1   T2
 */
Node* solaRotasyon(Node* z) {
    Node* y  = z->right;      // ① y = sağ çocuk
    Node* T2 = y->left;       // T2'yi kaydet

    y->left  = z;             // ② y'nin solu = z (z aşağı)
    z->right = T2;            // ③ z'nin sağı = T2

    updateHeight(z);
    updateHeight(y);

    return y;                  // yeni kök
}

Node* balance(Node* node) {
    int bf = getBF(node);

    // Sol-ağır (BF ≥ +2)
    if (bf > 1) {
        if (getBF(node->left) < 0) {
            // LR: önce sol çocuğu sola döndür
            node->left = solaRotasyon(node->left);
        }
        // LL (veya LR→LL dönüşmüş): sağa döndür
        return sagaRotasyon(node);
    }

    // Sağ-ağır (BF ≤ -2)
    if (bf < -1) {
        if (getBF(node->right) > 0) {
            // RL: önce sağ çocuğu sağa döndür
            node->right = sagaRotasyon(node->right);
        }
        // RR (veya RL→RR dönüşmüş): sola döndür
        return solaRotasyon(node);
    }

    return node;  // dengeli, rotasyon gerekmez
}

Node* avlEkle(Node* node, int deger) {
    // ── Adım 1: Standart BST ekleme ──
    if (!node)
        return yeniDugum(deger);

    if (deger < node->data)
        node->left  = avlEkle(node->left, deger);
    else if (deger > node->data)
        node->right = avlEkle(node->right, deger);
    else
        return node;  // duplicate, ekleme

    // ── Adım 2: Yükseklik güncelle ──
    updateHeight(node);

    // ── Adım 3: Dengele (gerekirse rotasyon) ──
    return balance(node);
}

Node* bstMin(Node* n) {
    while (n->left) n = n->left;
    return n;
}

Node* avlSil(Node* node, int deger) {
    if (!node) return NULL;

    // ── Adım 1: Standart BST silme ──
    if (deger < node->data) {
        node->left = avlSil(node->left, deger);
    } else if (deger > node->data) {
        node->right = avlSil(node->right, deger);
    } else {
        // Düğüm bulundu — 3 BST silme durumu
        if (!node->left) {
            Node* temp = node->right;
            free(node);
            return temp;  // yaprak veya tek sağ çocuk
        }
        if (!node->right) {
            Node* temp = node->left;
            free(node);
            return temp;  // tek sol çocuk
        }
        // İki çocuk: inorder successor ile değiştir
        Node* succ = bstMin(node->right);
        node->data = succ->data;
        node->right = avlSil(node->right, succ->data);
    }

    // ── Adım 2: Yükseklik güncelle ──
    updateHeight(node);

    // ── Adım 3: Dengele ──
    return balance(node);
}

void inorder(Node* n) {
    if (!n) return;
    inorder(n->left);
    printf("%d ", n->data);
    inorder(n->right);
}

void agacBilgi(Node* root) {
    printf("  Inorder:   "); inorder(root); printf("\n");
    printf("  Kök: %d | Yükseklik: %d | Kök BF: %d\n",
           root->data, root->height, getBF(root));
}

int main() {
    Node* root = NULL;

    printf("=== AVL Ağacı Demo ===\n\n");

    // Sıralı veri ekle — BST'de dejenere olurdu!
    printf("--- Sıralı Ekleme: 10,20,30,40,50,60,70 ---\n");
    int degerler[] = {10,20,30,40,50,60,70};
    for (int i = 0; i < 7; i++) {
        root = avlEkle(root, degerler[i]);
        printf("insert(%d) → kök=%d, h=%d\n",
               degerler[i], root->data, root->height);
    }
    agacBilgi(root);

    // Arama
    printf("\n--- Arama ---\n");
    printf("search(50): %s\n",
           bstAra(root,50) ? "Bulundu ✓" : "Yok");
    printf("search(35): %s\n",
           bstAra(root,35) ? "Bulundu" : "Bulunamadı ✗");

    // Silme
    printf("\n--- Silme ---\n");
    root = avlSil(root, 20);
    printf("delete(20): "); agacBilgi(root);

    root = avlSil(root, 40);
    printf("delete(40): "); agacBilgi(root);

    root = avlSil(root, 10);
    printf("delete(10): "); agacBilgi(root);

    printf("\nBST'de sıralı ekleme → h=6 (O(n))\n");
    printf("AVL'de sıralı ekleme → h=%d (O(log n)) ✓\n",
           root->height);

    return 0;
}

=== AVL Ağacı Demo ===

--- Sıralı Ekleme: 10,20,30,40,50,60,70 ---
insert(10) → kök=10, h=0
insert(20) → kök=10, h=1
insert(30) → kök=20, h=1        ← RR rotasyon: 10→20 kök oldu
insert(40) → kök=20, h=2
insert(50) → kök=20, h=2        ← RR rotasyon: 40'ta
insert(60) → kök=40, h=2        ← RR rotasyon: 20→40 kök oldu
insert(70) → kök=40, h=2        ← RR rotasyon: 60'ta
  Inorder:   10 20 30 40 50 60 70
  Kök: 40 | Yükseklik: 2 | Kök BF: 0

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

--- Silme ---
delete(20):   Inorder:   10 30 40 50 60 70
  Kök: 40 | Yükseklik: 2 | Kök BF: 0
delete(40):   Inorder:   10 30 50 60 70
  Kök: 50 | Yükseklik: 2 | Kök BF: 0
delete(10):   Inorder:   30 50 60 70
  Kök: 50 | Yükseklik: 2 | Kök BF: -1

BST'de sıralı ekleme → h=6 (O(n))
AVL'de sıralı ekleme → h=2 (O(log n)) ✓