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

    Под  узел дерева выделим одну лисповскую ячейку памяти, моделируя его точечной парой: CAR-элемент которой обозначает ключ узла (число), а CDR-элемент - цвет узла (красный - R или чёрный - B).

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

   (NIL . B),

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

   (NIL . B).

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

• (1) (Root Tree) - ключ корня бинарного дерева поиска Tree;
• (2) (Left Tree) - левое поддерево бинарного дерева поиска Tree;
• (3) (Right Tree) - правое поддерево бинарного дерева поиска Tree.

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

1. (RB-Ins Tree S) - включение узла в красно-чёрное дерево.

       Она вызывает функцию RB-Ins1, анализирующую и исправляющую нарушения красно-чёрных свойств дерева Tree, если таковы имеются, после вставки в него с помощью функции AddTree красного узла S. Затем функция RB-Ins перекрашивает корень полученного дерева в чёрный цвет;

2. (RB-Del Tree S) - удаление узла из красно-чёрного дерева.

       Она анализирует дерево и применяет к нему, если возможно, функцию Delete, удаляющую заданный узел S из красно-чёрного дерева Tree. Если полученное дерево имеет нарушения красно-чёрных свойств, то оно поступает на вход функции RB-Del1, восстанавливающую его красно-чёрные свойства.

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

1. (Srch S Tree) - предикат, устанавливающий тот факт, имеется ли элемент S в бинарном дереве поиска Tree с NIL-узлами;
2. (Search S Tree) - возвращает поддерево бинарного дерева поиска Tree, в котором узел с ключом S является корнем с NIL-узлами;
3. (Srch_G S Tree) - возвращает ключ "дедушки" узла S бинарного дерева поиска Tree с NIL-узлами;
4. (Srch_D S Tree) - возвращает ключ "отца" узла S бинарного дерева поиска Tree с NIL-узлами;
5. (Srch_B S Tree) - возвращает ключ "брата" узла S бинарного дерева поиска Tree с NIL-узлами;
6. (Srch_Nl S Tree) - возвращает ключ "племянника (левого)" узла S бинарного дерева поиска Tree с NIL-узлами;
7. (Srch_Nr S Tree) - возвращает ключ "племянника (правого)" узла S бинарного дерева поиска Tree с NIL-узлами;
8. (Srch_U S Tree) - возвращает ключ "дяди" узла S бинарного дерева поиска Tree с NIL-узлами;
9. (Subst LST A B) - замена в многоуровневом списке LST всех вхождений непустого элемента A на элемент B (замена производится на всех уровнях);
10. (Chng_Clr Tree D Clr_D GvB Clr_GvB UvN Clr_UvN) - изменение цвета Clr_* в бинарном дереве поиска Tree с NIL-узлами следующих узлов: "отца" (D), "дедушки" или "брата" (GvB), "дяди" или "племянника"(UvN);
11. (Rot_Right Tree) - операция "ротация вправо" в бинарном дереве поиска Tree с NIL-узлами;
12. (Rot_Left Tree) - операция "ротация влево" в бинарном дереве поиска Tree с NIL-узлами;
13. (RotInTree S Tree) - операция ротации, производимая над частью бинарного дерева Tree с NIL-узлами, поднимая узел S на уровень выше;
14. (OutTree Tree L) - изображение красно-чёрного дерева Tree на экране дисплея (L - накапливающий параметр, значение которого при первоначальном обращении равно 0).

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

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