İkili ağaçta arama süresi hangi koşullarda logaritmik süreden büyük olur?

İkili ağaçta arama süresi genellikle logaritmik (O(log n)) olup, ağaç dengelenmişse, yani ağacın yüksekliği düğüm sayısının logaritmasına orantılıysa geçerlidir. Ancak, ağaç dengesizse ve bağlı listeye benzeyen bir yapıya dönüşüyorsa (örneğin, tüm düğümler sadece bir çocuğa sahipse), ağacın yüksekliği doğrusal hale gelir (O(n)). Bu durumda, arama süresi doğrusal hale gelir ve logaritmik süreden daha kötü olur.

Örnek: Sıralı verilerin ardışık eklenmesiyle normal bir ikili arama ağacına dengeleme uygulanmazsa, ağaç zincir haline gelir ve arama O(n) süresinde gerçekleşir.