Objasnite zašto algoritam pretraživanja u uravnoteženom stablu radi u vremenu proporcionalnom logaritmu veličine strukture podataka.

В сбалансированном дереве (например, красно-чёрном или AVL) высота дерева пропорциональна логарифму от количества элементов (n), то есть h = O(log n). Это достигается за счёт поддержания баланса, чтобы дерево не вырождалось в список.

Поиск в дереве — это последовательное сравнение искомого значения с текущим узлом и переход в левое или правое поддерево. За каждый шаг мы исключаем примерно половину оставшихся элементов.

Поскольку на каждом уровне количество рассматриваемых элементов уменьшается вдвое, количество шагов до нахождения элемента или определения его отсутствия — порядка log n.

Пример: если в дереве 1024 элемента, поиск займет примерно 10 сравнений (log₂1024 = 10).