Arama Ağaçları
Arama ağaçları, sıralı anahtarları hiyerarşik bir yapıda saklamaktadır; böylece arama, ekleme ve silme işlemleri kökten yaprağa doğru bir yolu izlemektedir. Kendi kendini dengeleyen varyantları, logaritmik zamanlı işlemleri garanti etmek için bu yolu kısa tutmaktadır.
Tanım
Bir arama ağacı, anahtarları düğüm başına bir sıralama değişmezine göre sıralı tutan, verimli arama, ekleme, silme ve sıralama tabanlı sorguları destekleyen ağaç yapılı bir veri yapısıdır; dengeli bir arama ağacı ayrıca şeklini, yüksekliğin anahtar sayısına göre logaritmik kalmasını sağlayacak şekilde kısıtlamaktadır.
Kapsam
Bu kapsam, ağaç tabanlı sıralı sözlük yapılarını ele almaktadır: ikili arama ağacı ve sıralama değişmezi, yüksekliği sınırlayan kendi kendini dengeleyen şemalar (AVL, kırmızı-siyah ve diğerleri) ve harici depolama için tasarlanmış B-ağaçları gibi çok yollu dengeli ağaçlar. Bu yapılar tarafından basit aramanın ötesinde desteklenen işlemleri — öncül, ardıl, aralık sorguları ve sıralı geçiş — ele almakta ve bunları sırayı korumayan hash tablolarıyla karşılaştırmaktadır.
Temel sorular
- İkili arama ağacı sıralama değişmezi, aramayı nasıl kökten yaprağa doğru bir yürüyüş haline getirmektedir?
- Dengesiz bir ağaç neden doğrusal zamana düşebilmekte ve dengeleme bunu nasıl önlemektedir?
- AVL ve kırmızı-siyah ağaçları dengede tutan dönüşler veya yapısal kurallar nelerdir?
- B-ağaçları neden ikili ağaçlar yerine disk ve veritabanı depolaması için daha uygundur?
- Sıra koruyucu işlemler, bir hash tablosuna göre ek maliyete ne zaman değmektedir?
Anahtar kavramlar
- ikili arama ağacı değişmezi
- ağaç dönüşleri
- AVL trees
- kırmızı-siyah ağaçlar
- B-trees
- ağaç yüksekliği ve denge
- sıralı geçiş
- aralık ve ardıl sorguları
Temel kuramlar
- Yükseklik dengeleme logaritmik işlemleri garanti etmektedir
- Dönüşler veya yapısal kurallar aracılığıyla bir denge değişmezini koruyarak, kendi kendini dengeleyen ağaçlar yüksekliği O(log n) seviyesinde tutmakta, giriş sırasından bağımsız olarak en kötü durumda O(log n) arama, ekleme ve silme işlemlerini garanti etmektedir.
- Harici bellek için çok yollu ağaçlar
- B-ağaçları, disk bloğu boyutlarına uyacak şekilde düğüm başına birçok anahtar depolamakta, yavaş harici bellek erişimlerinin sayısını en aza indirmektedir; bu da onları veritabanları ve dosya sistemleri için standart yapı haline getirmektedir.
Klinik önem
Arama ağaçları, sıralı erişime ihtiyaç duyan sistemler için merkezi bir öneme sahiptir: kırmızı-siyah ağaçlar standart kütüphanelerde sıralı haritaları ve kümeleri uygulamaktadır, B-ağaçları ve varyantları ilişkisel veritabanlarında ve dosya sistemlerinde baskın indeks yapısıdır ve dengeli ağaçlar aralık sorgularını, aralık zamanlamayı ve geometrik arama yapılarını desteklemektedir.
Tarihçe
İlk kendi kendini dengeleyen ikili arama ağaçları olan AVL ağaçları, 1962 yılında Adelson-Velsky ve Landis tarafından tanıtılmıştır. Bayer ve McCreight, 1972 yılında büyük sıralı indeksler için B-ağaçlarını tanıtmış, kırmızı-siyah ağaçlar ise 1978 yılında Guibas ve Sedgewick tarafından pratik bir dengeleme şeması olarak geliştirilmiş ve birçok standart kütüphane uygulamasının temelini oluşturmuştur.
Öne çıkan isimler
- Georgy Adelson-Velsky
- Evgenii Landis
- Rudolf Bayer
- Robert Sedgewick
- Robert Tarjan
İlgili konular
Temel eserler
- bayer1972
- cormen2009
Sıkça sorulan sorular
- Neden her zaman bir arama ağacı yerine bir hash tablosu kullanılmamaktadır?
- Hash tabloları ortalama olarak daha hızlı arama sağlamakta ancak sıralama yapmamaktadır. Arama ağaçları anahtarları sıralı tutarak, hash tablolarının verimli bir şekilde yapamadığı aralık sorgularını, sıralı yinelemeyi ve O(log n) sürede öncül/ardıl aramalarını mümkün kılmaktadır. Seçim, sıranın önemli olup olmadığına bağlıdır.
- Veritabanları neden ikili arama ağaçları yerine B-ağaçları kullanmaktadır?
- B-ağaçları, bir disk bloğunun boyutuna uyacak şekilde her düğüme birçok anahtar sığdırmaktadır; bu nedenle bir arama, aynı anahtar sayısına sahip bir ikili ağaca göre çok daha az yavaş harici bellek bloğuna dokunmaktadır. Bu durum, veritabanları ve dosya sistemlerinde performansa hakim olan G/Ç'yi en aza indirmektedir.