Аноним

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

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Ротационный код''' (''Scheme using rotations'') - Рассматриваются два вида преобразован...)
 
Нет описания правки
Строка 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</math>, <math>B</math> --- [[вершина|вершины]], а <math>\alpha</math>,
<math>\beta</math>, <math>\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</math>, <math>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>.


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