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

    На этом шаге мы введем некоторые общие понятия.

    Работа с бинарными деревьями более эффективна тогда, когда деревья сбалансированы, т.е. длина пути от корня до любого из листьев находится в определённых пределах, связанных с числом узлов.

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

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

    Красно-чёрные деревья были введены R.Bayer [1972], а затем их изучали и разрабатывали L.J.Guibas и R.Sedgewick [1978]. Название происходит от стандартной раскраски узлов таких деревьев в красный и чёрный цвета, используемые для балансировки дерева.

    Оценкой среднего (а также и наихудшего) времени поиска в красно-чёрных деревьев, содержащим n узлов, является

   O(log2n).


   Замечание. В стандартной библиотеке классов языка C++ (STL) исполнители "множество" и "нагруженное множество" (классы set и map) реализованы на базе красно-чёрных деревьев.
Определение (по [1, с.340]).
Красно-чёрное дерево - это бинарное дерево поиска со следующими свойствами:
  • (1) каждый узел может находится в одном из двух состояний, которые называются красным и чёрным (говорят, что каждый узел окрашен либо в красный, либо в чёрный цвет);
  • (2) каждый узел дерева, имеющий хотя бы одну нулевую дочернюю связь, указывает на "несуществующие" узлы, которые называются листьями (внешними узлами, NIL-листьями) и всегда окрашены в чёрный цвет; остальные узлы называются внутренними узлами;
  • (3)  свойство красного узла: если узел является красным, то оба его потомка являются чёрными (другими словами, каждый красный узел должен иметь чёрного предка);
  • (4)  свойство чёрного узла: на всех ветвях дерева, ведущих от его корня к листьям, количество чёрных узлов одинаково.

    Пункты (3) и (4) определения проверяют, что дерево остаётся в определённом смысле сбалансированным.

    Более того, операции включения и удаления в красно-чёрном дереве, использующие правила (3) и (4), гораздо более эффективны, чем аналогичные, использующие полную балансировку (например, как в АВЛ-деревьях).


    Примеры красно-чёрных деревьев.

    Внешние узлы будем изображать маленькими чёрными квадратами.

    1. Пустое красно-чёрное дерево - это бинарное дерево, состоящее всего из одного внешнего чёрного узла:

      

    2. Красно-чёрное дерево с единственным корневым узлом (красным или чёрным):


Рис.1. Красно-чёрное дерево с единственным корневым узлом

    Итак, красно-чёрное дерево с единственным узлом содержит также два NIL-листа, являющиеся двумя нулевыми связями, исходящими из единственного "реального" внутреннего узла.

    3. Красно-чёрное дерево, содержащее два узла, корневой и дочерний (левый или правый), и, соответственно, три листа; оно представимо единственным образом, удовлетворяя определению понятия "красно-чёрное дерево": корневой узел окрашен в чёрный цвет, дочерний узел - в красный цвет, а NIL-листья - в чёрный:


Рис.2. Красно-чёрное дерево, содержащее два узла


   Замечание. Существуют бинарные деревья, вершины которых не могут быть окрашены в красный и чёрный цвета по правилам для красно-чёрных деревьев. Из свойства чёрных узлов следует, что пути, ведущие из произвольной вершины x красно-чёрного дерева к листьям, содержат одно и то же количество чёрных вершин, которая называется чёрной высотой вершины x.


    Пример дерева, не являющегося красно-чёрным деревом).

    Если узел с произвольным цветом (красным или чёрным) пометим меткой "?", то следующее дерево не является красно-чёрным деревом:


Рис.3. Дерево, не являющееся красно-чёрным

Определение.
  • (1) Чёрной высотой вершины x называется количество чёрных вершин в любом пути, ведущем от вершины x к листьям (при этом цвет вершины x не учитывается).
  • (2) Чёрной высотой дерева называется чёрная высота корня.


    Пример.


Рис.4. Чёрная высота дерева


   Замечание. Самый длинный путь в красно-чёрном дереве от корня к листу не более чем вдвое длиннее любого другого его пути от корня к листу.


    Пример. Рассмотрим красно-чёрное дерево с чёрной высотой hblack(Root)=2.


Рис.5. Дерево с чёрной высотой hblack(Root)=2

    Кратчайший путь от корня до листа равен 2.

    Максимальный путь от корня до листа красно-чёрного дерева с чёрной высотой 2 равен 4 и составляет этот путь последовательность чередования красных и чёрных узлов. Добавление чёрного узла к ветви дерева, представляющей собой длиннейший путь от корня до листа, невозможно, поскольку при этом нарушится свойство чёрного узла.

    Добавление красного узла к этой же ветви также недопустимо, т.к. у красных узлов должны быть чёрные потомки.

    Таким образом, в данной ситуации самый длинный путь от корня до листа красно-чёрного дерева вдвое длиннее пути, проходящего только через чёрные узлы.

Лемма [2, с.255].
Красно-чёрное дерево с n внутренними вершинами (отличными от NIL-листьев) имеет высоту не большую
   2log2(n+1).

(1)Бакнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi. - СПб.: ООО "ДиаСофтЮП", 2003. - 560 с.
(2)Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО, 1999. - 960 с.

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




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