Unter welchen Bedingungen übersteigt die Suchzeit in einem binären Baum logarithmisch?

Время поиска в бинарном дереве обычно логарифмическое (O(log n)) при условии, что дерево сбалансировано, то есть высота дерева пропорциональна логарифму от количества узлов. Однако, если дерево несбалансировано и вырождается в структуру, похожую на связный список (например, все узлы имеют только одного потомка), высота дерева становится линейной (O(n)). В этом случае время поиска ухудшается до линейного, что превосходит логарифмическое время.

Пример: если при последовательной вставке отсортированных данных в обычное бинарное дерево поиска не применяется балансировка, дерево превратится в цепочку, и поиск будет работать за O(n).