Сбалансированные деревья

 

Дерево называется идеально сбалансированным, если число узлов в его правом и левом поддеревьях отличается не более чем на единицу (далее будем называть такие деревья сбалансированными). Сбалансированное дерево, состоящее из N узлов, имеет минимальную высоту среди всех бинарных деревьев. Высоту сбалансированного дерева можно определить по формуле:

.

Минимальная высота при заданном числе узлов достигается, если на всех уровнях, кроме последнего, размещается максимально возможное число узлов. Это происходит за счет равномерного размещения узлов поровну слева и справа от каждого узла.

Правило равномерного размещения для N узлов (правило 1) формулируется с помощью рекурсии:

¨ взять один узел в качестве корня;

¨ по правилу 1 построить левое поддерево с числом узлов nl = N div 2;

¨ по правилу 1 построить правое поддерево с числом узлов nr = N - nl - 1.

Структура сбалансированного дерева из N узлов определяется количеством узлов (рис. 69).

 

N = 5