AVL ağacı
İlk kendini dengeleyen ikili arama ağacı: Adelson-Velsky ve Landis (1962). Her düğüm, çocukları arasındaki yükseklik farkını ≤ 1 tutar.
Denge ekleme/silmede bozulabilir; rotasyonlarla (tek ya da çift) onarılır. Her işlem için O(log n) garanti eder. Kırmızı-siyah ağaçlardan daha katı dengelidir; aramalar daha hızlı, güncellemeler daha pahalıdır.
İdeal alan: okuma ağırlıklı iş yükleri. Rakipleri: kırmızı-siyah ağaç (daha gevşek, güncellemede daha iyi; Linux çekirdeği bunu kullanır), B-ağacı (disk için), skip list’ler.