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

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Ротационный код''' (''[[Scheme using rotations]]'') - Рассматриваются два вида преобразований
'''Ротационный код''' (''[[Scheme using rotations]]'') Рассматриваются два вида преобразований
[[бинарное дерево|бинарных деревьев]] в бинарные деревья: [[правая ротация|''правая'']] и [[левая ротация|''левая'' ротация]]. Если бинарное дерево <math>D_1</math>
[[бинарное дерево|бинарных деревьев]] в бинарные деревья: [[правая ротация|''правая'']] и [[левая ротация|''левая'' ротация]]. Если бинарное дерево <math>\,D_1</math>
содержит [[поддерево]] <math>T_1=((\alpha ,A,\beta ),B,\gamma )</math>, где <math>A</math>, <math>B</math> --- [[вершина|вершины]], а <math>\alpha</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>\beta</math>, <math>\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>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_2</math> в вершине <math>A</math>. Левая (правая) ротация в вершине <math>A</math>
дерева  <math>\,D</math> имеет [[глубина дерева|глубину]] <math>\,k</math>, если <math>\,k</math> порядковый номер вершины <math>\,A</math> на [[путь|пути]] по дереву <math>\,D</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>(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</math>, <math>D_n</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>\,D_{i+1}</math> получается  из  <math>\,D_i</math> применением <math>x_i</math> левых
ротаций глубины <math>i</math>.
ротаций глубины <math>\,i</math>.


[[Файл:Scheme using rotations.png|750px]]
[[Файл:Scheme using rotations.png|750px]]


==См. также ==
==См. также ==
''[[Коды Закса]], [[Коды Ли]], [[Коды, свободные от повторения]], [[Коды с дублированием номеров вершин]], [[Коды с использованием ограничителей]], [[Линейный код]], [[Уровневые коды корневых деревьев]].''
* ''[[Коды Закса]],''
* ''[[Коды Ли]],''
* ''[[Коды, свободные от повторений]],''
* ''[[Коды с дублированием номеров вершин]],''
* ''[[Коды с использованием ограничителей]],''
* ''[[Линейный код]],''
* ''[[Уровневые коды корневых деревьев]].''
==Литература==
==Литература==
[Евстигнеев-Касьянов/94]}
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

Навигация