Время поиска для двоичного дерева поиска

Question

Кто-нибудь знает, как определить время поиска для двоичного дерева поиска (то есть наихудший случай, лучший случай и средний случай)?

Answer 1

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

В этом случае вам нужно в среднем выполнить поиск по половине списка, прежде чем найти нужный элемент.

Наилучшим случаем является O (log ₂ n) для идеально сбалансированного дерева, поскольку вы сокращаете пространство поиска пополам для каждого уровня дерева.

Средний случай находится где-то посередине между этими двумя и полностью зависит от данных: -)

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

                 8
         _______/ \_______
        /                 \
       4                  12
    __/ \__             __/ \__
   /       \           /       \
  2         6        10        14
 / \       / \       / \       / \
1   3     5   7     9  11    13  15

В этом прекрасно сбалансированном дереве вы можете видеть, что вы получаете 2 ⁿ -1 узлов на каждый n уровень. Это означает, что для 15 узлов вам никогда не придется искать более четырех узлов, чтобы найти его (например, чтобы найти 13, вы будете искать 8, 12, 14 и 13). Отсюда и получается лог ₂ n.

Вырожденное несбалансированное дерево, как уже говорилось, является связанным списком. Если ваши данные поступили последовательно и вы вставили их в несбалансированное двоичное дерево, вы получите:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -+
                                           |
+------------------------------------------+
|
+-> 10 -> 11 -> 12 -> 13 -> 14 -> 15

Чтобы найти 13 в этом случае, вам нужно искать 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 и 13, следовательно, O (n).

Answer 2

Возможно, вы захотите пометить это как "домашнюю работу". Вот хорошая отправная точка: http://en.wikipedia.org/wiki/Binary_search_tree

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

Наихудший случай наиболее интересен, и его легко увидеть, если признать, что первый уровень двоичного дерева имеет 1 узел, второй - 2, третий - 4 и т. Д. Таким образом, число узлов в двоичном дереве глубиной n точно равно 2 ^ n - 1 . Математической инверсией экспоненциальной функции является логарифм, таким образом: O (log n) .

Несбалансированное дерево может быть таким же плохим, как и связанный список, и может иметь форму, подобную следующей:

  1
 / \
    2
   / \
      3
     / \
        4
       / \

В этой ситуации худшее время доступа составляет O (n) .

Answer 3

Лучший случай - O (1). Первым элементом может быть элемент, который вы ищете. наихудший случай - O (n), т. е. в перекошенном дереве, а средний - O (lg n).