2014-02-24
807
Дерево называется идеально сбалансированным, если число узлов в его правом и левом поддеревьях отличается не более чем на единицу (далее будем называть такие деревья сбалансированными). Сбалансированное дерево, состоящее из N узлов, имеет минимальную высоту среди всех бинарных деревьев. Высоту сбалансированного дерева можно определить по формуле:
.
Минимальная высота при заданном числе узлов достигается, если на всех уровнях, кроме последнего, размещается максимально возможное число узлов. Это происходит за счет равномерного размещения узлов поровну слева и справа от каждого узла.
Правило равномерного размещения для N узлов (правило 1) формулируется с помощью рекурсии:
¨ взять один узел в качестве корня;
¨ по правилу 1 построить левое поддерево с числом узлов nl = N div 2;
¨ по правилу 1 построить правое поддерево с числом узлов nr = N - nl - 1.
Структура сбалансированного дерева из N узлов определяется количеством узлов (рис. 69).
N = 5
