🔧 5.2: BST Temel İşlemler

Ekleme, Arama ve Silme

1️⃣ Ekleme (Insert) O(log n)

Yeni değer, BST kuralına uygun yere yerleştirilir:

  1. Kökten başla
  2. Değer küçükse sola, büyükse sağa git
  3. Boş pozisyon bulana kadar devam et
  4. Yeni node'u o pozisyona yerleştir
Python Kodu 
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, data):
        """BST'ye yeni değer ekle - O(log n)"""
        if not self.root:
            self.root = Node(data)
            print(f"🌱 {data} kök olarak eklendi")
            return

        current = self.root
        while True:
            if data < current.data:
                # Sola git
                if current.left is None:
                    current.left = Node(data)
                    print(f"⬅️ {data}, {current.data}'in soluna eklendi")
                    return
                current = current.left
            elif data > current.data:
                # Sağa git
                if current.right is None:
                    current.right = Node(data)
                    print(f"➡️ {data}, {current.data}'in sağına eklendi")
                    return
                current = current.right
            else:
                print(f"⚠️ {data} zaten var!")
                return

    def display(self, node=None, level=0, prefix="Kök"):
        """Ağacı görselleştir"""
        if node is None:
            node = self.root
        if node is not None:
            print(" " * (level * 4) + prefix + ": " + str(node.data))
            if node.left or node.right:
                if node.left:
                    self.display(node.left, level + 1, "Sol")
                else:
                    print(" " * ((level + 1) * 4) + "Sol: -")
                if node.right:
                    self.display(node.right, level + 1, "Sağ")
                else:
                    print(" " * ((level + 1) * 4) + "Sağ: -")

# Test
print("=" * 50)
print("📌 BST EKLEME DEMO")
print("=" * 50)

bst = BST()
values = [50, 30, 70, 20, 40, 60, 80, 35]

for v in values:
    bst.insert(v)

print("\n🌳 Ağaç Yapısı:")
bst.display()
Çıktı bekleniyor...

2️⃣ Arama (Search) O(log n)

İkili arama mantığı: Her adımda arama alanı yarıya iner!

65 aranıyor:
50
65>50 →
70
65<70 →
60
65>60 →
65
✅ Bulundu!
Python Kodu 
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, data):
        if not self.root:
            self.root = Node(data)
            return
        current = self.root
        while True:
            if data < current.data:
                if not current.left:
                    current.left = Node(data)
                    return
                current = current.left
            else:
                if not current.right:
                    current.right = Node(data)
                    return
                current = current.right

    def search(self, target):
        """
        BST'de arama - O(log n)
        İteratif (döngü ile) versiyon
        """
        current = self.root
        steps = []

        while current:
            steps.append(current.data)
            if target == current.data:
                return True, steps
            elif target < current.data:
                current = current.left
            else:
                current = current.right

        return False, steps

    def search_recursive(self, target, node=None, steps=None):
        """
        BST'de arama - O(log n)
        Recursive (özyinelemeli) versiyon
        """
        if node is None:
            node = self.root
        if steps is None:
            steps = []

        if node is None:
            return False, steps

        steps.append(node.data)

        if target == node.data:
            return True, steps
        elif target < node.data:
            return self.search_recursive(target, node.left, steps)
        else:
            return self.search_recursive(target, node.right, steps)

# Test
bst = BST()
for v in [50, 30, 70, 20, 40, 60, 80, 65, 75]:
    bst.insert(v)

print("🌳 Ağaç: 50 → (30, 70) → ...")
print("\n" + "=" * 50)
print("🔍 ARAMA TESTLERİ")
print("=" * 50)

for target in [65, 40, 100, 50]:
    found, path = bst.search(target)
    status = "✅ Bulundu" if found else "❌ Yok"
    print(f"\n{target} aranıyor:")
    print(f"  Yol: {' → '.join(map(str, path))}")
    print(f"  Sonuç: {status} ({len(path)} adım)")
Çıktı bekleniyor...

3️⃣ Silme (Delete) O(log n)

Silme işlemi 3 farklı duruma göre değişir:

📗 Durum 1: Yaprak Node (Çocuğu Yok)

En kolay durum: Node'u direkt sil

20'yi sil: 20 → null

📙 Durum 2: Tek Çocuklu Node

Node'u sil, çocuğunu yerine koy

30'u sil (sadece sol çocuk var): 30 → 25 (çocuk yerine geçer)

📕 Durum 3: İki Çocuklu Node

En zor durum:

  1. Sağ alt ağacın en küçük değerini bul (inorder successor)
  2. Bu değeri silinecek node'un yerine koy
  3. Successor'ı eski yerinden sil (Durum 1 veya 2)
Python Kodu 
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, data):
        if not self.root:
            self.root = Node(data)
            return
        c = self.root
        while True:
            if data < c.data:
                if not c.left: c.left = Node(data); return
                c = c.left
            else:
                if not c.right: c.right = Node(data); return
                c = c.right

    def find_min(self, node):
        """En küçük değeri bul (en sol node)"""
        while node.left:
            node = node.left
        return node

    def delete(self, target, node=None, is_root_call=True):
        """BST'den değer sil - O(log n) - Recursive"""
        if is_root_call:
            node = self.root

        if node is None:
            print(f"❌ {target} bulunamadı!")
            return node

        # Hedefi bul
        if target < node.data:
            node.left = self.delete(target, node.left, False)
        elif target > node.data:
            node.right = self.delete(target, node.right, False)
        else:
            # BULUNDU! Şimdi sil

            # Durum 1 & 2: 0 veya 1 çocuk
            if node.left is None:
                print(f"🗑️ {target} silindi (sağ çocuk/None ile değiştirildi)")
                return node.right
            elif node.right is None:
                print(f"🗑️ {target} silindi (sol çocuk ile değiştirildi)")
                return node.left

            # Durum 3: 2 çocuk
            # Inorder successor'ı bul (sağ alt ağacın minimumu)
            successor = self.find_min(node.right)
            print(f"🔄 {target} → {successor.data} ile değiştiriliyor (inorder successor)")
            node.data = successor.data
            # Successor'ı sil
            node.right = self.delete(successor.data, node.right, False)

        if is_root_call:
            self.root = node
        return node

    def inorder(self, node=None, result=None):
        """Sıralı çıktı (inorder traversal)"""
        if result is None:
            result = []
        if node is None:
            node = self.root
        if node:
            self.inorder(node.left, result)
            result.append(node.data)
            self.inorder(node.right, result)
        return result

# Test
bst = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
    bst.insert(v)

print("🌳 Başlangıç (inorder):", bst.inorder())

print("\n--- Silme İşlemleri ---\n")

# Durum 1: Yaprak
bst.delete(20)
print(f"   Sonuç: {bst.inorder()}\n")

# Durum 3: İki çocuklu
bst.delete(50)
print(f"   Sonuç: {bst.inorder()}\n")

# Olmayan değer
bst.delete(100)
Çıktı bekleniyor...

📊 Zaman Karmaşıklığı Özeti

İşlem Ortalama En Kötü (Dengesiz)
Arama O(log n) O(n)
Ekleme O(log n) O(n)
Silme O(log n) O(n)

Not: En kötü durum, ağacın tek tarafa uzaması durumunda (linked list gibi) oluşur.

⬅️ Önceki: BST Giriş 📋 BST Menü Sonraki: Traversal ➡️