Сколько узлов в полностью заполненном (perfect) бинарном дереве высоты N?

Question

В полностью заполненном бинарном дереве каждый уровень полностью заполнен. Если высота дерева равна N (корень на уровне 0), то количество узлов равно 2^(N+1) - 1. Это связано с тем, что на каждом уровне количество узлов удваивается. Формула легко выводится как сумма геометрической прогрессии.

YeaHub · Accepted Answer

Полностью заполненное бинарное дерево — это идеальный пример структуры с регулярным ростом числа узлов.ОпределениеОпределение: Perfect бинарное дерево — бинарное дерево, в котором у каждого внутреннего узла есть ровно два потомка, а все листья находятся на одном уровне.Как растёт количество узловРассмотрим уровни дерева:Уровень 0 (корень): 1 узелУровень 1: 2 узлаУровень 2: 4 узлаУровень k: 2^k узловЕсли высота дерева N, то уровни идут от 0 до N.Вывод формулыОбщее число узлов — это сумма:1 + 2 + 4 + ... + 2^NЭто геометрическая прогрессия, сумма которой:2^(N+1) - 1ПримерДля N = 2:Уровни: 1 + 2 + 4Всего: 7 узловДля N = 3:1 + 2 + 4 + 8 = 15ВыводФормула 2^(N+1) - 1 позволяет быстро считать узлы без построения дерева.Она часто используется при анализе сложности алгоритмов на деревьях.