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

Иногда (при работе с деревьями очень часто) бывает нужно понять, насколько дерево сбалансированно. Проблема в том, что эта характеристика более-менее понятна в отношении бинарных деревьев (для них она равна отношению мощности левого и правого поддеревьев), а для «обычных» деревьев, в общем-то, не понятно, что на
что делить.

Итак, пусть T — «обычное» ориентированное дерево, и из каждой вершины может исходить n ребер. В зависимоти от задачи, можно считать сбалансированность разными способами:

Если n четно, тогда сбалансированность можно считать по следующей формуле:

 

где — мощность поддерева, с корнем в j-той вершине данного дерева. Нумерация здесь соответсвует обходу в ширину, а корень дерева имеет нулевой индекс. То есть, мы берем все ребра исходящие из корня дерева и делим это множество на два. Ссуммируем мощность подмножеств, которые начинаются с вершин, в которые входят эти ребра, и делим одну сумму на другую.
Если n нечетно, тогда формула видоизменяется следующим образом:

Смысл формулы здесь не изменился, но мы учитываем также половину мощности «центрального» поддерева и в делимом и в делителе.

Также сбалансированностью можно считать следующую величину:

где — мощность множества уровней дерева, которые содержат листья, а — количество уровней всего.