Анализ времени операций бинарного дерева поиска

Question

Я читал о бинарных деревьях поиска, что если это полное дерево (все узлы, кроме конечных узлов имеют двух дочерних элементов), имеющее n узлов, то ни один путь не может иметь более 1 + log n узлов.

Вот расчет, который я сделал ... Вы можете показать мне, где я ошибся ....

the first level of bst has only one node(i.e. the root)-->2^0
the second level have 2 nodes(the children of root)---->2^1
the third level has 2^3=8 nodes
 .
 .
the (x+1)th level has 2^x nodes

so the total number of nodes =n = 2^0 +2^1 +2^2 +...+2^x = 2^(x+1)-1
so, x=log(n+1)-1

now as it is a 'complete' tree...the longest path(which has most no of nodes)=x
and so the nodes experienced in this path is x+1= log(n+1)

Тогда как появилось число 1 + log n ...?

Answer 1

Краткий ответ: количество x уровней в полном (или совершенном) двоичном дереве равно log2(n+1), где n - количество узлов (альтернативно, n = 2^(x-1)). Дерево с x уровнями имеет высоту x-1. Самый длинный путь от корня до любого узла содержит x = log2(n+1) узлов (и x-1 ребер).

Теперь, поскольку n+1 является степенью 2, у нас есть это log2(n+1) = 1 + floor(log2(n)). Другими словами, 1 + log2(n) - это правильная верхняя граница, но это никогда не целое число.

Мне неясно, относится ли x в ваших вычислениях к высоте или количеству уровней.