Двоичные деревья поиска с n как root

Question

В своей книге я прочел следующее утверждение:

Предположим, что дерево является двоичным деревом поиска, тогда:

Если дерево содержит все значения от 1 до n ровно один раз, а n - это root дерева, тогда высота дерева не может быть log2 (n) (округлена в большую сторону)

Почему выполняется это утверждение?

Answer 1

Если n является root, это означает, что все остальные (n-1) элементы находятся на одной стороне дерева. Таким образом, высота дерева составляет не менее d = 1 + log2(n-1)

Маленькая алгебра:

log2(n-1) + 1 = log2(n-1) + log2(2) = log2(2(n-1)) > log2(n) for n > 2

Так что дерево, имеющее n в root, не может достичь высоты log2(n) если он содержит более 2 элементов.

Относительно rouned up части:

Пусть n=17, 17 в root. Оставшиеся 16 элементы составляют идеальное двоичное дерево высотой 4, поэтому общая глубина дерева составляет 5, что противоречит утверждению о том, что глубина не может быть ceil(log2(17)) == 5.