4183
правки
Ротационный код: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
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]} | ||