Za akých podmienok sa čas vyhľadávania v binárnom strome stáva nad logaritmický?

Čas vyhľadávania v binárnom strome je zvyčajne logaritmický (O(log n)), ak je strom vyvážený, teda výška stromu je úmerná logaritmu počtu uzlov. Ak však strom nie je vyvážený a degeneruje sa do štruktúry podobnej prepojenej zoznamu (napríklad, všetky uzly majú iba jedného potomka), výška stromu sa stáva lineárnou (O(n)). V takom prípade sa čas vyhľadávania zhoršuje na lineárny, čo prevyšuje logaritmický čas.

Príklad: ak pri sekvenčnom vkladaní zoradených dát do bežného binárneho vyhľadávacieho stromu sa neaplikuje vyváženie, strom sa premení na reťazec a vyhľadávanie bude fungovať v O(n).