На этом шаге мы приведем примеры работы с такими деревьями средствами языка LISP.
Приведем ряд примеров, иллюстрирующих работу с красно-черными деревьями с помощью конструкций языка LISP.
Пример 1. Построение красно-черного дерева.
Раскрыть/скрыть текст примера.
; Демонстрация использования библиотеки для работы ; с красно-чёрными деревьями ; Запуск функции на выполнение: ; ; >muLISP85 RBTree.sys 202-01.lsp ; -------------------------------- (DEFUN TEST (LAMBDA NIL (SETQ *PRINT-ESCAPE* NIL) (PRINT "Построение красно-чёрного дерева.") (SETQ Tree '(NIL . B)) (LOOP (PRINT "Введите ключ добавляемого узла (окончание !):") (SETQ S (READ)) ( (EQ S '!) ) (PRINT "Красно-чёрное дерево:") (OutTree (SETQ Tree (RB-Ins Tree S)) 0) (PRINT (PRINT " ")) ) (LOOP (PRINT "Введите ключ удаляемого узла (окончание !):") (SETQ S (READ)) ( (EQ S '!) (SYSTEM)) (PRINT "Красно-чёрное дерево:") (OutTree (SETQ Tree (RB-Del Tree S)) 0) (PRINT (PRINT " ")) ) )) (RDS)
Пример 2. Определение черной высоты красно-черного дерева, определённой по левой ветви исходного дерева.
Раскрыть/скрыть текст примера.
; Демонстрация функции, возвращающей чёрную высоту ; красно-чёрного дерева, определённой по левой ; ветви исходного дерева ; Запуск файла: ; ; >muLISP85 RBTree.sys 202-02.lsp ; ; -------------------------- (DEFUN HBlack (LAMBDA (Tree) (COND ( (NULL Tree) 0 ) ( (AND (OR (EQUAL (CDAR Tree) B) (EQUAL (CDAR Tree) R)) (EQUAL (Left Tree) '(NIL . B)) (EQUAL (Right Tree) '(NIL . B))) 1 ) ( (AND (OR (EQUAL (CDAR Tree) B) (EQUAL (CDAR Tree) R)) (NOT (EQUAL (Left Tree) '(NIL . B))) (EQUAL (CDAR (Left Tree)) B)) (+ 1 (HBlack (Left Tree))) ) ( (AND (EQUAL (CDAR Tree) B) (NOT (EQUAL (Left Tree) '(NIL . B))) (EQUAL (CDAR (Left Tree)) R)) (+ 1 (HBlack (Left Tree))) ) ( T (HBlack (Left Tree)) )) )) ; -------------------------- ; Неудачные тестовые примеры ; ----------------------------- (EQUAL (HBlack '(NIL . B) B) 0) (EQUAL (HBlack '((1 . B) (NIL . B) (NIL . B)) B) 1) (EQUAL (HBlack '((1 . R) (NIL . B) (NIL . B)) R) 1) (EQUAL (HBlack '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((6 . B) (NIL . B) (NIL . B))) B) 2) (EQUAL (HBlack '((5 . R) ((3 . B) (NIL . B) (NIL . B)) ((6 . B) (NIL . B) (NIL . B))) R) 2) (EQUAL (HBlack '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((10 . R) ((8 . B) ((7 . R) (NIL . B) (NIL . B)) (NIL . B)) ((11 . B) (NIL . B) (NIL . B)))) B) 2) (EQUAL (HBlack '((5 . R) ((3 . B) (NIL . B) (NIL . B)) ((8 . B) ((7 . R) (NIL . B) (NIL . B)) (NIL . B))) R) 2) (EQUAL (HBlack '((10 . B) ((3 . B) ((2 . B) (NIL . B) (NIL . B)) ((8 . R) ((5 . B) ((1 . R) (NIL . B) (NIL . B)) (NIL . B)) ((9 . B) (NIL . B) (NIL . B)))) ((13 . B) ((12 . B) (NIL . B) (NIL . B)) ((18 . R) ((15 . B) ((14 . R) (NIL . B) (NIL . B)) (NIL . B)) ((19 . B) (NIL . B) (NIL . B))))) B) 3) ; --------------------------------------------------------------- (RDS)
В приведенных примерах используется библиотека для работы с красно-чёрными деревьями. Ее текст приведен ниже.
Раскрыть/скрыть текст библиотеки.
; Библиотека для работы с красно-чёрными деревьями. ; ; Автор псевдокода операции вставки узла в красно-чёрное ; дерево и восстановления красно-чёрных свойств дерева ; после удаления узла: [Кормен,Лейзерсон,Ривест,1999]. ; ; Автор программы: И.А.Кудрявцева (01-07.08.2006) ; Исправления : И.А.Кудрявцева (23-24.01.2007) ; ----------------------------------------------- (SETQ *PRINT-ESCAPE* NIL) ; ---------------------------- (DEFUN RB-Ins (LAMBDA (Tree S) ; Функция возвращает красно-чёрное дерево поиска Tree, ; в которое добавлен указанный узел S ; -------------------------------------------------- (Subst (SETQ Tree (RB-Ins1 (AddTree S R Tree) S)) (CAR Tree) (CONS (Root Tree) B)) )) ; ----------------------------- (DEFUN RB-Ins1 (LAMBDA (Tree S) ; Функция возвращает бинарное дерево поиска Tree с NIL-узлами, ; в которое добавлен указанный узел S и которое может обладать ; всеми свойствами красно-чёрного дерева ; -------------------------------------- (COND ( (OR (EQUAL S (Root Tree)) (EQUAL (CDAR (Search (Srch_D S Tree) Tree)) B)) Tree ) ( (AND (OR (<; (Srch_D S Tree) (Srch_G S Tree)) (>; (Srch_D S Tree) (Srch_G S Tree))) (NOT (NULL (Srch_U S Tree))) (EQUAL (CDAR (Search (Srch_U S Tree) Tree)) R)) (RB-Ins1 (Chng_Clr Tree (Srch_D S Tree) B (Srch_G S Tree) R (Srch_U S Tree) B) (Srch_G S Tree)) ) ( (OR (AND (<; (Srch_D S Tree) (Srch_G S Tree)) (>; S (Srch_D S Tree))) (AND (>; (Srch_D S Tree) (Srch_G S Tree)) (<; S (Srch_D S Tree)))) (RB-Ins1 (RotInTree S Tree) (Srch_D S Tree)) ) ( T (RB-Ins1 (RotInTree (Srch_D S Tree) (Chng_Clr Tree (Srch_D S Tree) B (Srch_G S Tree) R NIL NIL)) S) )) )) ; ---------------------------- (DEFUN RB-Del (LAMBDA (Tree S) ; Функция возвращает красно-чёрное дерево поиска Tree, ; из которого удалён указанный узел S ; ----------------------------------- (COND ( (OR (NULL (Srch S Tree)) (NULL (Root Tree))) Tree ) ( (AND (EQUAL (CDAR (Search S Tree)) R) (OR (NULL (Root (Left (Search S Tree)))) (NULL (Root (Right (Search S Tree)))))) (Delete S Tree)) ( (AND (NULL (Root (Right (Search S Tree)))) (NULL (Root (Left (Search S Tree))))) (Delete S (RB-Del1 Tree S)) ) ( T (Delete S (RB-Del1 Tree (COND ( (NULL (Root (Right (Search S Tree)))) (Root (Left (Search S Tree))) ) ( T (CAR (Ud (Right (Search S Tree))))) ))) )) )) ; ----------------------------- (DEFUN RB-Del1 (LAMBDA (Tree X) ; Функция возвращает сбалансированное красно-чёрное дерево ; после удаления узла X ; ---------------------------------- (COND ( (OR (EQUAL X (Root Tree)) (EQUAL (CDAR (Search X Tree)) R)) (Subst Tree (CAR (Search X Tree)) (CONS X B)) ) ( (AND (OR (<; X (Srch_D X Tree)) (>; X (Srch_D X Tree))) (EQUAL (CDAR (Search (Srch_B X Tree) Tree)) R)) (RB-Del1 (RotInTree (Srch_B X Tree) (Chng_Clr Tree (Srch_D X Tree) R (Srch_B X Tree) B NIL NIL)) X) ) ( (AND (OR (<; X (Srch_D X Tree)) (>; X (Srch_D X Tree))) (EQUAL (CDAR (Search (Srch_B X Tree) Tree)) B) (OR (AND (NULL (Srch_Nl X Tree)) (NULL (Srch_Nr X Tree))) (AND (EQUAL (CDAR (Search (Srch_Nl X Tree) Tree)) B) (EQUAL (CDAR (Search (Srch_Nr X Tree) Tree)) B)))) (RB-Del1 (Chng_Clr Tree NIL NIL (Srch_B X Tree) R NIL NIL) (Srch_D X Tree)) ) ( (AND (<; X (Srch_D X Tree)) (EQUAL (CDAR (Search (Srch_Nr X Tree) Tree)) B)) (RB-Del1 (RotInTree (Srch_Nl X Tree) (Chng_Clr Tree NIL NIL (Srch_B X Tree) R (Srch_Nl X Tree) B)) X) ) ( (<; X (Srch_D X Tree)) (RotInTree (Srch_B X Tree) (Chng_Clr Tree (Srch_D X Tree) B (Srch_B X Tree) (CDAR (Search (Srch_D X Tree) Tree)) (Srch_Nr X Tree) B)) ) ; ---------------------------------------------- ; "Зеркальное" отражение двух предыдущих условий ; ---------------------------------------------- ( (AND (>; X (Srch_D X Tree)) (EQUAL (CDAR (Search (Srch_Nl X Tree) Tree)) B)) (RB-Del1 (RotInTree (Srch_Nr X Tree) (Chng_Clr Tree NIL NIL (Srch_B X Tree) R (Srch_Nr X Tree) B)) X) ) ( T (RotInTree (Srch_B X Tree) (Chng_Clr Tree (Srch_D X Tree) B (Srch_B X Tree) (CDAR (Search (Srch_D X Tree) Tree)) (Srch_Nl X Tree) B)) )) )) ; ------------------------------------------------------------ (DEFUN Chng_Clr (LAMBDA (Tree D Clr_D GvB Clr_GvB UvN Clr_UvN) ; Функция возвращает копию бинарного дерева поиска Tree с изме- ; нёнными данными (цветами) следующих узлов: ; "отца", "дедушки" или "брата", "дяди" или "племянника" ; ------------------------------------------------------ (COND ( (NULL Tree) Tree ) ( T (Subst (Subst (Subst Tree (CAR (Search GvB Tree)) (CONS GvB Clr_GvB)) (CAR (Search D Tree)) (CONS D Clr_D)) (COND ( (NULL UvN) NIL ) ( T (CAR (Search UvN Tree)) )) (CONS UvN Clr_UvN)) )) )) ; ------------------------ (DEFUN Root (LAMBDA (Tree) ; Функция возвращает ключ корня бинарного дерева поиска ; Tree с NIL-узлами ; ----------------- (CAAR Tree) )) ; ------------------------ (DEFUN Left (LAMBDA (Tree) ; Функция возвращает левое поддерево бинарного дерева поиска ; Tree с NIL-узлами ; --------------------------------- (COND ( (NULL (Root Tree)) NIL ) ( T (CADR Tree) )) )) ; ------------------------- (DEFUN Right (LAMBDA (Tree) ; Функция возвращает правое поддерево бинарного дерева поиска ; Tree с NIL-узлами ; --------------------------------- (COND ( (NULL (Root Tree)) NIL ) ( T (CADDR Tree) )) )) ; ----------------------------------- (DEFUN AddTree (LAMBDA (S Color Tree) ; Функция добавляет элемент с ключом S и цветом Color ; в бинарное дерево поиска Tree с NIL-узлами ; ------------------------------------------ (COND ( (EQUAL (Root Tree) NIL) (LIST (CONS S Color) (CONS NIL B) (CONS NIL B)) ) ( (EQUAL S (Root Tree)) Tree ) ( (<; S (Root Tree)) (LIST (CAR Tree) (AddTree S Color (Left Tree)) (Right Tree)) ) ( T (LIST (CAR Tree) (Left Tree) (AddTree S Color (Right Tree))) )) )) ; ---------------------------- (DEFUN Delete (LAMBDA (S Tree) ; Функция удаляет узел с ключом S из бинарного дерева поиска ; Tree с NIL-узлами. ; Место удаляемой вершины занимает вершина, ключ которой яв- ; ляется следующим по порядку (в смысле по ряду целых чисел) ; ключей вершин дерева. ; Функции Delete и Ud повторяют соответствующие рекурсивные ; процедуры Н.Вирта [1985], написанные на языке программиро- ; вания Pascal, с небольшими изменениями ; ------------------------------------------ (COND ( (NULL (Root Tree)) (CONS NIL B) ) ( (<; S (Root Tree)) (LIST (CAR Tree) (Delete S (Left Tree)) (Right Tree)) ) ( (>; S (Root Tree)) (LIST (CAR Tree) (Left Tree) (Delete S (Right Tree))) ) ( T (COND ( (NULL (Root (Right Tree))) (Left Tree) ) ( (NULL (Root (Left Tree))) (Right Tree) ) ( T (LIST (Ud (Right Tree)) (Left Tree) (Delete (Root (Ud (Right Tree))) (Right Tree))) )) )) )) ; ---------------------- (DEFUN Ud (LAMBDA (Tree) ; Возвращает узел с минимальным ключом бинарного дерева поиска ; Tree с NIL-узлами. ; Вспомогательная функция для функции Delete ; ----------------------------------------------- (COND ( (NULL (Root (Left Tree))) (CAR Tree) ) ( T (Ud (Left Tree)) )) )) ; -------------------------- (DEFUN Srch (LAMBDA (S Tree) ; Предикат, устанавливающий, имеется ли элемент S в ; бинарном дереве поиска Tree с NIL-узлами ; ---------------------------------------- (COND ( (NULL (Root Tree)) NIL ) ( (EQUAL (Root Tree) S) T ) ( T (OR (Srch S (Left Tree)) (Srch S (Right Tree))) )) )) ; ---------------------------- (DEFUN Search (LAMBDA (S Tree) ; Функция ищет в бинарном дереве поиска Tree с NIL-узлами ; элемент с ключом S: в случае успеха функция возвращает ; поддерево дерева Tree, в котором узел с ключом S являет- ; ся корнем; в противном случае - NIL ; ----------------------------------------------- (COND ( (OR (NULL S) (NULL (Root Tree))) NIL ) ( (EQUAL S (Root Tree)) Tree ) ( (<; S (Root Tree)) (Search S (Left Tree)) ) ( T (Search S (Right Tree)) )) )) ; ---------------------------- (DEFUN Subst (LAMBDA (LST A B) ; Функция заменяет в многоуровневом списке LST ; все вхождения элемента A на элемент B. ; Замена производится на всех уровнях ; ----------------------------------- (COND ( (NULL LST) NIL ) ( (NULL A) LST ) ( (AND (ATOM LST) (NEQ LST A)) LST) ( (EQUAL (CAR LST) A) (CONS B (Subst (CDR LST) A B)) ) ( T (CONS (Subst (CAR LST) A B) (Subst (CDR LST) A B) ))) )) ; ---------------------------- (DEFUN Srch_G (LAMBDA (S Tree) ; Функция, возвращающая ключ "дедушки" для заданной вершины ; S бинарного дерева поиска Tree с NIL-узлами ; ----------------------------------------------------- (COND ( (OR (NULL (Root Tree)) (NULL (Srch S Tree))) NIL ) ( (OR (EQUAL S (Root (Left (Left Tree)))) (EQUAL S (Root (Right (Left Tree)))) (EQUAL S (Root (Left (Right Tree)))) (EQUAL S (Root (Right (Right Tree))))) (Root Tree) ) ( (EQUAL (Srch S (Left Tree)) NIL) (Srch_G S (Right Tree)) ) ( T (Srch_G S (Left Tree)) )) )) ; ---------------------------- (DEFUN Srch_D (LAMBDA (S Tree) ; Функция, возвращающая ключ "отца" для заданной вершины ; S бинарного дерева поиска Tree с NIL-узлами ; ------------------------------------------- (COND ( (OR (EQUAL S (Root Tree)) (NULL (Srch S Tree))) NIL ) ( (NULL (Srch_G S Tree)) (Root Tree) ) ( (<; S (Srch_G S Tree)) (Root (Left (Search (Srch_G S Tree) Tree))) ) ( T (Root (Right (Search (Srch_G S Tree) Tree))) )) )) ; ---------------------------- (DEFUN Srch_B (LAMBDA (S Tree) ; Функция, возвращающая ключ "брата" для заданной вершины ; S бинарного дерева поиска Tree с NIL-узлами ; ------------------------------------------- (COND ( (NULL (Srch_D S Tree)) NIL) ( (<; S (Srch_D S Tree)) (Root (Right (Search (Srch_D S Tree) Tree))) ) ( T (Root (Left (Search (Srch_D S Tree) Tree))) )) )) ; ----------------------------- (DEFUN Srch_Nl (LAMBDA (S Tree) ; Функция, возвращающая ключ "племянника (левого)" для заданной ; вершины S бинарного дерева поиска Tree с NIL-узлами ; --------------------------------------------------- (COND ( (NULL (Srch_B S Tree)) NIL ) ( T (Root (Left (Search (Srch_B S Tree) Tree))) )) )) ; ----------------------------- (DEFUN Srch_Nr (LAMBDA (S Tree) ; Функция, возвращающая ключ "племянника (правого)" для заданной ; вершины S бинарного дерева поиска Tree с NIL-узлами ; --------------------------------------------------- (COND ( (NULL (Srch_B S Tree)) NIL ) ( T (Root (Right (Search (Srch_B S Tree) Tree))) )) )) ; ---------------------------- (DEFUN Srch_U (LAMBDA (S Tree) ; Функция, возвращающая ключ "дяди" для заданной вершины ; S бинарного дерева поиска Tree с NIL-узлами ; ------------------------------------------- (COND ( (NULL (Srch_G S Tree)) NIL ) ( (<; S (Srch_G S Tree)) (Root (Right (Search (Srch_G S Tree) Tree))) ) ( T (Root (Left (Search (Srch_G S Tree) Tree))) )) )) ; ----------------------------- (DEFUN Rot_Right (LAMBDA (Tree) ; Функция, моделирующая операцию "ротация вправо" ; в бинарном дереве поиска Tree с NIL-узлами ; ------------------------------------------ (COND ( (OR (NULL (Root Tree)) (NULL (Root (Left Tree)))) Tree ) ( T (CONS (CAR (Left Tree)) (LIST (Left (Left Tree)) (CONS (CAR Tree) (LIST (Right (Left Tree)) (Right Tree))))) )) )) ; ---------------------------- (DEFUN Rot_Left (LAMBDA (Tree) ; Функция, моделирующая операцию "ротация влево" ; в бинарном дереве поиска Tree с NIL-узлами ; ------------------------------------------ (COND ( (OR (NULL (Root Tree)) (NULL (Root (Right Tree)))) Tree ) ( T (CONS (CAR (Right Tree)) (LIST (CONS (CAR Tree) (LIST (Left Tree) (Left (Right Tree)))) (Right (Right Tree)))) )) )) ; ------------------------------- (DEFUN RotInTree (LAMBDA (S Tree) ; Функция, возвращающая преобразованное числовое бинарное ; дерево поиска Tree с NIL-узлами в результате операции ; ротации, производимой над частью дерева, поднимая узел ; S на уровень выше ; ------------------------------------------ (COND ( (NULL (Root Tree)) (CONS NIL B) ) ( (EQUAL (Root Tree) S) Tree ) ( (EQUAL (Root (Left Tree)) S) (Rot_Right Tree) ) ( (EQUAL (Root (Right Tree)) S) (Rot_Left Tree) ) ( T (CONS (CAR Tree) (LIST (RotInTree S (Left Tree)) (RotInTree S (Right Tree)))) )) )) ; ----------------------------- (DEFUN OutTree (LAMBDA (Tree L) ; Изображение красно-чёрного дерева Tree на экране дисплея; ; L - накапливающий параметр, значение которого при первона- ; чальном обращении равно 0 ; ------------------------------- (COND ( (NULL (Root Tree)) "") ( T ((OutTree (Right Tree) (+ L 1)) (PRINT "") (SPACES (* L 3)) (PRIN1 (Root Tree)) (PRIN1 "(") (PRIN1 (CDAR Tree)) (PRIN1 ")") (OutTree (Left Tree) (+ L 1))) )) )) ; -------------------------- ; Неудачные тестовые примеры ; -------------------------- (WRS "RBTree.txt") ; ----------------------------------------------------- "RB-Ins - функция, моделирующая операцию вставки узла S в красно-чёрное дерево Tree" ; ---------------------------------------------------------- (EQUAL (RB-Ins '(NIL . B) 1) '((1 . B) (NIL . B) (NIL . B))) (EQUAL (RB-Ins '((5 . B) ((3 . R) (NIL . B) (NIL . B)) ((7 . R) (NIL . B) (NIL . B))) 2) '((5 . B) ((3 . B) ((2 . R) (NIL . B) (NIL . B)) (NIL . B)) ((7 . B) (NIL . B) (NIL . B)))) (EQUAL (RB-Ins '((5 . B) ((3 . R) (NIL . B) (NIL . B)) ((7 . R) (NIL . B) (NIL . B))) 8) '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((7 . B) (NIL . B) ((8 . R) (NIL . B) (NIL . B))))) (EQUAL (RB-Ins '((5 . B) ((3 . R) (NIL . B) (NIL . B)) (NIL . B)) 4) '((4 . B) ((3 . R) (NIL . B) (NIL . B)) ((5 . R) (NIL . B) (NIL . B)))) (EQUAL (RB-Ins '((5 . B) (NIL . B) ((7 . R) (NIL . B) (NIL . B))) 6) '((6 . B) ((5 . R) (NIL . B) (NIL . B)) ((7 . R) (NIL . B) (NIL . B)))) (EQUAL (RB-Ins '((5 . B) ((3 . R) (NIL . B) (NIL . B)) ((7 . B) (NIL . B) (NIL . B))) 4) '((4 . B) ((3 . R) (NIL . B) (NIL . B)) ((5 . R) (NIL . B) ((7 . B) (NIL . B) (NIL . B))))) (EQUAL (RB-Ins '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((7 . R) (NIL . B) (NIL . B))) 6) '((6 . B) ((5 . R) ((3 . B) (NIL . B) (NIL . B)) (NIL . B)) ((7 . R) (NIL . B) (NIL . B)))) ; ------------------------------------------------------ "RB-Del - функция, моделирующая операцию удаления узла S из красно-чёрного дерева Tree" ; ---------------------------------------------------- (EQUAL (RB-Del '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((6 . B) (NIL . B) (NIL . B))) 5) '((6 . B) ((3 . R) (NIL . B) (NIL . B)) (NIL . B))) (EQUAL (RB-Del '((5 . B) ((3 . R) (NIL . B) (NIL . B)) ((6 . R) (NIL . B) (NIL . B))) 5) '((6 . B) ((3 . R) (NIL . B) (NIL . B)) (NIL . B))) (EQUAL (RB-Del '((5 . B) ((3 . B) ((1 . R) ((0 . B) (NIL . B) (NIL . B)) ((2 . B) (NIL . B) (NIL . B))) ((4 . B) (NIL . B) (NIL . B))) ((7 . B) ((6 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B)))) 7) '((3 . B) ((1 . B) ((0 . B) (NIL . B) (NIL . B)) ((2 . B) (NIL . B) (NIL . B))) ((5 . B) ((4 . B) (NIL . B) (NIL . B)) ((8 . B) ((6 . R) (NIL . B) (NIL . B)) (NIL . B))))) (EQUAL (RB-Del '((5 . B) ((3 . B) ((1 . R) ((0 . B) (NIL . B) (NIL . B)) ((2 . B) (NIL . B) (NIL . B))) ((4 . B) (NIL . B) (NIL . B))) ((7 . B) ((6 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B)))) 5) '((3 . B) ((1 . B) ((0 . B) (NIL . B) (NIL . B)) ((2 . B) (NIL . B) (NIL . B))) ((6 . B) ((4 . B) (NIL . B) (NIL . B)) ((7 . B) (NIL . B) ((8 . R) (NIL . B) (NIL . B)))))) (EQUAL (RB-Del '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((7 . B) (NIL . B) (NIL . B))) 7) '((5 . B) ((3 . R) (NIL . B) (NIL . B)) (NIL . B))) (EQUAL (RB-Del '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((7 . B) (NIL . B) (NIL . B))) 3) '((5 . B) (NIL . B) ((7 . R) (NIL . B) (NIL . B)))) (EQUAL (RB-Del '((5 . B) ((2 . R) ((1 . B) (NIL . B) (NIL . B)) ((3 . B) (NIL . B) (NIL . B))) ((8 . B) (NIL . B) (NIL . B))) 8) '((2 . B) ((1 . B) (NIL . B) (NIL . B)) ((5 . B) ((3 . R) (NIL . B) (NIL . B)) (NIL . B)))) (EQUAL (RB-Del '((5 . B) ((2 . B) ((1 . R) (NIL . B) (NIL . B)) ((3 . R) (NIL . B) (NIL . B))) ((8 . B) (NIL . B) (NIL . B))) 8) '((2 . B) ((1 . B) (NIL . B) (NIL . B)) ((5 . B) ((3 . R) (NIL . B) (NIL . B)) (NIL . B)))) (EQUAL (RB-Del '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((8 . R) ((7 . B) (NIL . B) (NIL . B)) ((9 . B) (NIL . B) (NIL . B))) ) 3) '((8 . B) ((5 . B) (NIL . B) ((7 . R) (NIL . B) (NIL . B))) ((9 . B) (NIL . B) (NIL . B)))) (EQUAL (RB-Del '(NIL . B) 1) '(NIL . B)) (EQUAL (RB-Del '((5 . B) ((3 . R) (NIL . B) (NIL . B)) (NIL . B)) 5) '((3 . B) (NIL . B) (NIL . B))) (EQUAL (RB-Del '((5 . B) ((3 . B) (NIL . B) (NIL . B)) (NIL . B)) 5) '((3 . B) (NIL . B) (NIL . B))) (EQUAL (RB-Del '((5 . B) (NIL . B) ((7 . R) (NIL . B) (NIL . B))) 5) '((7 . B) (NIL . B) (NIL . B))) (EQUAL (RB-Del '((5 . B) (NIL . B) ((7 . B) (NIL . B) (NIL . B))) 5) '((7 . B) (NIL . B) (NIL . B))) (EQUAL (RB-Del '((5 . B) ((3 . R) (NIL . B) (NIL . B)) (NIL . B)) 3) '((5 . B) (NIL . B) (NIL . B))) (EQUAL (RB-Del '((5 . B) (NIL . B) ((7 . R) (NIL . B) (NIL . B))) 7) '((5 . B) (NIL . B) (NIL . B))) (EQUAL (RB-Del '((5 . B) ((3 . R) (NIL . B) (NIL . B)) ((7 . R) (NIL . B) (NIL . B))) 7) '((5 . B) ((3 . R) (NIL . B) (NIL . B)) (NIL . B))) (EQUAL (RB-Del '((5 . B) ((3 . R) (NIL . B) (NIL . B)) ((7 . R) (NIL . B) (NIL . B))) 3) '((5 . B) (NIL . B) ((7 . R) (NIL . B) (NIL . B)))) (EQUAL (RB-Del '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((7 . B) (NIL . B) ((8 . R) (NIL . B) (NIL . B)))) 7) '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B)))) (EQUAL (RB-Del '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((7 . B) ((6 . R) (NIL . B) (NIL . B)) (NIL . B))) 7) '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((6 . B) (NIL . B) (NIL . B)))) (EQUAL (RB-Del '((5 . B) ((4 . B) ((3 . R) (NIL . B) (NIL . B)) (NIL . B)) ((7 . B) (NIL . B) (NIL . B))) 4) '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((7 . B) (NIL . B) (NIL . B)))) (EQUAL (RB-Del '((5 . B) ((3 . B) (NIL . B) ((4 . R) (NIL . B) (NIL . B))) ((7 . B) (NIL . B) (NIL . B))) 3) '((5 . B) ((4 . B) (NIL . B) (NIL . B)) ((7 . B) (NIL . B) (NIL . B)))) ; ------------------------------------------------------------- "Chng_Clr - функция, возвращающая копию бинарного дерева поиска Tree с изменёнными данными (цветами) следующих узлов: 'отца', 'дедушки' или 'брата', 'дяди' или 'племянника'" ; ------------------------------------------------------------- (EQUAL (Chng_Clr '(NIL . B) 3 R 4 R 8 B) '(NIL . B)) (EQUAL (Chng_Clr '((5 . B) ((3 . R) ((2 . R) (NIL . B) (NIL . B)) (NIL . B)) (NIL . B)) 3 B 5 R NIL B) '((5 . R) ((3 . B) ((2 . R) (NIL . B) (NIL . B)) (NIL . B)) (NIL . B))) (EQUAL (Chng_Clr '((3 . B) ((1 . R) (NIL . B) (NIL . B)) ((5 . R) (NIL . B) (NIL . B))) 3 R 1 B 8 B) '((3 . R) ((1 . B) (NIL . B) (NIL . B)) ((5 . R) (NIL . B) (NIL . B)))) (EQUAL (Chng_Clr '((5 . B) ((3 . R) ((2 . R) (NIL . B) (NIL . B)) (NIL . B)) ((7 . R) (NIL . B) (NIL . B))) 3 B 5 R 7 B) '((5 . R) ((3 . B) ((2 . R) (NIL . B) (NIL . B)) (NIL . B)) ((7 . B) (NIL . B) (NIL . B)))) (EQUAL (Chng_Clr '((5 . B) ((3 . R) ((2 . R) (NIL . B) (NIL . B)) (NIL . B)) ((7 . B) (NIL . B) (NIL . B))) 3 B 5 R 7 B) '((5 . R) ((3 . B) ((2 . R) (NIL . B) (NIL . B)) (NIL . B)) ((7 . B) (NIL . B) (NIL . B)))) (EQUAL (Chng_Clr '((5 . B) ((3 . R) (NIL . B) (NIL . B)) ((7 . R) (NIL . B) ((8 . R) (NIL . B) (NIL . B)))) 7 B 5 R 3 B) '((5 . R) ((3 . B) (NIL . B) (NIL . B)) ((7 . B) (NIL . B) ((8 . R) (NIL . B) (NIL . B))))) (EQUAL (Chng_Clr '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((7 . R) (NIL . B) ((8 . R) (NIL . B) (NIL . B)))) 7 B 5 R 3 B) '((5 . R) ((3 . B) (NIL . B) (NIL . B)) ((7 . B) (NIL . B) ((8 . R) (NIL . B) (NIL . B))))) (EQUAL (Chng_Clr '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((7 . R) ((6 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B)))) 5 R 7 B 8 B) '((5 . R) ((3 . B) (NIL . B) (NIL . B)) ((7 . B) ((6 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B))))) (EQUAL (Chng_Clr '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((7 . B) ((6 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B)))) 5 R 7 R 8 B) '((5 . R) ((3 . B) (NIL . B) (NIL . B)) ((7 . R) ((6 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B))))) (EQUAL (Chng_Clr '((5 . R) ((3 . B) (NIL . B) (NIL . B)) ((7 . B) ((6 . B) (NIL . B) (NIL . B)) ((8 . R) (NIL . B) (NIL . B)))) 5 B 7 R 8 B) '((5 . B) ((3 . B) (NIL . B) (NIL . B)) ((7 . R) ((6 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B))))) (EQUAL (Chng_Clr '((5 . B) ((3 . R) ((2 . B) (NIL . B) (NIL . B)) ((4 . B) (NIL . B) (NIL . B))) ((7 . B) (NIL . B) (NIL . B))) 5 R 3 B 2 B) '((5 . R) ((3 . B) ((2 . B) (NIL . B) (NIL . B)) ((4 . B) (NIL . B) (NIL . B))) ((7 . B) (NIL . B) (NIL . B)))) (EQUAL (Chng_Clr '((5 . R) ((3 . B) ((2 . B) (NIL . B) (NIL . B)) ((4 . B) (NIL . B) (NIL . B))) ((7 . B) (NIL . B) (NIL . B))) 5 R 3 R 2 B) '((5 . R) ((3 . R) ((2 . B) (NIL . B) (NIL . B)) ((4 . B) (NIL . B) (NIL . B))) ((7 . B) (NIL . B) (NIL . B)))) (EQUAL (Chng_Clr '((5 . R) ((3 . B) ((2 . R) (NIL . B) (NIL . B)) ((4 . B) (NIL . B) (NIL . B))) ((7 . B) (NIL . B) (NIL . B))) 5 B 3 R 2 B) '((5 . B) ((3 . R) ((2 . B) (NIL . B) (NIL . B)) ((4 . B) (NIL . B) (NIL . B))) ((7 . B) (NIL . B) (NIL . B)))) ; ------------------------------------------------------- "Root - функция, возвращающая ключ корня бинарного дерева поиска Tree с NIL-узлами" ; --------------------------- (EQUAL (Root '(NIL . B)) NIL) (EQUAL (Root '((2 . A) (NIL . B) (NIL . B))) 2) (EQUAL (Root '((1 . A) ((2 . B) ((3 . C) (NIL . B) (NIL . B)) (NIL . B)) (NIL . B))) 1) (EQUAL (Root '((4 . A) ((2 . B) ((1 . C) (NIL . B) (NIL . B)) ((3 . D) (NIL . B) (NIL . B))) (6 (NIL . B) (NIL . B)))) 4) (EQUAL (Root '((5 . A) ((3 . B) ((1 . C) (NIL . B) (NIL . B)) ((4 . D) (NIL . B) (NIL . B))) ((7 . E) ((6 . F) (NIL . B) (NIL . B))))) 5) ; ------------------------------------------------------------ "Left - функция, возвращающая левое поддерево бинарного дерева поиска Tree с NIL-узлами" ; --------------------------- (EQUAL (Left '(NIL . B)) NIL) (EQUAL (Left '((5 . A) (NIL . B) (NIL . B))) '(NIL . B)) (EQUAL (Left '((4 . A) (NIL . B) ((6 . B) ((5 . C) (NIL . B) (NIL . B)) ((25 . D) (NIL . B) ((28 . E) (NIL . B) (NIL . B)))))) '(NIL . B)) (EQUAL (Left '((5 . A) ((3 . B) ((1 . C) (NIL . B) (NIL . B)) (NIL . B)) (NIL . B))) '((3 . B) ((1 . C) (NIL . B) (NIL . B)) (NIL . B))) (EQUAL (Left '((4 . A) ((2 . B) ((1 . C) (NIL . B) (NIL . B)) ((3 . D) (NIL . B) (NIL . B))) ((6 . E) (NIL . B) (NIL . B)))) '((2 . B) ((1 . C) (NIL . B) (NIL . B)) ((3 . D) (NIL . B) (NIL . B)))) ; -------------------------------------------------------------- "Right - функция, возвращающая правое поддерево бинарного дерева поиска Tree с NIL-узлами" ; ---------------------------- (EQUAL (Right '(NIL . B)) NIL) (EQUAL (Right '((2 . A) (NIL . B) (NIL . B))) '(NIL . B)) (EQUAL (Right '((5 . A) ((2 . B) ((4 . C) ((3 . D) (NIL . B) (NIL . B)) (NIL . B)) (NIL . B)) (NIL . B))) '(NIL . B)) (EQUAL (Right '((5 . A) (NIL . B) ((6 . B) ((7 . C) (NIL . B) (NIL . B)) (NIL . B)))) '((6 . B) ((7 . C) (NIL . B) (NIL . B)) (NIL . B))) (EQUAL (Right '((5 . A) ((3 . B) ((1 . C) (NIL . B) (NIL . B)) ((4 . D) (NIL . B) (NIL . B))) ((7 . E) ((6 . F) (NIL . B) (NIL . B)) (NIL . B)))) '((7 . E) ((6 . F) (NIL . B) (NIL . B)) (NIL . B))) ; ---------------------------------------------------------- "AddTree - функция добавления узла с ключом S и цветом Color в бинарное дерево поиска Tree с NIL-узлами" ; ------------------------------------------------------------- (EQUAL (AddTree 2 R '(NIL . B)) '((2 . R) (NIL . B) (NIL . B))) (EQUAL (AddTree -3 R '((5 . B) (NIL . B) (NIL . B))) '((5 . B) ((-3 . R) (NIL . B) (NIL . B)) (NIL . B)) ) (EQUAL (AddTree 7 R '((5 . B) (NIL . B) (NIL . B))) '((5 . B) (NIL . B) ((7 . R) (NIL . B) (NIL . B))) ) (EQUAL (AddTree 6 R '((5 . B) ((-2 . R) (NIL . B) ((3 . B) (NIL . B) (NIL . B))) (NIL . B))) '((5 . B) ((-2 . R) (NIL . B) ((3 . B) (NIL . B) (NIL . B))) ((6 . R) (NIL . B) (NIL . B)))) (EQUAL (AddTree 4 R '((6 . R) ((5 . B) (NIL . B) (NIL . B)) ((9 . B) ((7 . G) (NIL . B) (NIL . B)) ((18 . B) (NIL . B) (NIL . B))))) '((6 . R) ((5 . B) ((4 . R) (NIL . B) (NIL . B)) (NIL . B)) ((9 . B) ((7 . G) (NIL . B) (NIL . B)) ((18 . B) (NIL . B) (NIL . B)))) ) (EQUAL (AddTree 7 R '((5 . B) ((3 . B) ((1 . R) (NIL . B) (NIL . B)) ((4 . R) (NIL . B) (NIL . B))) ((8 . R) ((6 . B) (NIL . B) (NIL . B)) (NIL . B)))) '((5 . B) ((3 . B) ((1 . R) (NIL . B) (NIL . B)) ((4 . R) (NIL . B) (NIL . B))) ((8 . R) ((6 . B) (NIL . B) ((7 . R) (NIL . B) (NIL . B))) (NIL . B)))) ; ------------------------------------------------------------ "Delete - функция удаления узла с ключом S из бинарного дерева поиска Tree с NIL-узлами" ; -------------------------------------- (EQUAL (Delete 1 '(NIL . B)) '(NIL . B)) (EQUAL (Delete 1 '((1 . B) (NIL . B) (NIL . B))) '(NIL . B)) (EQUAL (Delete 5 '((5 . B) ((3 . R) (NIL . B) (NIL . B)) (NIL . B))) '((3 . R) (NIL . B) (NIL . B))) (EQUAL (Delete 5 '((5 . B) (NIL . B) ((7 . R) (NIL . B) (NIL . B)))) '((7 . R) (NIL . B) (NIL . B))) (EQUAL (Delete 5 '((5 . B) ((3 . R) (NIL . B) (NIL . B)) ((7 . R) (NIL . B) (NIL . B)))) '((7 . R) ((3 . R) (NIL . B) (NIL . B)) (NIL . B))) (EQUAL (Delete 2 '((4 . B) ((2 . R) ((1 . B) (NIL . B) (NIL . B)) ((3 . B) (NIL . B) (NIL . B))) ((6 . R) ((5 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B))))) '((4 . B) ((3 . B) ((1 . B) (NIL . B) (NIL . B)) (NIL . B)) ((6 . R) ((5 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B))))) (EQUAL (Delete 4 '((4 . B) ((3 . B) ((1 . B) (NIL . B) (NIL . B)) (NIL . B)) ((6 . R) ((5 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B))))) '((5 . B) ((3 . B) ((1 . B) (NIL . B) (NIL . B)) (NIL . B)) ((6 . R) (NIL . B) ((8 . B) (NIL . B) (NIL . B))))) (EQUAL (Delete 3 '((4 . B) ((2 . R) ((1 . B) (NIL . B) (NIL . B)) ((3 . B) (NIL . B) (NIL . B))) ((6 . R) ((5 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B))))) '((4 . B) ((2 . R) ((1 . B) (NIL . B) (NIL . B)) (NIL . B)) ((6 . R) ((5 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B))))) (EQUAL (Delete 6 '((4 . B) ((2 . R) ((1 . B) (NIL . B) (NIL . B)) ((3 . B) (NIL . B) (NIL . B))) ((6 . R) ((5 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B))))) '((4 . B) ((2 . R) ((1 . B) (NIL . B) (NIL . B)) ((3 . B) (NIL . B) (NIL . B))) ((8 . B) ((5 . B) (NIL . B) (NIL . B)) (NIL . B)))) (EQUAL (Delete 6 '((4 . B) ((2 . R) ((1 . B) (NIL . B) (NIL . B)) ((3 . B) (NIL . B) (NIL . B))) ((6 . R) ((5 . B) (NIL . B) (NIL . B)) ((8 . B) ((7 . R) (NIL . B) (NIL . B)) (NIL . B))))) '((4 . B) ((2 . R) ((1 . B) (NIL . B) (NIL . B)) ((3 . B) (NIL . B) (NIL . B))) ((7 . R) ((5 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B))))) (EQUAL (Delete 8 '((4 . B) ((2 . R) ((1 . B) (NIL . B) (NIL . B)) ((3 . B) (NIL . B) (NIL . B))) ((6 . R) ((5 . B) (NIL . B) (NIL . B)) ((8 . B) ((7 . R) (NIL . B) (NIL . B)) (NIL . B))))) '((4 . B) ((2 . R) ((1 . B) (NIL . B) (NIL . B)) ((3 . B) (NIL . B) (NIL . B))) ((6 . R) ((5 . B) (NIL . B) (NIL . B)) ((7 . R) (NIL . B) (NIL . B))))) ; -------------------------------------------------------- "Ud - функция, возвращающая узел с минимальным ключом бинарного дерева поиска Tree с NIL-узлами" ; ------------------------------------------ (EQUAL (Ud '(NIL . B)) NIL) (EQUAL (Ud '((1 . B) (NIL . B) (NIL . B))) '(1 . B)) (EQUAL (Ud '((5 . B) ((3 . R) (NIL . B) (NIL . B)) (NIL . B))) '(3 . R)) (EQUAL (Ud '((4 . B) ((2 . R) ((1 . B) (NIL . B) (NIL . B)) ((3 . B) (NIL . B) (NIL . B))) ((6 . R) ((5 . B) (NIL . B) (NIL . B)) ((8 . B) (NIL . B) (NIL . B))))) '(1 . B)) (EQUAL (Ud '((5 . A) ((3 . B) ((1 . C) (NIL . B) (NIL . B)) (NIL . B)) (NIL . B))) '(1 . C)) (EQUAL (Ud '((4 . A) (NIL . B) ((6 . B) ((5 . C) (NIL . B) (NIL . B)) ((25 . D) (NIL . B) ((28 . E) (NIL . B) (NIL . B)))))) '(4 . A)) ; ----------------------------------------------------- "Srch - предикат, устанавливающий вхождение заданного S элемента в бинарное дерево поиска Tree с NIL-узлами" ; ------------------------------------------------------ (EQUAL (Srch A '(NIL . B)) NIL) (EQUAL (Srch R '((A . B) ((B . R) (NIL . B) ((D . G) (NIL . B) (NIL . B))) ((C . R) ((E . G) (NIL . B) (NIL . B)) ((F . B) (NIL . B) (NIL . B))))) NIL) (EQUAL (Srch A '((A . W) ((B . L) (NIL . B) ((D . Y) (NIL . B) (NIL . B))) ((C . T) ((E . I) (NIL . B) (NIL . B)) ((F . Y) (NIL . B) (NIL . B))))) T) (EQUAL (Srch D '((A . Q) ((B . W) (NIL . B) ((D . I) (NIL . B) (NIL . B))) ((C . S) ((E . F) (NIL . B) (NIL . B)) ((F . P) (NIL . B) (NIL . B))))) T) (EQUAL (Srch E '((A . Q) ((B . W) (NIL . B) ((D . P) (NIL . B) (NIL . B))) ((C . K) ((E . H) (NIL . B) (NIL . B)) ((F . L) (NIL . B) (NIL . B))))) T) (EQUAL (Srch C '((A . D) ((B . F) (NIL . B) ((D . L) (NIL . B) (NIL . B))) ((C . V) ((E . N) (NIL . B) (NIL . B)) ((F . C) (NIL . B) (NIL . B))))) T) ; ------------------------------------------------------------- "Search - функция, которая по заданному ключу S возвращает поддерево бинарного дерева поиска Tree, корнем кото- рого является элемент с ключом S" ; ------------------------------------------------------- (EQUAL (Search 18 '((4 . A) ((2 . B) (NIL . B) (NIL . B)) ((6 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Search 5 '((5 . A) ((3 . B) ((1 . C) (NIL . B) (NIL . B)) ((4 . D) (NIL . B) (NIL . B))) ((7 . E) ((6 . F) (NIL . B) (NIL . B)) (NIL . B)))) '((5 . A) ((3 . B) ((1 . C) (NIL . B) (NIL . B)) ((4 . D) (NIL . B) (NIL . B))) ((7 . E) ((6 . F) (NIL . B) (NIL . B)) (NIL . B)))) (EQUAL (Search 3 '((5 . A) ((3 . B) ((1 . C) (NIL . B) (NIL . B)) ((4 . D) (NIL . B) (NIL . B))) ((7 . E) ((6 . F) (NIL . B) (NIL . B)) (NIL . B)))) '((3 . B) ((1 . C) (NIL . B) (NIL . B)) ((4 . D) (NIL . B) (NIL . B)))) (EQUAL (Search 1 '((4 . A) ((2 . B) ((1 . C) (NIL . B) (NIL . B)) ((3 . D) (NIL . B) (NIL . B))) ((6 . E) (NIL . B) (NIL . B)))) '((1 . C) (NIL . B) (NIL . B))) (EQUAL (Search 6 '((5 . A) ((3 . B) ((1 . C) (NIL . B) (NIL . B)) ((4 . D) (NIL . B) (NIL . B))) ((7 . E) ((6 . F) (NIL . B) (NIL . B)) (NIL . B)))) '((6 . F) (NIL . B) (NIL . B))) ; --------------------------------------------------------- "Subst - функция замены в многоуровневом списке LST на всех уровнях всех вхождений элемента A на элемент B" ; -------------------------------------------------- (EQUAL (Subst '((A (C (A))) A (A)) A F) '((F (C (F))) F (F))) (EQUAL (Subst '(A (A (B A)) (A) ((B A) A) A) A '(X (Y))) '((X (Y)) ((X (Y)) (B (X (Y)))) ((X (Y))) ((B (X (Y))) (X (Y))) (X (Y)))) (EQUAL (Subst '((A B (A B)) A B ((A B))) '(A B) F) '((A B F) A B (F))) (EQUAL (Subst '(B A ((A ((B)) (A))) A (A) A B) '(A) '((C))) '(B A ((A ((B)) ((C)))) A ((C)) A B)) (EQUAL (Subst '((4 . A) ((2 . B) ((1 . C) (NIL . B) (NIL . B)) ((3 . D) (NIL . B) (NIL . B))) ((6 . E) (NIL . B) (NIL . B))) '(6 . E) '(8 . I)) '((4 . A) ((2 . B) ((1 . C) (NIL . B) (NIL . B)) ((3 . D) (NIL . B) (NIL . B))) ((8 . I) (NIL . B) (NIL . B)))) (EQUAL (Subst '((4 . A) ((2 . B) ((1 . C) (NIL . B) (NIL . B)) ((3 . D) (NIL . B) (NIL . B))) ((6 . E) (NIL . B) (NIL . B))) '(1 . C) '(-1 . I)) '((4 . A) ((2 . B) ((-1 . I) (NIL . B) (NIL . B)) ((3 . D) (NIL . B) (NIL . B))) ((6 . E) (NIL . B) (NIL . B)))) ; ------------------------------------------------------------- "Srch_G - функция поиска ключа 'дедушки' для заданной вершины S в бинарном дереве поиска с NIL-узлами" ; ------------------------------------------ (EQUAL (Srch_G 7 '(NIL . B)) NIL) (EQUAL (Srch_G 4 '((5 . A) ((3 . B) ((2 . C) (NIL . B) (NIL . B)) ((4 . D) (NIL . B) (NIL . B))) ((6 . E) (NIL . B) (NIL . B)))) 5) (EQUAL (Srch_G 7 '((5 . A) ((3 . B) ((2 . C) (NIL . B) (NIL . B)) ((4 . D) (NIL . B) (NIL . B))) ((6 . E) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_G 3 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_G 4 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_G 5 '((4 . A) ((2 . B) (NIL . B) ((3 . C) (NIL . B) (NIL . B))) ((6 . D) ((5 . E) (NIL . B) (NIL . B)) ((7 . F) (NIL . B) (NIL . B))))) 4) (EQUAL (Srch_G 3 '((4 . A) ((2 . B) (NIL . B) ((3 . C) (NIL . B) (NIL . B))) ((6 . D) ((5 . E) (NIL . B) (NIL . B)) ((7 . F) (NIL . B) (NIL . B))))) 4) (EQUAL (Srch_G 8 '((10 . A) ((6 . B) ((3 . C) (NIL . B) (NIL . B)) ((7 . D) (NIL . B) ((8 . E) (NIL . B) (NIL . B)))) ((15 . F) ((12 . G) (NIL . B) (NIL . B)) ((18 . H) ((17 . I) (NIL . B) (NIL . B)) (NIL . B))))) 6) ; ----------------------------------------------------------- "Srch_D - функция поиска ключа 'отца' для заданной вершины S в бинарном дереве поиска с NIL-узлами" ; ------------------------------------------ (EQUAL (Srch_D 5 '(NIL . B)) NIL) (EQUAL (Srch_D 3 '((1 . B) (NIL . B) ((2 . R) (NIL . B) ((3 . R) (NIL . B) (NIL . B))))) 2) (EQUAL (Srch_D 5 '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) ((7 . E) (NIL . B) (NIL . B)))) 4) (EQUAL (Srch_D 8 '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) ((7 . E) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_D 8 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_D 3 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) 4) (EQUAL (Srch_D 5 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) 4) (EQUAL (Srch_D 4 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_D 5 '((4 . A) ((2 . B) (NIL . B) ((3 . C) (NIL . B) (NIL . B))) ((6 . D) ((5 . E) (NIL . B) (NIL . B)) ((7 . F) (NIL . B) (NIL . B))))) 6) (EQUAL (Srch_D 6 '((4 . A) ((2 . B) (NIL . B) ((3 . C) (NIL . B) (NIL . B))) ((6 . D) ((5 . E) (NIL . B) (NIL . B)) ((7 . F) (NIL . B) (NIL . B))))) 4) (EQUAL (Srch_D 17 '((10 . A) ((6 . B) ((3 . C) (NIL . B) (NIL . B)) ((7 . D) (NIL . B) ((8 . E) (NIL . B) (NIL . B)))) ((15 . F) ((12 . G) (NIL . B) (NIL . B)) ((18 . H) ((17 . I) (NIL . B) (NIL . B)) (NIL . B))))) 18) (EQUAL (Srch_D 7 '((10 . A) ((6 . B) ((3 . C) (NIL . B) (NIL . B)) ((7 . D) (NIL . B) ((8 . E) (NIL . B) (NIL . B)))) ((15 . F) ((12 . G) (NIL . B) (NIL . B)) ((18 . H) ((17 . I) (NIL . B) (NIL . B)) (NIL . B))))) 6) ; ----------------------------------------------------------- "Srch_B - функция поиска ключа 'брата' для заданной вершины S в бинарном дереве поиска с NIL-узлами" ; ------------------------------------------ (EQUAL (Srch_B 5 '(NIL . B)) NIL) (EQUAL (Srch_B 3 '((1 . B) (NIL . B) ((2 . R) (NIL . B) ((3 . R) (NIL . B) (NIL . B))))) NIL) (EQUAL (Srch_B 5 '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) ((7 . E) (NIL . B) (NIL . B)))) 3) (EQUAL (Srch_B 4 '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) ((7 . E) (NIL . B) (NIL . B)))) 7) (EQUAL (Srch_B 8 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_B 3 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) 5) (EQUAL (Srch_B 5 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) 3) (EQUAL (Srch_B 4 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_B 5 '((4 . A) ((2 . B) (NIL . B) ((3 . C) (NIL . B) (NIL . B))) ((6 . D) ((5 . E) (NIL . B) (NIL . B)) ((7 . F) (NIL . B) (NIL . B))))) 7) (EQUAL (Srch_B 7 '((4 . A) ((2 . B) (NIL . B) ((3 . C) (NIL . B) (NIL . B))) ((6 . D) ((5 . E) (NIL . B) (NIL . B)) ((7 . F) (NIL . B) (NIL . B))))) 5) (EQUAL (Srch_B 17 '((10 . A) ((6 . B) ((3 . C) (NIL . B) (NIL . B)) ((7 . D) (NIL . B) ((8 . E) (NIL . B) (NIL . B)))) ((15 . F) ((12 . G) (NIL . B) (NIL . B)) ((18 . H) ((17 . I) (NIL . B) (NIL . B)) (NIL . B))))) NIL) (EQUAL (Srch_B 8 '((10 . A) ((6 . B) ((3 . C) (NIL . B) (NIL . B)) ((7 . D) (NIL . B) ((8 . E) (NIL . B) (NIL . B)))) ((15 . F) ((12 . G) (NIL . B) (NIL . B)) ((18 . H) ((17 . I) (NIL . B) (NIL . B)) (NIL . B))))) NIL) ; ----------------------------------------------------------- "Srch_Nl - функция поиска ключа 'племянника (левого)' для за- данной вершины S в бинарном дереве поиска с NIL-узлами" ; ------------------------------------------------------------ (EQUAL (Srch_Nl 5 '(NIL . B)) NIL) (EQUAL (Srch_Nl 3 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_Nl 5 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_Nl 4 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_Nl 7 '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) ((7 . E) (NIL . B) (NIL . B)))) 3) (EQUAL (Srch_Nl 4 '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) ((8 . E) ((7 . F) (NIL . B) (NIL . B)) ((9 . G) (NIL . B) (NIL . B))))) 7) (EQUAL (Srch_Nl 12 '((10 . A) ((6 . B) ((3 . C) (NIL . B) (NIL . B)) ((7 . D) (NIL . B) ((8 . E) (NIL . B) (NIL . B)))) ((15 . F) ((12 . G) (NIL . B) (NIL . B)) ((18 . H) ((17 . I) (NIL . B) (NIL . B)) (NIL . B))))) 17) (EQUAL (Srch_Nl 17 '((10 . A) ((6 . B) ((3 . C) (NIL . B) (NIL . B)) ((7 . D) (NIL . B) ((8 . E) (NIL . B) (NIL . B)))) ((15 . F) ((12 . G) (NIL . B) (NIL . B)) ((18 . H) ((17 . I) (NIL . B) (NIL . B)) (NIL . B))))) NIL) (EQUAL (Srch_Nl 3 '((10 . A) ((6 . B) ((3 . C) (NIL . B) (NIL . B)) ((7 . D) (NIL . B) ((8 . E) (NIL . B) (NIL . B)))) ((15 . F) ((12 . G) (NIL . B) (NIL . B)) ((18 . H) ((17 . I) (NIL . B) (NIL . B)) (NIL . B))))) NIL) ; ------------------------------------------------------------ "Srch_Nr - функция поиска ключа 'племянника (правого)' для за- данной вершины S в бинарном дереве поиска с NIL-узлами" ; ------------------------------------------------------------- (EQUAL (Srch_Nr 5 '(NIL . B)) NIL) (EQUAL (Srch_Nr 3 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_Nr 5 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_Nr 4 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_Nr 7 '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) ((7 . E) (NIL . B) (NIL . B)))) 5) (EQUAL (Srch_Nr 4 '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) ((8 . E) ((7 . F) (NIL . B) (NIL . B)) ((9 . G) (NIL . B) (NIL . B))))) 9) (EQUAL (Srch_Nr 6 '((10 . A) ((6 . B) ((3 . C) (NIL . B) (NIL . B)) ((7 . D) (NIL . B) ((8 . E) (NIL . B) (NIL . B)))) ((15 . F) ((12 . G) (NIL . B) (NIL . B)) ((18 . H) ((17 . I) (NIL . B) (NIL . B)) (NIL . B))))) 18) (EQUAL (Srch_Nr 7 '((10 . A) ((6 . B) ((3 . C) (NIL . B) (NIL . B)) ((7 . D) (NIL . B) ((8 . E) (NIL . B) (NIL . B)))) ((15 . F) ((12 . G) (NIL . B) (NIL . B)) ((18 . H) ((17 . I) (NIL . B) (NIL . B)) (NIL . B))))) NIL) (EQUAL (Srch_Nr 15 '((10 . A) ((6 . B) ((3 . C) (NIL . B) (NIL . B)) ((7 . D) (NIL . B) ((8 . E) (NIL . B) (NIL . B)))) ((15 . F) ((12 . G) (NIL . B) (NIL . B)) ((18 . H) ((17 . I) (NIL . B) (NIL . B)) (NIL . B))))) 7) ; ---------------------------------------------------------- "Srch_U - функция поиска ключа 'дяди' для заданной вершины S в бинарном дереве поиска с NIL-узлами" ; ------------------------------------------ (EQUAL (Srch_U 5 '(NIL . B)) NIL) (EQUAL (Srch_U 4 '((5 . A) ((3 . B) (NIL . B) ((4 . B) (NIL . B) (NIL . B))) (NIL . B))) NIL) (EQUAL (Srch_U 5 '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) ((7 . E) (NIL . B) (NIL . B)))) 7) (EQUAL (Srch_U 8 '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) ((7 . E) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_U 8 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_U 3 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_U 5 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_U 4 '((4 . A) ((3 . B) (NIL . B) (NIL . B)) ((5 . C) (NIL . B) (NIL . B)))) NIL) (EQUAL (Srch_U 5 '((4 . A) ((2 . B) (NIL . B) ((3 . C) (NIL . B) (NIL . B))) ((6 . D) ((5 . E) (NIL . B) (NIL . B)) ((7 . F) (NIL . B) (NIL . B))))) 2) (EQUAL (Srch_U 7 '((4 . A) ((2 . B) (NIL . B) ((3 . C) (NIL . B) (NIL . B))) ((6 . D) ((5 . E) (NIL . B) (NIL . B)) ((7 . F) (NIL . B) (NIL . B))))) 2) (EQUAL (Srch_U 17 '((10 . A) ((6 . B) ((3 . C) (NIL . B) (NIL . B)) ((7 . D) (NIL . B) ((8 . E) (NIL . B) (NIL . B)))) ((15 . F) ((12 . G) (NIL . B) (NIL . B)) ((18 . H) ((17 . I) (NIL . B) (NIL . B)) (NIL . B))))) 12) (EQUAL (Srch_U 7 '((10 . A) ((6 . B) ((3 . C) (NIL . B) (NIL . B)) ((7 . D) (NIL . B) ((8 . E) (NIL . B) (NIL . B)))) ((15 . F) ((12 . G) (NIL . B) (NIL . B)) ((18 . H) ((17 . I) (NIL . B) (NIL . B)) (NIL . B))))) 15) ; ---------------------------------------------------------- "Rot_Right - функция, моделирующая операцию 'ротация вправо' в бинарном дереве поиска Tree с NIL-узлами" ; -------------------------------------------------- (EQUAL (Rot_Right '(NIL . B)) '(NIL . B)) (EQUAL (Rot_Right '((3 . A) (NIL . B) (NIL . B))) '((3 . A) (NIL . B) (NIL . B))) (EQUAL (Rot_Right '((5 . A) (NIL . B) ((7 . B) ((6 . C) (NIL . B) (NIL . B)) ((8 . D) (NIL . B) (NIL . B))))) '((5 . A) (NIL . B) ((7 . B) ((6 . C) (NIL . B) (NIL . B)) ((8 . D) (NIL . B) (NIL . B))))) (EQUAL (Rot_Right '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) (NIL . B))) '((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((6 . A) ((5 . D) (NIL . B) (NIL . B)) (NIL . B)))) (EQUAL (Rot_Right '((15 . A) ((11 . B) ((8 . C) ((7 . D) (NIL . B) (NIL . B)) ((10 . E) (NIL . B) (NIL . B))) ((13 . F) ((12 . G) (NIL . B) (NIL . B)) ((14 . H) (NIL . B) (NIL . B)))) ((20 . I) ((16 . J) (NIL . B) (NIL . B)) ((22 . K) (NIL . B) (NIL . B))))) '((11 . B) ((8 . C) ((7 . D) (NIL . B) (NIL . B)) ((10 . E) (NIL . B) (NIL . B))) ((15 . A) ((13 . F) ((12 . G) (NIL . B) (NIL . B)) ((14 . H) (NIL . B) (NIL . B))) ((20 . I) ((16 . J) (NIL . B) (NIL . B)) ((22 . K) (NIL . B) (NIL . B)))))) ; -------------------------------------------------------- "Rot_Left - функция, моделирующая операцию 'ротация влево' в бинарном дереве поиска Tree с NIL-узлами" ; ------------------------------------------------- (EQUAL (Rot_Left '(NIL . B)) '(NIL . B)) (EQUAL (Rot_Left '((2 . A) (NIL . B) (NIL . B))) '((2 . A) (NIL . B) (NIL . B))) (EQUAL (Rot_Left '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) (NIL . B))) '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) (NIL . B))) (EQUAL (Rot_Left '((5 . A) (NIL . B) ((7 . B) ((6 . C) (NIL . B) (NIL . B)) ((8 . D) (NIL . B) (NIL . B))))) '((7 . B) ((5 . A) (NIL . B) ((6 . C) (NIL . B) (NIL . B))) ((8 . D) (NIL . B) (NIL . B)))) (EQUAL (Rot_Left '((15 . A) ((11 . B) ((8 . C) ((7 . D) (NIL . B) (NIL . B)) ((10 . E) (NIL . B) (NIL . B))) ((13 . F) ((12 . G) (NIL . B) (NIL . B)) ((14 . H) (NIL . B) (NIL . B)))) ((20 . I) ((16 . J) (NIL . B) (NIL . B)) ((22 . K) (NIL . B) (NIL . B))))) '((20 . I) ((15 . A) ((11 . B) ((8 . C) ((7 . D) (NIL . B) (NIL . B)) ((10 . E) (NIL . B) (NIL . B))) ((13 . F) ((12 . G) (NIL . B) (NIL . B)) ((14 . H) (NIL . B) (NIL . B)))) ((16 . J) (NIL . B) (NIL . B))) ((22 . K) (NIL . B) (NIL . B)))) ; ----------------------------------------------------- "RotInTree - ротация части бинарного дерева поиска Tree с NIL-узлами, корнем которого является узел с ключом S" ; ----------------------------------------- (EQUAL (RotInTree 2 '(NIL . B)) '(NIL . B)) (EQUAL (RotInTree 1 '((1 . A) (NIL . B) (NIL . B))) '((1 . A) (NIL . B) (NIL . B))) (EQUAL (RotInTree 2 '((1 . A) (NIL . B) (NIL . B))) '((1 . A) (NIL . B) (NIL . B))) (EQUAL (RotInTree 5 '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) (NIL . B))) '((6 . A) ((5 . D) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) (NIL . B)) (NIL . B)) (NIL . B))) (EQUAL (RotInTree 6 '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) (NIL . B))) '((6 . A) ((4 . B) ((3 . C) (NIL . B) (NIL . B)) ((5 . D) (NIL . B) (NIL . B))) (NIL . B))) (EQUAL (RotInTree 6 '((5 . A) (NIL . B) ((7 . B) ((6 . C) (NIL . B) (NIL . B)) ((8 . D) (NIL . B) (NIL . B))))) '((5 . A) (NIL . B) ((6 . C) (NIL . B) ((7 . B) (NIL . B) ((8 . D) (NIL . B) (NIL . B)))))) (EQUAL (RotInTree 7 '((5 . A) (NIL . B) ((7 . B) ((6 . C) (NIL . B) (NIL . B)) ((8 . D) (NIL . B) (NIL . B))))) '((7 . B) ((5 . A) (NIL . B) ((6 . C) (NIL . B) (NIL . B))) ((8 . D) (NIL . B) (NIL . B)))) (EQUAL (RotInTree 13 '((15 . A) ((11 . B) ((8 . C) ((7 . D) (NIL . B) (NIL . B)) ((10 . E) (NIL . B) (NIL . B))) ((13 . F) ((12 . G) (NIL . B) (NIL . B)) ((14 . H) (NIL . B) (NIL . B)))) ((20 . I) ((16 . J) (NIL . B) (NIL . B)) ((22 . K) (NIL . B) (NIL . B))))) '((15 . A) ((13 . F) ((11 . B) ((8 . C) ((7 . D) (NIL . B) (NIL . B)) ((10 . E) (NIL . B) (NIL . B))) ((12 . G) (NIL . B) (NIL . B))) ((14 . H) (NIL . B) (NIL . B))) ((20 . I) ((16 . J) (NIL . B) (NIL . B)) ((22 . K) (NIL . B) (NIL . B))))) (EQUAL (RotInTree 11 '((15 . A) ((11 . B) ((8 . C) ((7 . D) (NIL . B) (NIL . B)) ((10 . E) (NIL . B) (NIL . B))) ((13 . F) ((12 . G) (NIL . B) (NIL . B)) ((14 . H) (NIL . B) (NIL . B)))) ((20 . I) ((16 . J) (NIL . B) (NIL . B)) ((22 . K) (NIL . B) (NIL . B))))) '((11 . B) ((8 . C) ((7 . D) (NIL . B) (NIL . B)) ((10 . E) (NIL . B) (NIL . B))) ((15 . A) ((13 . F) ((12 . G) (NIL . B) (NIL . B)) ((14 . H) (NIL . B) (NIL . B))) ((20 . I) ((16 . J) (NIL . B) (NIL . B)) ((22 . K) (NIL . B) (NIL . B)))))) (EQUAL (RotInTree 10 '((15 . A) ((11 . B) ((8 . C) ((7 . D) (NIL . B) (NIL . B)) ((10 . E) (NIL . B) (NIL . B))) ((13 . F) ((12 . G) (NIL . B) (NIL . B)) ((14 . H) (NIL . B) (NIL . B)))) ((20 . I) ((16 . J) (NIL . B) (NIL . B)) ((22 . K) (NIL . B) (NIL . B))))) '((15 . A) ((11 . B) ((10 . E) ((8 . C) ((7 . D) (NIL . B) (NIL . B)) (NIL . B)) (NIL . B)) ((13 . F) ((12 . G) (NIL . B) (NIL . B)) ((14 . H) (NIL . B) (NIL . B)))) ((20 . I) ((16 . J) (NIL . B) (NIL . B)) ((22 . K) (NIL . B) (NIL . B))))) ; -------------------------------------------------------- "OutTree - графическое изображение бинарного дерева поиска Tree с NIL-узлами" ; ------------------------------ "Графическое изображение дерева: '((4 . B) ((3 . R) (NIL . B) (NIL . B)) ((5 . R) (NIL . B) (NIL . B)))" (OutTree '((4 . B) ((3 . R) (NIL . B) (NIL . B)) ((5 . R) (NIL . B) (NIL . B))) 0) "" "Графическое изображение дерева: '((10 . B) ((3 . B) ((2 . B) (NIL . B) (NIL . B)) ((8 . R) ((5 . B) ((1 . R) (NIL . B) (NIL . B)) (NIL . B)) ((9 . B) (NIL . B) (NIL . B)))) ((13 . B) ((12 . B) (NIL . B) (NIL . B)) ((18 . R) ((15 . B) ((14 . R) (NIL . B) (NIL . B)) (NIL . B)) ((19 . B) (NIL . B) (NIL . B)))))" (OutTree '((10 . B) ((3 . B) ((2 . B) (NIL . B) (NIL . B)) ((8 . R) ((5 . B) ((4 . R) (NIL . B) (NIL . B)) (NIL . B)) ((9 . B) (NIL . B) (NIL . B)))) ((13 . B) ((12 . B) (NIL . B) (NIL . B)) ((18 . R) ((15 . B) ((14 . R) (NIL . B) (NIL . B)) (NIL . B)) ((19 . B) (NIL . B) (NIL . B))))) 0) ; ----------------------------------------------------------- (WRS) (SYSTEM) (RDS)
На следующем шаге мы рассмотрим реализацию красно-чёрных деревьев на языке Haskell.
