На этом шаге мы приведем еще ряд общих сведений о таких деревьях.
Построение красно-чёрного дерева осуществляется посредством операции включения узла в бинарное дерево поиска с проверкой свойств (1)-(4) предыдущего шага красно-чёрных деревьев.
В пустое красно-чёрное дерево можно осуществить включение как красного, так и чёрного узла. Но, последующий процесс включения вершин усложняется в силу следующих обстоятельств.
Красный узел, изначально имея два чёрных листа, по свойству красного узла должен иметь двух чёрных потомков, что усложняет процесс добавления второй вершины в бинарное дерево: красной - из-за нарушения свойства красного узла, чёрной - из-за нарушения чёрной высоты дерева.
Чёрный узел, изначально имея два чёрных листа, не допускает включения в бинарное дерево из-за нарушения чёрной высоты дерева.
Единственно простое включение вершины в бинарное дерево, содержащее один узел, возможно при наличии чёрного корня дерева и включаемой красной вершины.
Поэтому классические алгоритмы включения и удаления узлов предполагают работу с красно-чёрными деревьями, имеющими чёрный корень.
Для соблюдения баланса бинарного дерева, который "контролируется" его чёрной высотой, расположение и цвет включаемой вершины будет зависеть от цвета вершин поддерева (к которому она присоединяется) с корнем, расположенным на два уровня выше неё.
Соглашения об обозначении узлов красно-чёрного дерева.
1. Узлы дерева, не являющиеся листьями, будем отмечать прописными латинскими буквами с указанием в скобках их цвета.
2. Внешние узлы (листья) дерева будем отмечать буквой d с указанием в скобках чёрного цвета (для наглядности).
3. Добавляемый узел будем обозначать буквой S (от англ. son - сын), тогда важную часть его окрестности узлов будут составлять следующие узлы:
отец - D (от англ. dad - отец);
дядя - U (от англ. uncle - дядя);
дедушка - G (от англ. granddad - дедушка);
брат - B (от англ. brother - брат);
племянник (левый) - Nl (от англ. nephew - племянник,
left - левый);
племянник (правый) - Nr (от англ. nephew - племянник,
right - правый);
ребёнок - C (от англ. child - ребёнок).
Изобразим окрестность добавляемого узла:
Рис.1. Окрестность добавляемого узла
4. Узлы, являющиеся несущественными, будем нумеровать натуральными числами слева направо по уровням, начиная с первого.
Замечание (методическое). С красно-чёрным деревом обычно работают с помощью карандаша и бумаги; вначале нарисуйте дерево, затем вставляйте или удаляйте узлы. После выполнения этих операций при необходимости проведите балансировку.
На следующем шаге мы рассмотрим алгоритм включения узла в красно-чёрное дерево.
