Стоимость операции поиска в двоичном дереве?

Question

Сколько стоит операция поиска в двоичном дереве?Это O (n)?

Answer 1

        Average     Worst case
Space   O(n)        O(n)
Search  O(log n)    O(n)
Insert  O(log n)    O(n)
Delete  O(log n)    O(n)

Answer 2

Да, это O (n), поскольку это двоичное дерево, а НЕ двоичное дерево поиска.

Поскольку невозможно определить, в каком направлении (влево или вправо) разветвляться в «двоичном дереве», мы должны выполнить поиск по всему дереву в худшем случае.

Answer 3

Среднее значение для поиска элемента: O (log n)

Наихудшее значение: O (n)

Вы можете проверить наличие сбалансированных деревьев (AVL, Red Black), если вам нужнолучшие (логарифмические) наихудшие случаи с запущенными сложностями.

Answer 4

Согласно книге "Введение в анализ алгоритмов" Роберта Седжвика, если это двоичное дерево построено случайной перестановкой размера N, то средний успешный поиск составляет 2H_N - 3 + 2H_N / N = 2ln (N)+ O (1), и среднее значение неудачного поиска составляет 2H_ {N + 1} - 2 = 2ln (N) + O (1).

Answer 5

да Это будет O (n), потому что у вас нет условий сортировки в этом дереве, например, в дереве бинарного поиска, поэтому вам нужно пройти по всему дереву, как массив