Лабораторная работа 31. Динамические структуры данных: бинарные деревья

Цель работы: изучить понятие, формирование, особенности доступа к данным и работы с памятью в бинарных деревьях, научиться решать задачи с использованием рекурсивных функций и алгоритмов обхода бинарных деревьев в языке C++.

При выполнении лабораторной работы для каждого задания требуется написать программу на языке С++, в которой выполнено формирование бинарных деревьев в соответствии с постановкой задачи, ввод данных элементов деревьев с учетом типа информационного поля, их обработка и вывод на экран в указанном формате. Для хранения данных бинарных деревьев следует использовать ресурсы динамической памяти. Ввод данных осуществляется с клавиатуры с учетом требований к входным данным, содержащихся в постановке задачи. Ограничениями на входные данные являются максимальный размер строковых данных, диапазоны числовых типов полей структуры и допустимый размер области динамической памяти в языке С++.

Теоретические сведения.

Ознакомьтесь с материалом лекции.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

1. Найдите количество четных элементов бинарного дерева. Укажите эти элементы и их уровни.
2. Найдите сумму элементов сбалансированного дерева, находящихся на уровне k.
3. Реализовать прямой обход бинарного дерева. Вывести на печать результат обхода.
4. Реализовать обратный обход бинарного дерева. Вывести на печать результат обхода.
5. Добавить 2 элемента к бинарному дереву. Изобразить начальную и конечную организацию бинарного дерева.
6. Удалить 3 элемента из бинарного дерева. Изобразить начальную и конечную организацию бинарного дерева.

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

• Титульный лист.
• Словесная постановка задачи. В этом подразделе проводится полное описание задачи. Описывается суть задачи, анализ входящих в нее физических величин, область их допустимых значений, единицы их измерения, возможные ограничения, анализ условий при которых задача имеет решение (не имеет решения), анализ ожидаемых результатов.
• Математическая модель. В этом подразделе вводятся математические описания физических величин и математическое описание их взаимодействий. Цель подраздела – представить решаемую задачу в математической формулировке.
• Алгоритм решения задачи. В подразделе описывается разработка структуры алгоритма, обосновывается абстракция данных, задача разбивается на подзадачи. Схема алгоритма выполняется по ЕСПД (ГОСТ 19.003-80 и ГОСТ 19.002-80).
• Листинг программы. Подраздел должен содержать текст программы на языке программирования С++, реализованный в среде MS Visual Studio 2010.
• Выводы по лабораторной работе.
• Ответы на контрольные вопросы.

Контрольные вопросы

1. С чем связана популярность использования деревьев в программировании?
2. Можно ли список отнести к деревьям? Ответ обоснуйте.
3. Какие данные содержат адресные поля элемента бинарного дерева?
4. Может ли бинарное дерево быть строгим и неполным? Ответ обоснуйте.
5. Может ли бинарное дерево быть нестрогим и полным? Ответ обоснуйте.
6. Каким может быть почти сбалансированное бинарное дерево: полным, неполным, строгим, нестрогим? Ответ обоснуйте.
7. Куда может быть добавлен элемент в бинарное дерево в зависимости от его вида (полное, неполное, строгое, нестрогое)? Вид дерева при этом должен сохраниться.
8. Куда может быть добавлен элемент в сбалансированное бинарное дерево? Вид дерева при этом должен сохраниться.
9. Чем отличаются, с точки зрения реализации алгоритма, прямой, симметричный и обратный обходы бинарного дерева?

Красно-черные деревья

Бинарные деревья работают лучше всего, когда они сбалансированы, когда длина пути от корня до любого из листьев находится в определенных пределах, связанных с числом вершин. Красно-черные деревья являются одним из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета вершин используются при балансировке дерева.

Красно-черное дерево (Red-Black-Tree, RB-Tree) – это бинарное дерево со следующими свойствами (рис. 32.4):

• каждая вершина должна быть окрашена либо в черный, либо в красный цвет;
• корень дерева должен быть черным;
• листья дерева должны быть черными и объявляться как NIL-вершины (NIL-узлы, то есть "виртуальные" узлы, наследники узлов, которые обычно называют листьями; на них "указывают" NULL указатели);
• каждый красный узел должен иметь черного предка;
• на всех ветвях дерева, ведущих от его корня к листьям, число черных вершин одинаково.

Рис. 32.4. Красно-черное дерево

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

Над красно-черными деревьями можно выполнять все те же основные операции, что и над бинарными деревьями.

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

//создание красно-черного дереваvoid Make_RBTree(RBTree** Node, int n){ int Data; while (n > 0) { cout << "Введите значение "; cin >> Data; Insert_Node(Node, Data); n--; }} //добавление узла в красно-черное деревоvoid Insert_Node(RBTree** Node,int Data) { RBTree **Curent, *Parent, *New_Node; Curent = Node; Parent = NIL; // Поиск местоположения while (*Curent!= NIL) { Parent = (*Curent); Curent = Data < (*Curent)->Data? &((*Curent)->Left): &((*Curent)->Right); } // Создание нового узла New_Node = new RBTree(); New_Node->Data = Data; New_Node->Parent = Parent; New_Node->Left = NIL; New_Node->Right = NIL; New_Node->color = RED; // Вставка элемента в дерево if(Parent!= NIL){ if (Data < Parent->Data) Parent->Left = New_Node; else Parent->Right = New_Node; } else (*Curent) = New_Node; Insert_Fixup(Node, New_Node);} // Поддержка баланса дерева после вставки нового элементаvoid Insert_Fixup(RBTree** Node,RBTree* New_Node){ RBTree* Current = New_Node; // Проверка свойств дерева while (Current!= *(Node) && Current->Parent->color == RED){ // если есть нарушение if (Current->Parent == Current->Parent->Parent->Left) { RBTree *ptr = Current->Parent->Parent->Right; if (ptr->color == RED) { Current->Parent->color = BLACK; ptr->color = BLACK; Current->Parent->Parent->color = RED; Current = Current->Parent->Parent; } else { if (Current == Current->Parent->Right) { // сделать Current левым потомком Current = Current->Parent; Rotate_Left(Node,Current); } // перекрасить и повернуть Current->Parent->color = BLACK; Current->Parent->Parent->color = RED; Rotate_Right(Node,Current->Parent->Parent); } } else { RBTree *ptr = Current->Parent->Parent->Left; if (ptr->color == RED) { Current->Parent->color = BLACK; ptr->color = BLACK; Current->Parent->Parent->color = RED; Current = Current->Parent->Parent; } else { if (Current == Current->Parent->Left) { Current = Current->Parent; Rotate_Right(Node,Current); } Current->Parent->color = BLACK; Current->Parent->Parent->color = RED; Rotate_Left(Node,Current->Parent->Parent); } } } (*Node)->color = BLACK;} //поворот узла Current влевоvoid Rotate_Left(RBTree** Node,RBTree *Current) { RBTree *ptr = Current->Right; Current->Right = ptr->Left; if (ptr->Left!= NIL) ptr->Left->Parent = Current; if (ptr!= NIL) ptr->Parent = Current->Parent; if (Current->Parent!= NIL) { if (Current == Current->Parent->Left) Current->Parent->Left = ptr; else Current->Parent->Right = ptr; } else { (*Node) = ptr; } ptr->Left = Current; if (Current!= NIL) Current->Parent = ptr;} //поворот узла Current вправоvoid Rotate_Right(RBTree** Node,RBTree *Current) { RBTree *ptr = Current->Left; Current->Left = ptr->Right; if (ptr->Right!= NIL) ptr->Right->Parent = Current; if (ptr!= NIL) ptr->Parent = Current->Parent; if (Current->Parent!= NIL) { if (Current == Current->Parent->Right) Current->Parent->Right = ptr; else Current->Parent->Left = ptr; } else { (*Node) = ptr; } ptr->Right = Current; if (Current!= NIL) Current->Parent = ptr;} //печать красно-черного дереваvoid Print_RBTree(RBTree* Node, int l){ int i; if (Node!= NIL) { Print_RBTree(Node->Right, l+1); for (i=0; i< l; i++) cout << " "; if (Node->color == RED) SetConsoleTextAttribute(hStd,FOREGROUND_RED); cprintf ("%4ld", Node->Data); SetConsoleTextAttribute(hStd,atr); Print_RBTree(Node->Left, l+1); } else cout << endl;} //прямой обход красно-черного дереваvoid PreOrder_RBTree(RBTree* Node){ if (Node!= NIL) { printf ("%3ld",Node->Data); PreOrder_RBTree(Node->Left); PreOrder_RBTree(Node->Right); }} //обратный обход красно-черного дереваvoid PostOrder_RBTree(RBTree* Node){ if (Node!= NIL) { PostOrder_RBTree(Node->Left); PostOrder_RBTree(Node->Right); printf ("%3ld",Node->Data); }} //симметричный обход красно-черного дереваvoid SymmetricOrder_RBTree(RBTree* Node){ if (Node!= NIL) { PostOrder_RBTree(Node->Left); printf ("%3ld",Node->Data); PostOrder_RBTree(Node->Right); }} //проверка пустоты красно-черного дереваbool Empty_RBTree(RBTree* Node){ return (Node == NIL? true: false);} //освобождение памяти, выделенной под красно-черное деревоvoid Delete_RBTree(RBTree* Node){ if (Node!= NIL) { Delete_RBTree(Node->Left); Delete_RBTree(Node->Right); delete(Node); }}