Binary Search Tree - Hızlı Arama için Ağaç Yapısı
Şimdiye kadar öğrendiğimiz veri yapılarını düşünelim ve bir problemi ele alalım:
Bir telefon rehberi uygulaması yazıyorsunuz. Kullanıcılar:
Bu üç işlemi de hızlı yapan bir yapıya ihtiyacımız var!
Ekleme hızlı (sona ekle) ama arama çok yavaş - tüm diziyi taramak gerekir.
| Arama: | O(n) 😟 |
| Ekleme: | O(1) 😊 |
| Silme: | O(n) 😟 |
Binary search ile arama hızlı, ama ekleme/silme için kaydırma gerekir.
| Arama: | O(log n) 😊 |
| Ekleme: | O(n) 😟 |
| Silme: | O(n) 😟 |
Ekleme/silme kolay, ama sıralı tutulsa bile arama için baştan taramak gerekir.
| Arama: | O(n) 😟 |
| Ekleme: | O(1)* 😊 |
| Silme: | O(n) 😟 |
*Pozisyon biliniyorsa
BST, hem arama hem ekleme hem silme işlemlerini O(log n)'de yapabilir!
BST, ikili ağaçlara (binary tree) özel bir kural ekler. Bu kural sayesinde arama çok hızlı olur:
Ağaçtaki her node için şu kural geçerlidir:
Bu basit kural, her karşılaştırmada arama alanını yarıya indirmemizi sağlar!
Sadece direkt çocuklar değil, tüm alt ağaç için geçerli:
50
/ \
30 70
/ \ / \
20 40 60 80
50'nin sol alt ağacındaki TÜM değerler (20, 30, 40) < 50
50'nin sağ alt ağacındaki TÜM değerler (60, 70, 80) > 50
Değer girin ve "Ekle" butonuna tıklayın
BST node'u, linked list node'una benzer ama iki referans içerir:
# 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}")| Arama: | O(n) (sıralıysa O(log n)) |
| Ekleme: | O(n) (kaydırma gerekir) |
| Silme: | O(n) (kaydırma gerekir) |
| Arama: | O(n) |
| Ekleme (başa): | O(1) |
| Silme: | O(n) (arama + O(1)) |
| Arama: | O(log n) ✨ |
| Ekleme: | O(log n) ✨ |
| Silme: | O(log n) ✨ |
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'nin gücü, ikili arama (binary search) mantığından gelir. Her karşılaştırmada arama alanı yarıya iner!
Her node'da kendimize şunu sorarız:
50 ← Başla / \ 30 70 / \ / \ 20 40 60 80
7 elemanlı ağaçta sadece 3 karşılaştırma ile değeri bulduk!
Bir 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
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}")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!