Ротационный код

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

Scheme using rotations.png

См. также

Литература

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