Сложность в лучшем случае для неудачного поиска в бинарном дереве поиска

Question

Поскольку я не смог найти ответ на этот вопрос:

Какова сложность в лучшем случае для неудачного поиска в несбалансированном бинарном дереве поиска в бета-тета-записи?

Answer 1

Я не уверен, правильно ли я понимаю вопрос, и если вас спросят об амортизированной сложности или конкретном лучшем случае.

Для конкретного случая это будет O(1) для лучшегоcase:

Представьте несбалансированное дерево с корнем, содержащим значение X, с большим левым поддеревом (значениями меньше X), но пустым правым поддеревом (без значений больше X).

Теперь, если вы попытаетесь найти любое значение, большее, чем X (хороший случай), вы поймете, что такого значения нет, просто посетив корень.

Answer 2

Если размер левого дерева равен N1, а правое дерево - N2, то сложность наилучшего случая равна Theta(min(log(N1), log(N2)) + 1) (обратите внимание, что N1 + N2 = N).