Ротационный код: различия между версиями

'''Ротационный код''' (''[[Scheme using rotations]]'') — Рассматриваются два вида преобразований

[[бинарное дерево|бинарных деревьев]] в бинарные деревья: [[правая ротация|''правая'']] и [[левая ротация|''левая'' ротация]]. Если бинарное дерево <math>\,D_1</math>

содержит [[поддерево]] <math>\,T_1=((\alpha ,A,\beta ),B,\gamma )</math>, где <math>\,A,\, B</math> — [[вершина|вершины]], а <math>\,\alpha,\,\beta,\,\gamma</math> — произвольные поддеревья, то [[дерево]] <math>\,D_2</math>, в котором <math>\,T_1</math> заменено на поддерево

<math>\,T_2=(\alpha ,A,(\beta ,B,\gamma ))</math>, является результатом правой ротации <math>\,D_1</math> в вершине <math>\,B</math>, а дерево <math>\,D_1</math>

является результатом левой ротации дерева <math>\,D_2</math> в вершине <math>\,A</math>. Левая (правая) ротация в вершине <math>\,A</math>

дерева  <math>\,D</math> имеет [[глубина дерева|глубину]] <math>\,k</math>, если <math>\,k</math> — порядковый номер вершины <math>\,A</math> на [[путь|пути]] по дереву <math>\,D</math> от

Последовательность <math>(x_{n-1},x_{n-2}, \ldots ,x_2,x_1)</math> называется ротационным кодом дерева <math>\,D</math>, если

есть последовательность деревьев <math>D_n,D_{n-1},\ldots ,D_1</math>, в которой <math>\,D_1=D,\,D_n</math> —

[[левостороннее дерево]], а каждое дерево <math>\,D_{i+1}</math> получается  из  <math>\,D_i</math> применением <math>x_i</math> левых

ротаций глубины <math>\,i</math>.

* ''[[Коды Закса]],''

* ''[[Коды Ли]],''

* ''[[Коды, свободные от повторений]],''

* ''[[Коды с дублированием номеров вершин]],''

* ''[[Коды с использованием ограничителей]],''

* ''[[Линейный код]],''

* ''[[Уровневые коды корневых деревьев]].''

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