|
Дерево называется идеально сбалансированным, если число узлов в его правом и левом поддеревьях отличается не более чем на единицу (далее будем называть такие деревья сбалансированными). Сбалансированное дерево, состоящее из N узлов, имеет минимальную высоту среди всех бинарных деревьев.
Минимальная высота при заданном числе узлов достигается, если на всех уровнях, кроме последнего, размещается максимально возможное число узлов. Это происходит за счет равномерного размещения узлов поровну слева и справа от каждого узла.
Правило равномерного размещения для N узлов (правило 1) формулируется с помощью рекурсии:
• взять один узел в качестве корня;
• по правилу 1 построить левое поддерево с числом узлов nl = N div 2;
• по правилу 1 построить правое поддерево с числом узлов nr = N - nl - 1.
Сбалансированное дерево, как и дерево любого другого вида, можно построить в процессе нисходящего обхода. Особенность работы процедуры построения дерева заключается в том, что сначала создаются корневые узлы, адреса которых запоминаются в стеке. Установить ссылки из корневых узлов дерева на их поддеревья можно только после того, как эти поддеревья будут созданы и адреса их корневых узлов возвращены в точки вызова. Точками вызова являются поля ссылок на левое поддерево (root^.left) или правое поддерево (root^.right) корневого узла (в таблице установка этих ссылочных связей показана стрелками). Подобная возможность обеспечивается за счет того, что указатель на корень дерева является параметром-переменной процедуры.
|
