Ротационный код

Ротационный код (Scheme using rotations) — Рассматриваются два вида преобразований бинарных деревьев в бинарные деревья: правая и левая ротация. Если бинарное дерево $D_1$ содержит поддерево $T_1=((\alpha ,A,\beta ),B,\gamma )$, где $A,B$ — вершины, а $\alpha ,\beta ,\gamma$ — произвольные поддеревья, то дерево $D_2$, в котором $T_1$ заменено на поддерево $T_2=(\alpha ,A,(\beta ,B,\gamma ))$, является результатом правой ротации $D_1$ в вершине $B$, а дерево $D_1$ является результатом левой ротации дерева $D_2$ в вершине $A$. Левая (правая) ротация в вершине $A$ дерева $D$ имеет глубину $k$, если $k$ — порядковый номер вершины $A$ на пути по дереву $D$ от его корня к самому левому листу.

Последовательность $(x_{n-1},x_{n-2},\dots ,x_2,x_1)$ называется ротационным кодом дерева $D$, если есть последовательность деревьев $D_n,D_{n-1},\dots ,D_1$, в которой $D_1=D,D_n$ — левостороннее дерево, а каждое дерево $D_{i+1}$ получается из $D_i$ применением $x_i$ левых ротаций глубины $i$.

См. также

• Коды Закса,
• Коды Ли,
• Коды, свободные от повторений,
• Коды с дублированием номеров вершин,
• Коды с использованием ограничителей,
• Линейный код,
• Уровневые коды корневых деревьев.

Литература

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