Veri Yapıları #08 | Ağaçlar: İkili Arama Ağacı — Arama, Ekleme, Gezinme ve Silme

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

Veri Yapıları dersinin sekizinci videosu. Bir milyon sayı arasında bin rastgele arama yapıyoruz: sıralı bağlı listede ortalama 517 768 karşılaştırma gerekiyor, aynı sayıları karışık sırayla ikili arama ağacına koyunca ortalama 27. Bu ağacı birlikte kuruyoruz. Ağaçta bir düğümün birden çok çocuğu olabilir: kök, çocuk, ebeveyn, yaprak ve kardeş kavramlarıyla başlıyor, N düğümlü ağaçta neden tam N − 1 kenar olduğunu görüyoruz. Derinlik (kökten düğüme giden yoldaki kenar sayısı) ve yükseklik (düğümden en uzak yaprağa giden yol) örnek bir ağaçta adım adım hesaplanıyor. İkili ağacın düğümü bir değer ve iki işaretçiden oluşur: 4 bayt değer, 4 bayt dolgu, 8'er baytlık sol ve sağ, toplam 24 bayt. İkili arama ağacında her düğümün solunda küçükler, sağında büyükler durur; arama kökten başlayıp her adımda bir yöne gider: 60 üç karşılaştırmada bulunur, 65 için NULL'a varılır. Ekleme aynı yolu izler ve yeni değer yaprak olur; özyinelemeli ekleme fonksiyonunun dönüş zincirini satır satır takip ediyoruz. Üç gezinme (kök ortada, kök önce, kök sonda) gerçek çıktılarla gösteriliyor: kök ortada gezinme değerleri sıralı verir, yükseklik de kök sonda hesaplanır. Silmenin üç durumu: yaprak, tek çocuklu düğüm ve sağ alt ağacın en küçüğüyle değiştirilen iki çocuklu düğüm. Son olarak ağacın şeklinin geliş sırasına bağlı olduğunu ölçüyoruz: bin değer karışık sırayla gelince yükseklik 19, sıralı gelince 999. Ekrandaki her çıktı, kodun gerçekten derlenip çalıştırılmasından geliyor. Bu derste: 1. Ağaç kavramları: kök, çocuk, yaprak, kardeş; N düğüm, N − 1 kenar 2. Derinlik ve yükseklik 3. İkili ağaç düğümü (24 bayt) ve ikili arama ağacının kuralı 4. Arama, ekleme (özyineleme) ve silmenin üç durumu 5. Üç gezinme ve ağacın şeklinin ekleme sırasına bağlılığı Bölümler: 0:00 Ağaç: birden çok çocuk 0:27 Bir milyon sayıda arama 0:49 Derinlik ve yükseklik 1:20 İkili ağacın düğümü 1:38 Arama: küçükse sola, büyükse sağa 2:07 Ekleme ve özyineleme 2:40 Üç gezinme 3:39 Silmenin üç durumu 4:24 Şekil, geliş sırasına bağlı 5:00 Bugünün dört kuralı 5:21 Sonraki ders: AVL ağacı Kaynak kitap: Mark Allen Weiss — Data Structures and Algorithm Analysis in C++, 4. baskı (2014), §4.1–4.3 ve §4.6 (ağaç kavramları ve gezinmeler, ikili ağaçlar, ikili arama ağacı: arama, en küçük/en büyük, ekleme, silme, ortalama durum). 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 3.–7. dersleri (bağlı liste, yığın, kuyruk).

Bu videoyu izlemek için Premium üyelik gerekir.