5.1: İkili Arama Ağacı (BST) Giriş

🤔 Ağaç (Tree) Veri Yapısı Nedir?

Ağaç, hiyerarşik bir veri yapısıdır. Linked List'in genelleştirilmiş halidir:

Linked List: Her node → 1 sonraki node
Binary Tree: Her node → 0, 1 veya 2 çocuk node

📌 Temel Terimler

Root (Kök): Ağacın en üstündeki node
Parent (Ebeveyn): Bir node'un üstündeki node
Child (Çocuk): Bir node'un altındaki node'lar
Leaf (Yaprak): Çocuğu olmayan node'lar
Height (Yükseklik): Kökten en derin yaprağa mesafe

🎯 İkili Arama Ağacı (BST) Özelliği

🔑 BST Kuralı (Çok Önemli!)

Her node için:

Sol alt ağaçtaki TÜM değerler < node değeri
Sağ alt ağaçtaki TÜM değerler > node değeri

Bu kural sayesinde arama O(log n) olur!

🧱 Node (Düğüm) Yapısı

BST node'u, linked list node'una benzer ama iki referans içerir:

LEFT

←

DATA

50

RIGHT

→

Python Kodu

# BST için Node sınıfı
class Node:
    def __init__(self, data):
        self.data = data      # Saklanan değer
        self.left = None      # Sol çocuğa referans (küçükler)
        self.right = None     # Sağ çocuğa referans (büyükler)

# Örnek: Basit bir ağaç oluşturalım
#        50
#       /  \
#      30   70
#     / \   / \
#    20 40 60 80

root = Node(50)
root.left = Node(30)
root.right = Node(70)

root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)

# Yapıyı kontrol edelim
print("🌳 Ağaç Yapısı:")
print(f"Kök: {root.data}")
print(f"  Sol çocuk: {root.left.data}")
print(f"    Sol-sol: {root.left.left.data}")
print(f"    Sol-sağ: {root.left.right.data}")
print(f"  Sağ çocuk: {root.right.data}")
print(f"    Sağ-sol: {root.right.left.data}")
print(f"    Sağ-sağ: {root.right.right.data}")

# BST kuralını kontrol edelim
print("\n✅ BST Kuralı Kontrolü:")
print(f"  30 < 50 < 70? {root.left.data} < {root.data} < {root.right.data}")
print(f"  20 < 30 < 40? {root.left.left.data} < {root.left.data} < {root.left.right.data}")
print(f"  60 < 70 < 80? {root.right.left.data} < {root.right.data} < {root.right.right.data}")

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)

print(f"Kök: {root.data}")
print(f"Sol: {root.left.data}")
print(f"Sağ: {root.right.data}")

Çıktı bekleniyor...

📊 Neden BST? Performans Karşılaştırması

📋 Sıralı Dizi

Arama:	O(n) (sıralıysa O(log n))
Ekleme:	O(n) (kaydırma gerekir)
Silme:	O(n) (kaydırma gerekir)

🔗 Linked List

Arama:	O(n)
Ekleme (başa):	O(1)
Silme:	O(n) (arama + O(1))

🌳 BST (Dengeli)

Arama:	O(log n) ✨
Ekleme:	O(log n) ✨
Silme:	O(log n) ✨

⚠️ Önemli Not: Dengesiz BST

Eğer elemanlar sıralı eklenirse (1, 2, 3, 4, 5...), BST bir "linked list"e dönüşür ve performans O(n) olur!

Bu problemi çözmek için AVL Tree veya Red-Black Tree gibi dengeli ağaçlar kullanılır.

🔍 BST'de Arama Nasıl Çalışır?

Aradığımız değer: 40

Kökten başla (50)
40 < 50 → Sola git (30)
40 > 30 → Sağa git (40)
40 == 40 → Bulundu! ✅

Sadece 3 karşılaştırma ile 7 elemanlı ağaçta değeri bulduk!

Python Kodu

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def search(root, target):
    """BST'de arama - O(log n)"""
    steps = 0
    current = root

    while current is not None:
        steps += 1
        print(f"Adım {steps}: {current.data} ile karşılaştır", end=" → ")

        if target == current.data:
            print(f"BULUNDU! ✅")
            return current, steps
        elif target < current.data:
            print(f"{target} < {current.data}, SOLA git")
            current = current.left
        else:
            print(f"{target} > {current.data}, SAĞA git")
            current = current.right

    print("Bulunamadı ❌")
    return None, steps

# Ağacı oluştur
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)

print("🌳 Ağaç: 50 → (30, 70) → (20, 40, 60, 80)\n")

# Farklı değerleri ara
for target in [40, 80, 25, 50]:
    print(f"\n🔍 {target} aranıyor:")
    result, steps = search(root, target)
    print(f"   Toplam adım: {steps}")

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def search(root, target):
    current = root
    steps = 0
    while current:
        steps += 1
        if target == current.data:
            return current, steps
        elif target < current.data:
            current = current.left
        else:
            current = current.right
    return None, steps

root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)

for val in [40, 20, 100]:
    result, steps = search(root, val)
    status = "Bulundu" if result else "Yok"
    print(f"{val}: {status} ({steps} adım)")

Çıktı bekleniyor...

🌍 Gerçek Hayat Kullanım Alanları

💾 Veritabanı ve Dosya Sistemleri

📚 Veritabanı Index'leri: MySQL, PostgreSQL gibi veritabanları B-Tree (BST'nin gelişmiş hali) kullanır. Milyonlarca kayıt arasında saniyenin kesri içinde arama yapabilirsiniz.
📁 Dosya Sistemleri: NTFS, ext4 gibi dosya sistemleri klasör yapısını ağaç şeklinde organize eder.

🖥️ Yazılım Uygulamaları

🔤 Otomatik Tamamlama: Arama motorları ve IDE'ler yazdığınız harflere göre önerileri BST varyantları (Trie) ile bulur.
📖 Sözlük Uygulamaları: Kelime arama ve yazım denetimi sistemleri.
🗜️ Huffman Kodlama: ZIP, GZIP gibi sıkıştırma algoritmaları binary tree kullanır.

🎮 Oyun ve Grafik

🎮 Collision Detection: Oyunlarda nesnelerin çarpışıp çarpışmadığını kontrol etmek için BST varyantları kullanılır.
🗺️ Harita Uygulamaları: Google Maps gibi uygulamalar yakındaki noktaları bulmak için spatial tree yapıları kullanır.

💡 Neden BST?

Dizide arama: 1 milyon elemanda → 1.000.000 karşılaştırma (O(n))

BST'de arama: 1 milyon elemanda → sadece ~20 karşılaştırma (O(log n))

Bu fark, gerçek dünya uygulamalarında hayati önem taşır!

🌳 5.1: İkili Arama Ağacı (BST) Nedir?