- İkili ağacı önce-kök, ortada-kök, sonra-kök ve düzey sırasıyla dolaşmak
- İkili arama ağacında arama, ekleme ve silme yapmak ve O(h) maliyetini açıklamak
- Yığında ekleme ve en küçüğü çıkarmayı dizi gösterimi üzerinde izlemek
Bilgisayarındaki klasörler, bir soy ağacı, bir web sayfasının HTML öğeleri, derleyicinin programdan kurduğu sözdizimi ağacı; hepsi birer ağaçtır. Bir hastanenin acil servisinde ise hastalar geliş sırasına göre değil, durumlarının ciddiyetine göre alınır: bu, ağaç üzerine kurulu bir öncelik kuyruğudur. Bu derste ağaçların matematiğini ve en önemli iki türünü, ikili arama ağacını ve yığını öğreneceğiz.
İkili ağaçlar ve dolaşma
Her düğümün en fazla iki çocuğu (sol ve sağ) olan ağaç. En üstteki düğüm kök, çocuğu olmayan düğüm yapraktır. Bir düğümün derinliği kökten ona kadar olan kenar sayısı, ağacın yüksekliği h ise en büyük derinliktir.
- ndüğüm sayısı
- hağacın yüksekliği (kenar sayısıyla)
d derinliğinde en fazla 2ᵈ düğüm olabilir: 1 + 2 + 4 + … + 2ʰ = 2ʰ⁺¹ − 1. Yani n düğümlü bir ikili ağacın yüksekliği yaklaşık log₂ n'den küçük olamaz, ama n − 1'e kadar büyük olabilir.
50
/ \
30 70
/ \ / \
20 40 60 80
/
35| Dolaşma | Kural | Örnek ağaç için sonuç | Nerede kullanılır |
|---|---|---|---|
| Önce-kök (preorder) | kök, sol, sağ | 50 30 20 40 35 70 60 80 | ağacı kopyalamak |
| Ortada-kök (inorder) | sol, kök, sağ | 20 30 35 40 50 60 70 80 | anahtarları sıralı almak |
| Sonra-kök (postorder) | sol, sağ, kök | 20 35 40 30 60 80 70 50 | silme, klasör boyutu hesaplama |
| Düzey sırası | kuyrukla, yukarıdan aşağıya | 50 30 70 20 40 60 80 35 | en kısa yollar, düzeylere göre yazdırma |
İkili arama ağaçları (BST)
İkili arama ağacında her düğüm için sol alt ağaçtaki tüm anahtarlar ondan küçük, sağ alt ağaçtakiler büyüktür. Arama kökten başlar: anahtar küçükse sola, büyükse sağa gideriz; bu, ikili aramanın ağaç biçimidir. Ekleme de aynı yolu izleyerek boş bir yer bulur. İki işlem de O(h) sürer.
Örnek ağaçtan 30'u sil. Silmeden sonra ağacın ortada-kök dolaşması nasıl olur?
Çözümü gösterÇözümü gizle
30'un iki çocuğu var (20 ve 40). Sağ alt ağaç: 40 → 35. En küçüğü 35'tir (sola gidebildiğin kadar git).
30'un yerine 35 yazılır, 35 eski yerinden silinir (yapraktır).
Yeni ağaç: 50 → (35 → 20, 40), (70 → 60, 80).
Ortada-kök: 20 35 40 50 60 70 80; hâlâ artan sırada, BST özelliği korunmuş.
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def inorder(t):
return inorder(t.left) + [t.key] + inorder(t.right) if t else []
def preorder(t):
return [t.key] + preorder(t.left) + preorder(t.right) if t else []
def height(t):
return -1 if t is None else 1 + max(height(t.left), height(t.right))
root = chain = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, k)
for k in range(1, 9):
chain = insert(chain, k)
print('inorder: ', inorder(root))
print('preorder:', preorder(root))
print('height:', height(root), '| sorted input height:', height(chain))▸ Beklenen çıktı
inorder: [20, 30, 35, 40, 50, 60, 70, 80] preorder: [50, 30, 20, 40, 35, 70, 60, 80] height: 3 | sorted input height: 7
Çıkış yolu dengeli ağaçlardır: her ekleme ve silmeden sonra döndürmelerle (rotation) yüksekliği O(log n) tutarlar. AVL ağacında her düğümün sol ve sağ alt ağaçlarının yükseklikleri en fazla 1 farklıdır (h < 1,44 log₂ n); kırmızı-siyah ağaçta h ≤ 2 log₂(n + 1)'dir. Java TreeMap ve C++ std::map kırmızı-siyah ağaçtır; veri tabanı indeksleri ise her düğümde yüzlerce anahtar tutan B-ağaçlarıdır.
Yığınlar ve öncelik kuyrukları
Tam bir ikili ağaç (tüm düzeyler dolu, sonuncusu soldan sağa doldurulmuş) ve her düğüm çocuklarından küçük ya da onlara eşittir. Yani en küçük değer her zaman köktedir. Ağaç işaretçisiz, doğrudan bir dizide saklanır.
- idüğümün dizideki indeksi (0'dan)
Ağaç diziye düzey düzey yazılır; tam olduğu için boşluk kalmaz ve yüksekliği ⌊log₂ n⌋'dir.
Min-yığın: [3, 5, 8, 10, 7]. a) 2'yi ekle. b) Ardından en küçüğü çıkar. Her adımdan sonra diziyi yaz.
Çözümü gösterÇözümü gizle
parent(5) = 2'de 8 > 2 → değiştir → [3, 5, 2, 10, 7, 8].
parent(2) = 0'da 3 > 2 → değiştir → [2, 5, 3, 10, 7, 8]. Köke ulaştık.
b) Aşağı kaydırma (sift-down): kökteki 2 alınır, son eleman 8 köke taşınır → [8, 5, 3, 10, 7].
Çocuklar: 5 (i = 1) ve 3 (i = 2); küçüğü 3 → değiştir → [3, 5, 8, 10, 7].
i = 2'nin çocuğu yok (5 ve 6 indeksleri dizinin dışında) → [3, 5, 8, 10, 7], çıkarılan 2.
Her işlem en fazla h = ⌊log₂ n⌋ değiş tokuş yapar → O(log n).
import heapq
heap = [3, 5, 8, 10, 7]
heapq.heappush(heap, 2)
print(heap)
print(heapq.heappop(heap), heap)
patients = []
for urgency, name in [(3, 'Aysel'), (1, 'Murad'), (2, 'Leyla'), (1, 'Elvin')]:
heapq.heappush(patients, (urgency, name))
while patients:
print(heapq.heappop(patients))
def heap_sort(a):
h = a[:]
heapq.heapify(h)
return [heapq.heappop(h) for _ in range(len(h))]
print(heap_sort([9, 4, 7, 1, 8, 2]))▸ Beklenen çıktı
[2, 5, 3, 10, 7, 8] 2 [3, 5, 8, 10, 7] (1, 'Elvin') (1, 'Murad') (2, 'Leyla') (3, 'Aysel') [1, 2, 4, 7, 8, 9]
heapq modülü sıradan bir list üzerinde min-yığındır: sonuç elle yaptığımız izlemeyle aynıdır. Hastalar (aciliyet, ad) çiftleri olarak saklanır: küçük sayı daha acildir, eşitlikte adlar karşılaştırılır. heapify + n kez heappop = yığın sıralaması.- hdüğümün yapraklardan yüksekliği
- n / 2ʰ⁺¹n / 2ʰ⁺¹yüksekliği h olan düğüm sayısı (yaklaşık)
heapify bir diziyi aşağıdan yukarıya yığına çevirir: düğümlerin yarısı yapraktır (0 iş), dörtte biri 1 adım batar vb. ∑ h/2ʰ = 2 olduğundan toplam O(n log n) değil O(n)'dir. Yığın sıralaması ardından n çıkarmayla O(n log n) yapar.
| İşlem | Dengeli BST | Dengesiz BST (en kötü) | İkili yığın |
|---|---|---|---|
| herhangi bir anahtarı arama | O(log n) | O(n) | O(n) |
| ekleme | O(log n) | O(n) | O(log n) |
| en küçüğe bakmak | O(log n) | O(n) | O(1) |
| en küçüğü çıkarmak | O(log n) | O(n) | O(log n) |
| n elemandan kurmak | O(n log n) | O(n²) | O(n) |
Önemli noktalar
- n düğümlü bir ikili ağacın yüksekliği en az ≈ log₂ n, en fazla n − 1'dir.
- Önce-kök, ortada-kök ve sonra-kök dolaşmaları kökün yerini belirtir; BST'nin ortada-kök dolaşması anahtarları artan sırada verir.
- BST işlemleri O(h)'dir; dengeli ağaçlar (AVL, kırmızı-siyah, B-ağaçları) h = O(log n) tutar.
- Yığın dizide saklanan tam bir ağaçtır: çocuklar 2i + 1 ve 2i + 2'de; ekleme ve en küçüğü çıkarma O(log n), kurma O(n)'dir.
- Öncelik kuyruğu yığınla kurulur; yığın sıralaması O(n log n) ve yerindedir ama kararlı değildir.
Kendini test et
10 soru. Her doğru cevap XP kazandırır.