Поиск стоимости в двоичном дереве?

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

2012-03-26 Nethre

Хотя дан ответ, однако, вы могли бы легко получили ответ на ваш вопрос, если бы вы набрали свой вопрос в окне поиска в Google или Stack Overflow. – Yavar

Вы имеете в виду двоичное ** поиск ** дерево? – svick

 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)

источник

2012-03-26 11:37:45

@AndreasBrinck, Когда у вас вырожденное дерево (другими словами, каждый узел имеет только 1 ребенка). Итак, мы можем считать, что дерево стало связанным списком. –

Да, я глупо просто прочитал вопрос как бинарный поиск (в массиве). Сожалею. –

Средний чехол для поиска элемент: O (журнал N)

Худший случай: O (п)

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

источник

2012-03-26 11:38:20 Yavar

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

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

источник

2012-03-26 12:06:15 Algorist

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

источник

2016-03-14 12:41:15

Поиск стоимости в двоичном дереве?

ответ

Смежные вопросы