Может ли существовать сбалансированное двоичное дерево, не являющееся сбалансированным двоичным деревом поиска? Какова временная сложность?

Может ли существовать сбалансированное двоичное дерево, не являющееся сбалансированным двоичным деревом поиска? Если да, то какова бы сложность времени заключалась в поиске узла в таком дереве.Может ли существовать сбалансированное двоичное дерево, не являющееся сбалансированным двоичным деревом поиска? Какова временная сложность?

Мое понимание таково:

Binary Tree: любой узел имеет два высших узлов листа. Поиск в двоичном дереве с использованием DFS или BFS - O | V + E |
Двоичное дерево поиска: BST - дерево упорядоченных узлов. Поиск в двоичном дереве поиска с использованием DFS - O | log n |
Сбалансированное дерево (при условии сбалансированного по высоте): Максимальное количество уровней ниже корня сохраняется до минимума. Имеет ли равновесие какое-либо влияние на временную сложность поиска?

Таким образом, я могу создать двоичное дерево, сбалансированное по высоте, но не упорядоченное. Будет ли время поиска этого дерева O | V + E | или это будет лучше?

источник

2015-07-28 archie

Возможно, http://cs.stackexchange.com/ было бы лучше для вашего вопроса – Rod

Это не DFS (или BFS) при поиске упорядоченного дерева. «F» означает «First», подразумевая, что есть хотя бы один другой вариант, но нет выбора, который можно сделать с упорядоченными деревьями. Вы точно знаете путь. – ikegami

@ikegami hmm, так что вы говорите, что вам не нужно выбирать алгоритм поиска, основываясь на очереди или на основе стека (первая часть), поскольку вы проходите на основе порядка. – archie

Поиск неупорядоченного бинарного дерева требует посещений каждого узла, так что это O (N), является ли это сбалансированным

  50 
     __/ \__ 
    /  \ 
    25   26 
/\  /\ 
49 46 48 47

или не

Там действительно нет смысла балансировать неупорядоченное дерево.

источник

2015-07-28 17:31:42 ikegami

Заметим, что O (| V | + | E |) = O (| V |), потому что | E | = | V | -1 в случае дерева –

(... если говорить «внутренние края» (не-нильские ссылки/указатели) или _binary_ деревья (деревья ограниченной степени)) – greybeard

@NiklasB. | E | = | V | -1, потому что дерево является связным графом, то O (2 | V | -1) приближается к O (V) правильно. http://math.stackexchange.com/questions/457042/prove-that-a-connected-graph-with-n-vertices-has-at-least-n-1-edges – archie

Может ли существовать сбалансированное двоичное дерево, не являющееся сбалансированным двоичным деревом поиска? Какова временная сложность?

ответ

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