Шаг 170.
Основы языка Haskell. Рекурсивные типы данных. Красно-чёрные деревья, AA-деревья. Реализация красно-чёрных деревьев на языке LISP

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

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

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

   (NIL . B),
т.к. цвет их является чёрным.

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

   (NIL . B).

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

 

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

  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).

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




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