Комбинаторные алгоритмы для программистов



             

Длина путей


Деревья можно использовать не только как способ представления структуры данных, но также как средство для анализа поведения определенных алгоритмов. В связи с этим возникает потребность в количественных измерениях различных характеристик деревьев и, в частности, бинарных деревьев.

Наиболее важные количественные характеристики деревьев связаны с уровнями узлов. Уровень

p
определяется рекурсивно и считается равным нулю, если
p
корень
T
; в противном случае уровень
p
определяется как
1+\text{уровень}(FATHER(p))
. Понятие уровня дает возможность определить высоту
h(T)
дерева
T
:

h(T)\max_{p\in T}\text{уровня} (p).

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




Содержание  Назад  Вперед