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

Красно-чёрное бинарное дерево поиска описательно представим так:

    (Корень(Цвет) Левое_поддерево Правое_поддерево).

Для моделирования этого представления в языке Haskell воспользуемся тернарным функтором

   (Node root left right),

где root - корень дерева, а left и right соответственно - левое и правое поддерево. Пустое дерево зададим функтором NIL.

Таким образом, определение типа данных "целочисленное красно-чёрное бинарное дерево поиска" в языке Haskell, поддерживающего класс типов Eq, над которыми определены отношения равенства, будет таким:

   data RBTree = NIL (Char)
               | Node (Integer,Char) (RBTree) (RBTree)
      deriving Eq

Узел дерева будем обозначать парой

   (Integer,Char),

первый элемент которой обозначает ключ узла (число), а второй элемент - цвет узла (красный - 'R' или чёрный - 'B').

Внешние узлы дерева (или NIL-узлы) будем обозначать парой

   (NIL ('B')),

т.к. цвет их является чёрным.

Пустое дерево состоит из одного внешнего чёрного узла и по определению является красно-чёрным, поэтому обозначим его парой

   (NIL ('B')).

Базовые функции лежащие в основе построения красно-чёрного бинарного дерева поиска Tree с NIL-узлами:

(1) определение корня бинарного дерева поиска tree:
```
   root:: RBTree -> (Integer,Char)
   root tree
```
(2) определение левого поддерева бинарного дерева поиска tree:
```
   left:: RBTree -> RBTree
   left tree
```
(3) определение правого поддерева бинарного дерева поиска tree:
```
   right:: RBTree -> RBTree
   right tree
```

Основные функции для построения красно-чёрных деревьев:

Вставка узла в красно-чёрное дерево:
```
   rb_Ins:: RBTree -> Integer -> RBTree
   rb_Ins tree s
```
Функция rb_Ins вызывает функцию rb_Ins1
```
   rb_Ins1:: RBTree -> Integer -> RBTree
   rb_Ins1 tree s
```
Функция rb_Ins1 анализирует и исправляет нарушения красно-чёрных свойств дерева tree, если таковы имеются, после вставки в него красного узла s с помощью функции addTree:
```
   addTree:: Integer -> Char -> RBTree -> RBTree
   addTree s color tree
```
Затем функция rb_Ins перекрашивает корень полученного дерева в чёрный цвет;
Удаление узла из красно-чёрного дерева:
```
   rb_Del:: RBTree -> Integer -> RBTree
   rb_Del tree s
```
Функция rb_Del анализирует дерево и применяет к нему, если возможно, функцию delete, удаляющую заданный узел s из красно-чёрного дерева tree:
```
   delete:: Integer -> RBTree -> RBTree
   delete s tree
```
Если полученное дерево имеет нарушения красно-чёрных свойств, то оно поступает на вход функции rb_Del1:
```
   rb_Del1:: RBTree -> Integer -> RBTree
   rb_Del1 tree x
```
Функция rb_Del1 восстанавливает красно-чёрные свойства дерева.

Вспомогательные предикаты для реализации основных функций:

Установление вхождения элемента s в красно-чёрное бинарное дерево поиска tree с NIL-узлами:
```
   srch:: Integer -> RBTree -> Bool
   srch s tree
```
Установление наличия вершины "дедушка" для заданной вершины s красно-чёрного бинарного дерева поиска tree с NIL-узлами:
```
   pSrch_G:: Integer -> RBTree -> Bool
   pSrch_G s tree
```
Установление наличия вершины "отец" для заданной вершины s красно-чёрного бинарного дерева поиска tree с NIL-узлами:
```
   pSrch_D:: Integer -> RBTree -> Bool
   pSrch_D s tree
```
Установление наличия вершины "брат" для заданной вершины s красно-чёрного бинарного дерева поиска tree с NIL-узлами:
```
   pSrch_B:: Integer -> RBTree -> Bool
   pSrch_B s tree
```
Установление наличия вершины "племянник" (слева) для заданной вершины s красно-чёрного бинарного дерева поиска tree с NIL-узлами:
```
   pSrch_Nl:: Integer -> RBTree -> Bool
   pSrch_Nl s tree
```
Установление наличия вершины "племянник" (справа) для заданной вершины s красно-чёрного бинарного дерева поиска tree с NIL-узлами:
```
   pSrch_Nr:: Integer -> RBTree -> Bool
   pSrch_Nr s tree
```
установление наличия вершины "дядя" для заданной вершины s красно-чёрного бинарного дерева поиска tree с NIL-узлами:
```
   pSrch_U:: Integer -> RBTree -> Bool
   pSrch_U s tree
```

Вспомогательные функции для реализации основных функций:

Определение поддерева красно-чёрного бинарного дерева поиска tree с корнем s (при отсутствии узла s возвращается пустое дерево):
```
   search:: Integer -> RBTree -> RBTree
   search s tree
```
Определение узла "дедушка" красно-чёрного бинарного дерева поиска tree с ключом s:
```
   srch_G:: Integer -> RBTree -> (Integer,Char)
   srch_G s tree
```
Определение узла "отец" красно-чёрного бинарного дерева поиска tree с ключом s:
```
   srch_D:: Integer -> RBTree -> (Integer,Char)
   srch_D s tree
```
Определение узла "брат" красно-чёрного бинарного дерева поиска tree с ключом s:
```
   srch_B:: Integer -> RBTree -> (Integer,Char)
   srch_B s tree
```
Определение узла "племянник" (слева) красно-чёрного бинарного дерева поиска tree с ключом s:
```
   srch_Nl:: Integer -> RBTree -> (Integer,Char)
   srch_Nl s tree
```
Определение узла "племянник" (справа) красно-чёрного бинарного дерева поиска tree с ключом s:
```
   srch_Nr:: Integer -> RBTree -> (Integer,Char)
   srch_Nr s tree
```
Определение узла "дядя" красно-чёрного бинарного дерева поиска tree с ключом s:
```
   srch_U:: Integer -> RBTree -> (Integer,Char)
   srch_U s tree
```
Замена всех вхождений узла a на узел b красно-чёрного дерева поиска tree:
```
   subst:: RBTree -> (Integer,Char) -> (Integer,Char) -> RBTree
   subst tree a b
```
Изменение цвета узла с указанным ключом v на заданный цвет clr_V в красно-чёрном бинарном дереве поиска tree:
```
   chng_Clr:: RBTree -> Integer -> Char -> RBTree
   chng_Clr tree v clr_V
```
Dыполнение операции "ротация вправо" в красно-чёрном бинарном дереве поиска tree:
```
   rot_Right:: RBTree -> RBTree
   rot_Right tree
```
Выполнение операции "ротация влево" в красно-чёрном бинарном дереве поиска tree:
```
   rot_Left:: RBTree -> RBTree
   rot_Left tree
```
Выполнение операции ротации, производимой над частью красно-чёрного бинарного дерева поиска tree, поднимая узел с указанным ключом s на уровень выше:
```
   rotInTree:: Integer -> RBTree -> RBTree
   rotInTree s tree
```
Изображение красно-чёрного бинарного дерева поиска tree на экране дисплея:
```
   outTree:: RBTree -> IO()
   outTree tree
```
Изображение красно-чёрного бинарного дерева поиска tree на экране дисплея в виде строки описания дерева (l - накапливающий параметр, значение которого при первоначальном обращении равно 0):
```
   drawTree:: RBTree -> Int -> String
   drawTree tree l
```

На следующем шаге мы рассмотрим демонстрационные примеры.

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