Дайте пример за най-лошия случай на търсене в двоични дървета.

Най-лошият случай на търсене в двоично дърво за търсене (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)$ в най-лошия случай.