Ağaçlar
Hiyerarşiler, dengeleme ve sorgular
İkili Arama Ağacı
Her sol alt ağacın daha küçük, her sağ alt ağacın daha büyük olduğu sıralı ağaç — ekleme, arama ve silme tek bir kök-yaprak yolunu izler.
Süre O(h) · Alan O(n)
AVL Ağacı
Kendini dengeleyen bir İAA: her eklemeden sonra denge faktörlerini kontrol eder ve yükseklik O(log n) kalsın diye döndürür.
Süre O(log n) · Alan O(n)
İkili Yığın
Dizide saklanan tam ikili ağaç; ekleme bir değeri yukarı süzer, çıkarma son elemanı aşağı indirerek maksimum yığın düzenini korur.
Süre O(log n) · Alan O(n)
Trie (Önek Ağacı)
Karakterlerle anahtarlanan ağaç: her kök-düğüm yolu bir önek yazar, böylece ekleme ve arama yalnızca kelime uzunluğu kadar maliyetlidir.
Süre O(L) · Alan O(Σ · N)
Segment Ağacı
Dizi aralıkları üzerinde bir ikili ağaç: her düğüm bir toplam saklar, böylece aralık sorguları O(log n) kapsayıcı düğümü birleştirerek O(log n)'de çözülür.
Süre O(log n) query · Alan O(n)