--- title: 'Dengeli Arama Ağaçları' source: 'https://academia.sh/tr/kurslar/veri-yapilari/dengeli-arama-agaclari' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:08:00+00:00' license: 'CC BY-SA 4.0' --- # Dengeli Arama Ağaçları Dönme işlemi, AVL denge ölçütü ve dört durum, kırmızı–siyah ağaçların renk değişmezleri ve iki ailenin karşılaştırması. Önceki ders bir sorunla bitti: ikili arama ağacının yüksekliği, ekleme sırasına bağlıdır ve sıralı girdi ağacı bağlı listeye çevirir. Çözüm, ağacı her değişiklikten sonra denetlemek ve dengesizlik oluştuğunda **yeniden düzenlemektir**. Bu dersin konusu, düzenlemeyi yapan işlem ve onu ne zaman uygulayacağını söyleyen iki klasik kural kümesidir. ## Dönme **Dönme (rotation)**, bir bağı yeniden yönlendirerek ağacın yüksekliğini değiştiren yerel bir işlemdir. En önemli özelliği, **sıralama değişmezini bozmamasıdır.** ``` sağa dönme (y ekseninde) sola dönme (y) (x) (x) (y) / \ / \ / \ / \ (x) C → A (y) A (y) → (x) C / \ / \ / \ / \ A B B C B C A B ``` Sağa dönmede `x` yukarı, `y` aşağı iner; `B` alt ağacı `x`'in sağından `y`'nin soluna geçer. Sıralama açısından hiçbir şey değişmez: `A < x < B < y < C` ilişkisi her iki biçimde de geçerlidir. Değişen tek şey yüksekliktir. Dönme sabit sayıda bağ yazar; maliyeti $O(1)$'dir. ```python class DugumAVL: def __init__(self, deger: int) -> None: self.deger = deger self.sol: "DugumAVL | None" = None self.sag: "DugumAVL | None" = None self.yukseklik = 0 # yaprak: 0 def h(dugum: DugumAVL | None) -> int: return -1 if dugum is None else dugum.yukseklik def guncelle(dugum: DugumAVL) -> None: dugum.yukseklik = 1 + max(h(dugum.sol), h(dugum.sag)) def denge(dugum: DugumAVL | None) -> int: """Sol yükseklik eksi sağ yükseklik.""" return 0 if dugum is None else h(dugum.sol) - h(dugum.sag) def saga_dondur(y: DugumAVL) -> DugumAVL: x = y.sol y.sol = x.sag # B alt ağacı yer değiştirir x.sag = y guncelle(y); guncelle(x) # önce alttaki güncellenir return x # yeni kök def sola_dondur(x: DugumAVL) -> DugumAVL: y = x.sag x.sag = y.sol y.sol = x guncelle(x); guncelle(y) return y ``` Yükseklik güncellemesinin sırası önemlidir: aşağıdaki düğüm önce güncellenmelidir, çünkü üsttekinin yüksekliği ona bağlıdır. ## AVL Ağacı **AVL ağacı**, her düğümde şu koşulu zorunlu kılar: > Sol ve sağ alt ağaçların yükseklik farkı en fazla birdir. Bu fark, düğümün **denge çarpanıdır**. Değeri $-1$, $0$ veya $+1$ olmalıdır; $\pm 2$ olduğunda dengesizlik vardır ve düzeltilir. Koşul katıdır ve karşılığında sıkı bir yükseklik sınırı verir: $n$ düğümlü bir AVL ağacının yüksekliği $1{,}44 \log_2 n$'i aşmaz. Arama, ekleme ve silme bu nedenle her zaman $O(\log n)$'dir — dejenere durum olanaksızdır. ## Dört Durum Ekleme sonrası dengesizlik dört biçimde ortaya çıkar. Adları, dengesiz düğümden itibaren eklenen düğüme giden yolu tarif eder. | Durum | Belirti | Çözüm | |---|---|---| | Sol–sol | Denge $> 1$, sol çocuğun dengesi $\geq 0$ | Sağa dönme | | Sağ–sağ | Denge $< -1$, sağ çocuğun dengesi $\leq 0$ | Sola dönme | | Sol–sağ | Denge $> 1$, sol çocuğun dengesi $< 0$ | Sol çocuğu sola döndür, sonra sağa dönme | | Sağ–sol | Denge $< -1$, sağ çocuğun dengesi $> 0$ | Sağ çocuğu sağa döndür, sonra sola dönme | Son iki durumda tek dönme yetmez: dengesizlik "zikzak" biçimindedir ve önce düzleştirilir, sonra düzeltilir. ```python def ekle_avl(kok: DugumAVL | None, deger: int) -> DugumAVL: if kok is None: return DugumAVL(deger) if deger < kok.deger: kok.sol = ekle_avl(kok.sol, deger) elif deger > kok.deger: kok.sag = ekle_avl(kok.sag, deger) else: return kok # yinelenen değer guncelle(kok) d = denge(kok) if d > 1 and denge(kok.sol) >= 0: # sol–sol return saga_dondur(kok) if d < -1 and denge(kok.sag) <= 0: # sağ–sağ return sola_dondur(kok) if d > 1: # sol–sağ kok.sol = sola_dondur(kok.sol) return saga_dondur(kok) if d < -1: # sağ–sol kok.sag = saga_dondur(kok.sag) return sola_dondur(kok) return kok def ic_sirali(dugum, sonuc=None): sonuc = [] if sonuc is None else sonuc if dugum is not None: ic_sirali(dugum.sol, sonuc) sonuc.append(dugum.deger) ic_sirali(dugum.sag, sonuc) return sonuc # Sıralı ekleme: sade arama ağacında dejenere olurdu. kok = None for deger in (3, 7, 10, 12, 25, 30): kok = ekle_avl(kok, deger) print(ic_sirali(kok)) # [3, 7, 10, 12, 25, 30] print(kok.deger) # 12 — kök kendiliğinden ortaya yerleşti print(h(kok)) # 2 — dejenere ağaçta 5 olurdu ``` Altı değerin artan sırada eklenmesi, önceki derste yüksekliği beş olan bir zincir üretiyordu. AVL kuralı aynı girdide yüksekliği ikide tutar; dönmeler ekleme sırasında kendiliğinden çalışmıştır. Bir eklemeden sonra en fazla **bir** dönme (veya çift dönme) gerekir; yükseklik güncellemeleri ise kökten aşağı olan yol boyunca yapılır. Ekleme maliyeti bu nedenle $O(\log n)$ kalır. ## Kırmızı–Siyah Ağaçlar İkinci klasik aile, dengeyi yüksekliklerle değil **renklerle** izler. Her düğüm kırmızı veya siyah boyanır ve dört değişmez korunur: 1. Kök siyahtır. 2. Kırmızı bir düğümün çocukları siyahtır — iki kırmızı düğüm ardışık olamaz. 3. Kökten herhangi bir boş bağa giden tüm yollarda aynı sayıda siyah düğüm bulunur. 4. Boş bağlar siyah sayılır. Üçüncü koşul, ağacın "siyah yükseklik" açısından mükemmel dengeli olmasını sağlar. En uzun yol, en kısa yolun en fazla iki katı olabilir — çünkü en uzun yol kırmızı ve siyahın dönüşümlüsü, en kısa yol tümüyle siyahtır. Buradan yükseklik sınırı çıkar: $$ h \leq 2 \log_2 (n + 1) $$ AVL'nin $1{,}44 \log_2 n$ sınırından daha gevşektir; ağaç biraz daha derin olabilir. Karşılığında, dengeyi korumak için gereken yeniden düzenleme sayısı azdır: ekleme ve silmede sabit sayıda dönme yeterlidir, AVL'de ise silme sırasında kök yoluna kadar dönme zinciri oluşabilir. ## İki Aileyi Seçmek | Ölçüt | AVL | Kırmızı–siyah | |---|---|---| | Yükseklik sınırı | $\approx 1{,}44 \log_2 n$ | $\approx 2 \log_2 n$ | | Arama | Biraz daha hızlı | Biraz daha yavaş | | Ekleme/silme | Daha çok dönme | Daha az dönme | | Uygun kullanım | Okuma ağırlıklı | Yazma ağırlıklı | Genel amaçlı kütüphanelerin sıralı eşleme ve sıralı küme yapıları çoğunlukla kırmızı–siyah ağaç kullanır: güncelleme maliyetinin daha öngörülebilir olması, genel kullanımda arama farkından daha değerlidir. Her iki ailenin de ortak bedeli, kod karmaşıklığıdır. Silme durumları özellikle çoktur ve elle yazılan gerçekleştirimlerde hata kaynağıdır. Doğrusal yapılar konusundaki atlama listesi, aynı beklenen maliyeti çok daha kısa kodla verdiği için bir alternatiftir — farkı, güvencenin beklenen olması ve kesin olmamasıdır. ## Özet - Dönme, bağları yeniden yönlendirerek yüksekliği değiştiren ve sıralama değişmezini koruyan sabit maliyetli bir işlemdir. - AVL ağacında her düğümün denge çarpanı $-1$, $0$ veya $+1$ olmalıdır; ihlal dört durumdan biriyle giderilir. - Zikzak biçimli dengesizlikler (sol–sağ, sağ–sol) önce tek dönmeyle düzleştirilir. - AVL yükseklik sınırı yaklaşık $1{,}44 \log_2 n$'dir; dejenere durum olanaksızdır. - Kırmızı–siyah ağaç dengeyi renk değişmezleriyle izler; sınırı daha gevşektir ama güncellemede daha az dönme gerektirir. - Okuma ağırlıklı yükte AVL, yazma ağırlıklı yükte kırmızı–siyah tercih edilir. ## Sonraki Adım İkili ağaçlarda denge, dönmelerle sonradan onarılıyor. Farklı bir yaklaşım, düğüm başına birden çok anahtar tutup ağacın **tüm yapraklarını aynı derinlikte** tutmaktır. Sonraki ders bu fikri kuran 2-3 ağaçlarını ele alacak.