Временная сложность создания сбалансированного бинарного дерева поиска?

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

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


algorithm data-structures heap avl-tree binary-search-tree
person AV94    schedule 10.12.2017    source источник
comment
(Временная сложность построения сбалансированного BST также зависит от входных данных: Ο(n) если ваши n входных элементов упорядочены (и, в зависимости от деталей, доступны случайным образом).)   -  person greybeard    schedule 10.12.2017

Ответы (1)


arrow_upward
2
arrow_downward

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

Если вы используете подход siftDown (снизу вверх), сложность будет O(n), а с siftUp будет O(nlogn), как и в BST.

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

Восходящий подход к построению кучи неприменим для BST, если входной список уже не отсортирован, но в этом случае у вас уже есть O(nlogn) сложность из-за сортировки.

person Miljen Mikic    schedule 10.12.2017
comment
@Mikic, вы не добавили изображение. - person AV94; 10.12.2017
comment
Понял. Спасибо :) - person AV94; 10.12.2017