Приведи пример худшего случая поиска в бинарных деревьях.

Худший случай поиска в бинарном дереве поиска (BST) возникает, когда дерево является вырожденным, то есть представляет собой по сути связный список. Это происходит при добавлении элементов в строго возрастающем или строго убывающем порядке.

Например, если элементы добавляются в порядке 1, 2, 3, 4, 5:

plaintext

или в порядке 5, 4, 3, 2, 1:

plaintext

В таком дереве поиск любого элемента превращается в последовательный перебор, аналогичный поиску в связном списке.

Время поиска в худшем случае: O(n), где n — количество узлов в дереве. Это эквивалентно линейному поиску в массиве или связном списке.

Пример поиска элемента 5 в первом случае:

1. Сравнение с корнем (1). 5 > 1, идем вправо.
2. Сравнение с узлом 2. 5 > 2, идем вправо.
3. Сравнение с узлом 3. 5 > 3, идем вправо.
4. Сравнение с узлом 4. 5 > 4, идем вправо.
5. Сравнение с узлом 5. Найдено.

Пять сравнений для дерева из пяти узлов.

Для сравнения, в сбалансированном бинарном дереве поиска (например, красно-черном дереве или AVL-дереве) поиск занимает O(\log n) времени в худшем случае.