Ekleme, Arama, Silme ve Min/Max - Adım Adım
BST'nin gücü, temel işlemlerin hepsinin O(log n) sürede yapılabilmesidir. Bu bölümde dört temel işlemi detaylı olarak inceleyeceğiz:
Yeni değer ekle
Değer bul
En küçük/büyük bul
Değer kaldır
BST'ye yeni bir değer eklemek, arama işlemine çok benzer. Fark şu: aramayı yapıp "bulunamadı" dediğimiz yere yeni node'u yerleştiriyoruz!
Başlangıç Ağacı
35 Eklendikten Sonra
Değer girin ve BST'ye nasıl eklendiğini adım adım izleyin!
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()İkili arama mantığı: Her adımda arama alanı yarıya iner! Bu sayede n elemanlı bir ağaçta en fazla log₂(n) adımda sonuca ulaşırız.
Değer girin ve BST'de nasıl arandığını adım adım izleyin!
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)")BST'nin güzel özelliği: En küçük eleman her zaman en solda, en büyük eleman her zaman en sağda bulunur!
Kökten başla, sürekli sola git. Sol çocuğu olmayan node = minimum!
def find_min(node):
while node.left:
node = node.left
return node.data
Kökten başla, sürekli sağa git. Sağ çocuğu olmayan node = maximum!
def find_max(node):
while node.right:
node = node.right
return node.data
En küçük veya en büyük elemanın nasıl bulunduğunu adım adım izleyin!
Dengeli bir ağaçta, köken en soldaki/sağdaki yaprak node'a kadar olan mesafe yaklaşık log₂(n)'dir. Her adımda bir seviye aşağı ineriz, yani ağacın yüksekliği kadar adım atarız.
Silme işlemi BST'deki en karmaşık işlemdir çünkü BST kuralını korumamız gerekir. Silinecek node'un kaç çocuğu olduğuna göre 3 farklı durum vardır:
Yaprak Node
Direkt sil
Tek Çocuk
Çocuğu yerine koy
İki Çocuk
Successor ile değiştir
En kolay durum! Node'un hiç çocuğu yoktur, yani ağacın "yaprak"larından biridir. Bu durumda node'u direkt sileriz - başka hiçbir node etkilenmez.
None yapÖnce: 10 silinecek
Sonra: 10 silindi
💡 Önemli: Yaprak node silmek en basit durumdur çünkü hiçbir alt ağaç etkilenmez. Sadece parent'ın pointer'ı None olur.
Node'un ya sol ya da sağ çocuğu vardır (ikisi birden değil). Bu durumda node'u sil, tek çocuğunu onun yerine koy. Çocuk tüm alt ağacıyla birlikte yukarı çıkar.
Önce: 30 silinecek
Sonra: 20 yerine geçti
💡 Önemli: Çocuk yukarı çıkarken tüm alt ağacını beraberinde getirir. BST kuralı korunur çünkü çocuğun alt ağacındaki tüm değerler zaten doğru yerde.
Bu durumda node'u direkt silemeyiz çünkü iki alt ağacı var. Her iki alt ağacı da korumamız gerekiyor. Çözüm: Inorder Successor veya Inorder Predecessor kullanmak.
Inorder Successor: Bir node'dan bir sonraki büyük değerdir. BST'de bu değer şöyle bulunur:
Önce: 50 silinecek
🔴 Kırmızı: Silinecek | 🟢 Yeşil: Successor
Sonra: 60 köke geldi
Inorder Successor (60), silinecek node'dan (50) büyük olan en küçük değerdir. Bu özel konumu sayesinde:
Successor yerine Predecessor (bir önceki küçük değer) de kullanılabilir. Predecessor için sol alt ağacın en sağ node'unu bulursun. İkisi de geçerli çözümlerdir!
Bir düğüme tıklayarak silin ve 3 farklı durumu gözlemleyin!
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)Not: En kötü durum, ağacın tek tarafa uzaması durumunda (linked list gibi) oluşur.