На этом шаге мы рассмотрим эти операции.

Существуют две операции "спаренный двусторонний поворот" и две операции "спаренный односторонний поворот".

Целью выполнения всех "спаренных" операций является повышение уровня узла на два уровня.

1. Операция "спаренный односторонний поворот"

Операция "спаренный односторонний поворот" состоит из двух выполняемых последовательно ротаций вправо или влево, причём выполнение операции всегда начинается с ротации вокруг верхнего узла.

Иногда применяются следующие названия этих операций: zig-zig-поворот, LL-поворот, RR-поворот.

Пример операции "RR-поворот" (по [1, с.335]).

Рис.1. Операция "RR-поворот"

Пример операции "LL-поворот" (по [1, с.335]).

Рис.2. Операция "LL-поворот"

2. Операция "спаренный двусторонний поворот"

Операция "спаренный двусторонний поворот" состоит:

(1) либо из ротации вправо, за которой следует ротация влево;
(2) либо из ротации влево, за которой следует ротация вправо.

Иногда применяются следующие названия этих операций: zig-zig-поворот, LR-поворот, RL-поворот.

Пример операции "LR-поворот" (по [1, с.335]).

Рис.3. Операция "LR-поворот"

Пример операции "RL-поворот" (по [1, с.335]).

Рис.4. Операция "RL-поворот"

В заключение приведем демонстрационный пример.

   ; Демонстрация сравнения по количеству применяемых операций
   ; "ротация" и "спаренный поворот"  в  процессе  перемещения
   ; в корень указанной вершины A бинарного дерева поиска Tree.
   ;  Запуск функции на выполнение:
   ;
   ;  >muLISP85 SplTree.sys 201-04.LSP
   ;
   ; Автор: И.А.Кудрявцева (01.07.2006)
   ; **********************************
   (DEFUN TEST (LAMBDA NIL
      (PRINT "Построение числового бинарного дерева поиска:")
      (SETQ Tree NIL)
      (LOOP
         (PRIN1 "Введите очередной элемент дерева (окончание !): ")
         (SETQ X (READ)) ( (EQ X '!) )
         (PRINT (SETQ Tree (AddTree X Tree)))
      )  
      (PRIN1 "Введите элемент дерева: ")
      (SETQ A (READ))
      ; -----------------
      (WRS "Compare.txt")
      (PRINT "Числовое бинарное дерево поиска:") 
      (PRINT (OutTree Tree 0)) 
      (PRINT "Результат ротации (изменение корня дерева):")
      (Root_A A Tree 0)
      (PRINT "Результат поворотов (изменение корня дерева):")
      (SpRoot_A A Tree 0)
      (WRS)
   ))
   ; --------------------------------
   (DEFUN Root_A (LAMBDA (A Tree Kol)
   ; Функция, которая по числовому бинарному дереву поиска
   ; Tree возвращает преобразованное дерево, корнем  кото-
   ; рого стала одна из его вершин A в результате выполне-
   ; ния операции "ротация"; параметр  Kol содержит  коли-
   ; чество применённых операций "ротация"
   ; -------------------------------------
      (COND ( (OR (NULL Tree)
                  (AND (NOT (Search A (Left Tree))) 
                       (NOT (Search A (Right Tree))))
                  (EQUAL (Root Tree) A)) 
              ((OutTree Tree 0)
               (PRINT "") (PRIN1 "Количество ротаций: ")
               (PRINT Kol)) )
            (  T  (Root_A A (RotInTree A Tree)
                            (+ 1 Kol)) ))
   ))
   ; ----------------------------------
   (DEFUN SpRoot_A (LAMBDA (A Tree Kol)
   ; Функция, которая по числовому бинарному дереву поиска
   ; Tree возвращает преобразованное дерево, корнем  кото-
   ; рого стала одна из его вершин A в результате выполне-
   ; ния операции "спаренный поворот" (и возможно,  опера-
   ; ции "ротация"); параметр Kol содержит количество при-
   ; менённых  операций  "спаренный поворот" (и  возможно,
   ; операции "ротация")
   ; ------------------------
      (COND ( (OR (NULL Tree)
                  (AND (NOT (Search A (Left Tree))) 
                       (NOT (Search A (Right Tree))))
                  (EQUAL (Root Tree) A)) 
              ((OutTree Tree 0)
               (PRINT "") (PRIN1 "Количество поворотов: ")
               (PRINT Kol)) )
            ( (EQUAL (Root (Left Tree)) A) 
              ((OutTree (Rot_Right Tree) 0)
               (PRINT "") 
               (PRIN1 "Количество поворотов (+ одна ротация): ")
               (PRINT (+ 1 Kol))) )
            ( (EQUAL (Root (Right Tree)) A) 
              ((OutTree (Rot_Left Tree) 0)
               (PRINT "") 
               (PRIN1 "Количество поворотов (+ одна ротация): ") 
               (PRINT (+ 1 Kol))) )
            (  T  (SpRoot_A A (SparPov A Tree)
                            (+ 1 Kol)) ))
   ))
   (RDS)

Все файлы можно взять здесь.

⁽¹⁾ Бакнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi. - СПб.: ООО "ДиаСофтЮП", 2003. - 560 с.

На следующем шаге мы рассмотрим операцию "включение в корень бинарного дерева поиска".

Предыдущий шаг Содержание Следующий шаг