Veri Yapıları #09 | AVL Ağacı: Denge Kuralı, Tek ve Çift Döndürme

Eğitmen: Dr. Süleyman Burak ÇELİK

Veri Yapıları dersinin dokuzuncu videosu. 1'den 1000'e sıralı değerleri iki ağaca ekliyoruz: düz ikili arama ağacının yüksekliği 999, AVL ağacının yalnızca 9. Aradaki tek fark, her eklemeden sonra yapılan küçük bir düzeltme. AVL ağacı, her düğümde sol ve sağ alt ağacın yüksekliklerinin en fazla 1 farklı olmasını isteyen bir ikili arama ağacıdır (boş alt ağacın yüksekliği −1). Denge değerini (sol yükseklik eksi sağ yükseklik) 1, 2, 3 zincirinde adım adım hesaplıyor, kökte −2 ile kuralın bozulduğunu görüyoruz. Her düğüm kendi yüksekliğini saklar: yükseklik alanı önceki derste dolgu olarak boş kalan 4 baytın yerine oturur, düğüm yine 24 bayttır. Tek döndürmeyi sola_dondur fonksiyonunun satırlarını izleyerek yapıyoruz: yalnızca iki işaretçi değişir, sıra bozulmaz. 3, 1, 2 sırasında ağırlık içeride kaldığı için çift döndürme gerekir: önce çocuk, sonra düğüm. Dört dengesizlik durumunu ve dengele fonksiyonunu görüyor, geçen dersin sıralı 1..7 dizisini AVL ağacına verip her döndürmeyi gerçek izle takip ediyoruz: sonuç yüksekliği 2 olan tam dengeli bir ağaç. Son olarak bir milyon değerde ölçüyoruz: sıralı eklemede yükseklik 19, karışık eklemede 23; ikisi de kitaptaki yaklaşık 27'lik sınırın altında. Ekrandaki her çıktı, kodun gerçekten derlenip çalıştırılmasından geliyor. Bu derste: 1. AVL denge kuralı ve denge değerinin adım adım hesabı 2. Düğümde yükseklik: yine 24 bayt 3. Tek döndürme (sola_dondur satır satır) ve çift döndürme 4. Dört dengesizlik durumu ve dengele fonksiyonu 5. 1..7 sıralı eklemenin izi; bir milyon değerde yükseklik ve kitaptaki sınır Bölümler: 0:00 Dengeli bir ağaç 0:17 1'den 1000'e sıralı: 999 ve 9 0:37 Denge kuralı 1:19 Düğüm yüksekliğini saklar 1:42 Tek döndürme 2:26 Çift döndürme 2:55 Dört durum ve dengele 3:29 1'den 7'ye, bu kez AVL 4:03 Ne kadar yüksek? 4:33 Bugünün dört kuralı 4:54 Sonraki ders: çizgeler Kaynak kitap: Mark Allen Weiss — Data Structures and Algorithm Analysis in C++, 4. baskı (2014), §4.4 (AVL ağaçları: denge koşulu, yüksekliğin düğümde saklanması, en derin dengesiz düğümde düzeltme, dört durum, tek ve çift döndürme, yükseklik sınırı). Konu sırası ve kavramlar kaynak kitaptan izlenir; programlar ve örnekler C ile özgün yazıldı, anlatım ve ekranlar özgündür. Hedef kitle: veri yapılarına başlayan mühendislik ve bilgisayar/yazılım öğrencileri. Ön koşul: temel C, özyineleme ve bu serinin 8. dersi (ikili arama ağacı).