2016-04-11 1 views
0

Я узнаю о бинарных деревьях. Таким образом, для n элементов минимальная высота равна h = ceiling(log(n+1)) - 1, и я получаю, как это рассчитывается от n = 2^(h+1) - 1, но я не понимаю, почему потолок используется. Я получаю, что для большинства значений n, log(n+1) было бы реально, поэтому у меня есть использовать функцию, чтобы сделать ее целым числом, но почему потолок и не этаж?Минимальная высота двоичного дерева

ответ

2

Подумайте о случае n = 2. log (3) находится между 1 и 2. Если мы поланем, оно выйдет на 1-1 = 0, что неверно. Если мы потолок, получим 2-1 = 1, что верно.

Если вам это поможет, вы можете думать об этом как о необходимости округлить частичные уровни до целых уровней, потому что они все еще рассчитывают на высоту дерева.