Реализация структур данных типа дерево и типовые алгоритмы их обработки

Постановка задачи

Реализовать процедуры создания красно-черных деревьев (динамическое представление), поиска, удаления и добавления узлов. Реализовать малое левое вращение для решения задач балансировки.

Теоретические положения

Красно-чёрное дерево — самобалансирующееся двоичное дерево поиска, имеющее сложность О (log n), которое быстро выполняет основные операции: добавление, удаление и поиск узла. Узлы дерева имеют атрибут «цвет», что помогает сбалансировать дерево. Атрибут может принимать значения «черный» или «красный». Дерево обладает свойствами: корень и листья дерева — обязательно черные и оба потомка красного узла — черные.

Балансировка дерева — операция изменения связи предок-потомок в случае разницы высот правого и левого поддеревьев больше 1. Результат достигается путем вращения поддерева данной вершины.

Описание сферы практического применения используемого типа данных — дерева.

Красно-черное дерево — особый вид двоичного дерева, который используется для организации данных, например, чисел или текста. В таком дереве быстро выполняется поиск. Листья красно-черного дерева не имеют данных. Эти деревья — самобалансирующиеся.

Описание алгоритмов обработки дерева.

Вставка: Узел окрашивается в красный цвет, и если мы вставляем узел в лист, то добавляем в этот лист красный узел с двумя черными потомками. Затем выполнить балансировку.

Удаление:

• · Если у вершины нет потомков, то изменяем указатель на неё у родителя на null.
• · Если у неё только один потомок, то делаем у родителя ссылку на него вместо этой вершины.
• · Если же имеются оба потомка, то находим вершину со следующим значением ключа. У такой вершины нет левого потомка. Удаляем уже эту вершину описанным во втором пункте способом, скопировав её ключ в изначальную вершину.
• · Сбалансировать дерево.

Результаты работы программы

Представлен пример выполнения программы.

Рис. 6. Результат работы 4-ой части программы