Уровневые коды корневых деревьев

Уровневые коды корневых деревьев (Level representation of rooted trees) — Пусть $(T,z)$ обозначает корневое дерево с лежащим в его основе свободным деревом $T$ и корнем $z$. Уровень вершины $v$ в $(T,z)$ — это расстояние $v$ от $z$ плюс единица. Уровневый код (обозначение $L(T,z)=[l_1,l_2,\dots ,l_n]$) — это последовательность целых чисел, полученная выписыванием уровней вершин дерева $(T,z)$ в постфиксном порядке. Уровневый код называется каноническим (обозначение $L^{\ast }(T,z))$, если он является наибольшим в лексикографическом упорядочении среди всех уровневых кодов, описывающих дерево.

Вершина $z$ называется основным корнем свободного дерева $T$ (обозначение $\overline{z}(T)$ или просто $\overline{z}$), если либо $z$ — единственный центр $T$, либо $z$ — один из центров $z_1$ и $z_2$ бицентрального дерева $T$, определяемый по следующим правилам. Пусть $T_1$ и $T_2$ — поддеревья, получаемые из $T$ удалением ребра, соединяющего $z_1$ и $z_2$. В качестве $z$ берется $z_1$, если либо $T_1$ имеет меньше вершин, чем $T_2$, либо $T_1$ и $T_2$ состоят из равного числа вершин, но $L^{\ast }(T_1,z_1)$ лексикографически предшествует последовательности $L^{\ast }(T_2,z_2);z_2$ берется в противном случае. Уровневый код $L(T,\overline{z})$называется главным уровневым кодом дерева $T$, а $L^{\ast }(T,\overline{z})$ — главным каноническим уровневым кодом дерева $T$.

См. также

• Код Гапта для 2-3-деревьев,
• Коды Ли,
• Коды, свободные от повторений,
• Коды с дублированием номеров вершин,
• Коды с использованием ограничителей,
• Линейный код.

Литература

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.