Milyen feltételek mellett válik a bináris fa keresési ideje meghaladja a logaritmikus értéket?

A bináris fa keresési ideje általában logaritmikus (O(log n)), feltéve, hogy a fa kiegyensúlyozott, azaz a fa magassága arányos a csomópontok számának logaritmusával. Azonban, ha a fa kiegyensúlyozatlan és egy láncszerű struktúrává degenerálódik (például, minden csomópontnak csak egy leszármazottja van), akkor a fa magassága lineárissá válik (O(n)). Ebben az esetben a keresési idő lineárissá válik, meghaladva a logaritmikus időt.

Példa: ha sorozatosan rendezett adatok beszúrásakor nem alkalmazunk kiegyensúlyozást egy normál bináris keresőfába, a fa lánccá alakul, és a keresés O(n) idő alatt működik.