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

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

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

    1
     \
      2
       \
        3
         \
          4
           \
            5

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

        5
       /
      4
     /
    3
   /
  2
 /
1

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

Время поиска в худшем случае: $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)$ времени в худшем случае.