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