İkili ağacda axtarış vaxtı hansı şərtlərdə logaritmikdən çox olur?

İkili ağacda axtarış vaxtı adətən logarifmik (O(log n)) olur, şərt odur ki, ağac balanslı olsun, yəni ağacın hündürlüyü düyümlərin sayının logaritminə proporsional olsun. Ancaq, əgər ağac balanssızdırsa və əlaqəli siyahıya bənzər bir quruluşa çevrilərsə (məsələn, bütün düyümler yalnız bir övladına malikdirsə), ağacın hündürlüyü xətti (O(n)) olur. Bu halda, axtarış vaxtı xətti şəkildə pisləşir və logarifmik vaxtdan çox olur.

Nümunə: əgər ardıcıl olaraq sıralanmış məlumatların daxil edilməsi zamanı balanslaşdırma tətbiq olunmazsa, ağac zəncirə çevrilər və axtarış O(n) vaxtında işləyər.