На этом шаге мы рассмотрим реализацию данной операции.

Рассмотрим (следуя [1, с. 520]) алгоритмы для объединения двух бинарных деревьев поиска в единое бинарное дерево поиска.

1. Обойти первое BST-дерево, включая каждый из посещённых узлов во второе BST-дерево; при этом функция "включение во второе BST-дерево" используется как параметр функции обхода первого BST-дерева.

Время выполнения подобного решения нелинейно, поскольку для каждого включения требуется линейное время.

2. Обойти оба BST-дерева и поместить посещённые элементы в общий массив; затем построить с помощью этого массива новое BST-дерево.

Время выполнения этой операции может быть линейным, но это связано с потенциально большим массивом.

3. Рассмотрим рекурсивную реализацию операции "объединение BST-деревьев":

(1) вначале включаем корень первого BST-дерева во второе BST-дерево, используя операцию "включение в корень". Эта операция позволяет получить два поддерева, ключи которых заведомо меньше этого корня, и два поддерева, ключи которых заведомо больше этого корня;
(2) требуемый результат получается рекурсивным объединением первой пары в левое поддерево корня, а второй пары - в правое поддерево корня.

Эта реализация является линейной по затратам времени.

Приведем демонстрационный пример на языке LISP.

   ; Демонстрация функции, возвращающей результат выполнения
   ; операции "объединение двух  бинарных деревьев поиска" с
   ; помощью операции "включение в корень  с  использованием
   ; операции "ротация"".
   ;   Внимание! Объединяемые деревья не должны иметь одина-
   ; ковых вершин.
   ;
   ;  Запуск функции на выполнение:
   ;
   ;  >muLISP85 SplTree.sys 201-07.LSP
   ;
   ; Автор: И.А.Кудрявцева (02.08.2006)
   ; ----------------------------------
   (DEFUN TEST (LAMBDA NIL
      (PRINT "Построение числового бинарного дерева поиска 1:")
      (SETQ Tree1 NIL)
      (LOOP
         (PRIN1 "Введите очередной элемент дерева (окончание !): ")
         (SETQ X (READ)) 
         ( (EQ X '!) )
         (PRINT (SETQ Tree1 (AddInRoot X Tree1)))
         (PRINT "Числовое бинарное дерево поиска:") 
         (PRINT (OutTree Tree1 0))
      )  
      (PRINT "Построение числового бинарного дерева поиска 2:")
      (SETQ Tree2 NIL)
      (LOOP
         (PRIN1 "Введите очередной элемент дерева (окончание !): ")
         (SETQ X (READ)) ( (EQ X '!) )
         (PRINT (SETQ Tree2 (AddInRoot X Tree2)))
         (PRINT "Числовое бинарное дерево поиска:") 
         (PRINT (OutTree Tree2 0))
      )  
      (PRINT "Результат объединения бинарных деревьев поиска:")
      (PRINT (SETQ Tree3 (UniteBST Tree1 Tree2)))
      (PRINT (OutTree Tree3 0))
   ))
   ; -----------------------------------
   (DEFUN UniteBST (LAMBDA (Tree1 Tree2)
   ; Функция, возвращающая результат объединения двух числовых
   ; бинарных деревьев поиска Tree1 и Tree2
   ; --------------------------------------
     (COND ( (NULL Tree1) Tree2 )
           ( (NULL Tree2) Tree1 )
           ( T (CONS (Root Tree1)
                     (LIST (UniteBST (Left Tree1)
                                     (Left (AddInRoot (Root Tree1)
                                                      Tree2)))
                           (UniteBST (Right Tree1)
                                     (Right (AddInRoot (Root Tree1)
                                                       Tree2)))))
           )
     )
   ))
   ; ***************************
   ; Неудачные тестовые примеры:
   ; ---------------------------
   (WRS TestUnit.txt)
   "UniteBST"
   ; -------------------------------------------------
   (EQUAL (UniteBST '(1 NIL NIL) '(3 (2 NIL NIL) NIL))
          '(1 NIL (3 (2 NIL NIL) NIL)))
   (EQUAL (UniteBST '(8 (6 NIL (7 NIL NIL))) 
                    '(10 NIL (14 NIL NIL)))
          '(8 (6 NIL (7 NIL NIL)) (10 NIL (14 NIL NIL))))
   (EQUAL (UniteBST '(5 (4 (3 NIL NIL) NIL) NIL)
                    '(9 (8 (7 NIL NIL) NIL) NIL)) 
          '(5 (4 (3 NIL NIL) NIL) (9 (8 (7 NIL NIL) NIL) NIL))) 
   (EQUAL (UniteBST '(5 (4 NIL NIL) NIL)
                    '(9 (8 (7 NIL NIL) NIL) NIL)) 
          '(5 (4 NIL NIL) (9 (8 (7 NIL NIL) NIL) NIL)))
   (EQUAL (UniteBST '() '(5 (4 NIL NIL) NIL)) 
          '(5 (4 NIL NIL) NIL))
   (EQUAL (UniteBST '(6 (5 (4 NIL NIL) NIL) NIL) 
                    '(9 NIL (11 NIL NIL)))
          '(6 (5 (4 NIL NIL) NIL ) (9 NIL (11 NIL NIL))))
   (EQUAL (UniteBST '(15 (12 (8 (3 NIL NIL) (5 NIL NIL)) NIL) NIL)
                    '(17 (16 NIL NIL) (29 NIL NIL)))
          '(15 (12 (8 (3 NIL NIL) (5 NIL NIL)) NIL)
               (17 (16 NIL NIL) (29 NIL NIL))))
   (EQUAL (UniteBST '(5 (4 (1 NIL NIL) NIL) (8 NIL NIL))
                    '(9 (6 NIL NIL) (11 NIL NIL)))
          '(5 (4 (1 NIL NIL) NIL)
              (8 (6 NIL NIL) (9 NIL (11 NIL NIL)))))
   (EQUAL (UniteBST '() '()) '()) 

   (EQUAL (UniteBST '(71 (69 (65 NIL NIL) NIL)
                         (77 (73 NIL NIL) (82 NIL NIL)))
                    '(78 (72 (67 NIL NIL) NIL)
                         (88 (83 (80 NIL NIL) NIL) NIL)))
          '(71 (69 (65 NIL (67 NIL NIL)) NIL)
               (77 (73 (72 NIL NIL) NIL)
                   (82 (78 NIL (80 NIL NIL))
                       (88 (83 NIL NIL) NIL)))))
   ; -------------------------------------------
   ; Удачный тестовый пример:
   ; ---------------------------------------------
   ; (EQUAL (UniteBST '(4 (2 NIL NIL) (8 NIL NIL)) 
   ;                  '(4 (2 (1 NIL NIL) (3 NIL NIL)) NIL))
   ;        '(4 (2 (1 NIL NIL) (3 NIL NIL)) (8 NIL NIL)))
   ; ----------------------------------------------------
   (WRS)
   (RDS)

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

⁽¹⁾ Седжвик Р. Фундаментальные алгоритмы C++. Анализ. Структуры данных. Сортировка. Поиск. - К.: ДиаСофт, 2001. - 688 с.

На следующем шаге мы рассмотрим Декартовы деревья.

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