Kendini dengeleyen ağaçlar: AVL ve kırmızı-siyah ağaç

Kısaca: Ekleme ve silmeden sonra kendilerini yeniden kuran arama ağaçları; böylece uzun bir zincire dönüşmezler ve işlemler hızlı kalır.

Biraz daha ayrıntılı: Bir ikili arama ağacı dengeliyse değerleri O(log n)‘de bulur. Ama sıralı veri eklerseniz (1, 2, 3, 4, …) O(n) çabalı uzun bir “zincir” ortaya çıkar. Kendini dengeleyen ağaçlar bu dengesizliği algılar ve dengeyi döndürmelerle yeniden kurar.