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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
 
(не показаны 3 промежуточные версии 1 участника)
Строка 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]]


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

Текущая версия от 15:19, 9 октября 2019

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

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

Scheme using rotations.png

См. также

Литература

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