Ağaçlar, hiyerarşik veri yapılarıdır ve birçok bilgisayar bilimi uygulamasında kullanılır.
İkili Arama Ağaçları (Binary Search Trees - BST)
Her düğümün en fazla iki çocuğu olan ve sol alt ağaçtaki tüm değerlerin düğümden küçük, sağ alt ağaçtaki tüm değerlerin düğümden büyük olduğu ağaç yapısıdır.
Temel Operasyonlar:
- Arama: O(log n) ortalama, O(n) en kötü
- Ekleme: O(log n) ortalama, O(n) en kötü
- Silme: O(log n) ortalama, O(n) en kötü
AVL Ağaçları
Kendini dengeleyen ikili arama ağacıdır. Her düğümde, sol ve sağ alt ağaçların yükseklikleri arasındaki fark en fazla 1'dir.
Avantajları:
- Garantili O(log n) performans
- Otomatik dengeleme
- Arama yoğun uygulamalar için ideal
Kırmızı-Siyah Ağaçlar
Her düğümün kırmızı veya siyah renkli olduğu, belirli kurallara göre dengelenen ikili arama ağacıdır.
Kurallar:
- Kök düğüm siyahtır
- Tüm yapraklar (NIL) siyahtır
- Kırmızı düğümün çocukları siyahtır
- Her yolda aynı sayıda siyah düğüm vardır