Бинарлы ағаштарда іздеу күрделілігі әрқашан логарифмдік пе?

Жоқ, әрқашан емес. Бинарлы ағашта іздеу қиындығы оның биіктігіне байланысты.

• теңдестірілген бинарлы ағашта (мысалы, AVL ағашы немесе қызыл-сұр ағашы) биіктігі log(n)-ға пропорционал, мұнда n - түйіндердің саны. Бұл жағдайда іздеудің қиындығы логарифмдік, O(log n).

• теңдестірілмеген бинарлы ағашта биіктік сызықтыққа дейін ұлғаюы мүмкін, ең нашар жағдайда n-ға дейін (мысалы, элементтер қатаң өсіп немесе азая отырып енгізілсе, тізім құрып). Бұл жағдайда іздеудің қиындығы сызықтық, O(n).

Осылайша, логарифмдік қиындығы теңдестірілген бинарлы ағаштар үшін кепілденген.