Каково наихудшее время выполнения поиска элемента в сбалансированном двоичном дереве поиска с n * 2 ^ n элементами?

Question

Я знаю, что поиск сбалансированного дерева с n узлами - это O (logN) ，, но я даже не знаю, почему дерево, указанное в вопросе, также является сбалансированным BST.

Answer 1

Ну, как вы сказали, сбалансированный BST с k имеет время поиска O (log k). Итак, все, что нам нужно сделать, это подключить n2 ⁿ для k, чтобы увидеть, что мы получим:

log (n2 ⁿ )

= log n + log 2 ⁿ

= log n + n log 2

= O (n).

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