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

Длина путей


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

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

определяется рекурсивно и считается равным нулю, если
корень
; в противном случае уровень
определяется как
. Понятие уровня дает возможность определить высоту
дерева
:

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



Содержание раздела