- •Структуры и алгоритмы обработки данных
- •Логическая и физическая структуры данных
- •Классификация структур данных
- •Основные операции над структурами данных
- •Алгоритм и примеры задач, решаемых с помощью алгоритмов
- •Адресация и распределение памяти
- •Адресные пространства и модели оперативной памяти
- •Формирование физического адреса в реальном режиме
- •Особенности адресации в защищенном режиме
- •Кэширование
- •Анализ алгоритмов
- •Быстродействие – основной показатель эффективности алгоритма
- •Подсчет числа простейших операций
- •Лучший, средний и худший случаи
- •Алгоритмы и платформы
- •Виртуализация памяти
- •Использование кэша
- •Выравнивание данных
- •Рандомизированные алгоритмы
- •Общая характеристика записей и способы описания в Delphi
- •Многоуровневые записи
- •Выравнивание и упакованные записи
- •Записи с вариантной частью
- •Массивы
- •Общая характеристика массивов
- •Статические (стандартные) массивы
- •Многомерные статические массивы
- •Свойства статических массивов
- •Открытые массивы
- •Динамические массивы
- •Динамические векторы
- •Многомерные динамические массивы
- •Массивы типа Variant
- •Вставка и удаление в массиве
- •Связные списки и алгоритмы их обработки
- •Списки и их разновидности
- •Односвязный список
- •Общая характеристика односвязного списка
- •Структура элемента односвязного списка
- •Формирование односвязного списка
- •Просмотр односвязного списка
- •Вставка элемента в односвязный список
- •Удаление элемента из односвязного списка
- •Линейный двухсвязный список
- •Структура элемента двухсвязного списка
- •Реализация операций в линейном двухсвязном списке
- •Нелинейный двухсвязный список
- •Нелинейный трехсвязный список
- •Определение плекса и его общие признаки
- •Иерархическая списковая структура. Сетевая структура
- •Достоинства и недостатки связных списков
- •Функциональные и свободные списки
- •Общая характеристика функционального и свободного списка
- •Методы формирования свободного списка
- •Стеки, очереди, деки и операции в них
- •Общая характеристика
- •Очередь
- •Динамические множества и словари
- •Общая характеристика
- •Операции в динамических множествах
- •Деревья
- •Общая характеристика и некоторые определения
- •Представление дерева в памяти
- •Естественное представление дерева
- •Представление дерева с помощью вектора
- •Представление дерева с использованием списков сыновей
- •Методы обхода деревьев
- •Бинарное дерево
- •Структура бинарного дерева
- •Формирование бинарного дерева
- •Обход бинарного дерева
- •Преобразование любого дерева к бинарному дереву
- •Включение и исключение в дереве
- •Включение в дереве
- •Исключение в дереве
- •Поиск: определение и общая терминология
- •Линейный (последовательный) поиск
- •Последовательный поиск в упорядоченной таблице
- •Последовательный поиск при накоплении запросов
- •Индексно-последовательный поиск
- •Бинарный поиск
- •Поиск, использующий бинарное дерево
- •Сортировка
- •Общие сведения и некоторые определения
- •Внутренняя сортировка
- •Сортировка прямыми включениями
- •Сортировка бинарными включениями
- •Сортировка прямым выбором
- •Сортировка прямым обменом
- •Сортировка методом Шелла
- •Сортировка с помощью бинарного дерева
- •Пирамидальная сортировка
- •Быстрая сортировка разделением
- •Внешняя сортировка
- •Сортировка прямым слиянием
- •Сортировка естественным слиянием
- •Сортировка многопутевым слиянием
- •Многофазная сортировка
- •Хеширование и хеш-таблицы
- •Общие сведения и определения
- •Коллизии при хешировании
- •Разрешение коллизий при хешировании
- •Разрешение коллизий методом открытой адресации
- •Разрешение коллизий методом цепочек
- •Функции хеширования
- •Поисковые деревья
- •Бинарное дерево поиска
- •Структура бинарного дерева поиска и алгоритм поиска
- •Вставка элемента в бинарное дерево поиска
- •Удаление из бинарного дерева поиска
- •Красно-черные деревья
- •Определение красно-черного дерева, структура его элементов
- •Повороты
Бинарное дерево
Структура бинарного дерева
Упорядоченные деревья второй степени (m-арные деревья при m=2) называют двоичными или бинарными деревьями. Упорядоченное бинарное дерево можно определить как множество вершин, которое либо пусто, либо состоит из корня с двумя отдельными двоичными деревьями, которые называют левым и правым поддеревьями этого корня. Деревья степени больше двух называют сильно ветвящимися деревьями (multiway trees).
При представлении бинарного дерева в виде связного списка каждый элемент может содержать поля данных и два структурных указателя: указатель (Left) левого сына и указатель (Right) правого сына. Такое представление называется естественным представлением бинарного дерева.
Тип бинарного дерева (базовый тип дерева) может быть объявлен следующим образом:
Type
Pvertex = ^Tvertex;
Tvertex = Record
Dat: <поля данных>;
Left, Right: Pvertex;
End;
Var CurrentVertex, Root: Pvertex;
CountVertex: Integer;
где Dat, как и ранее, совокупность информационных полей; Left и Right поля структурных указателей. Поля данных мы будем использовать для размещения меток вершин. Переменные-указатели CurrentVertex и Root и необходимы для идентификации соответственно некоторой текущей вершины и корня. CountVertex количество вершин в дереве.
На рисунке 9.8 изображена структура естественного представления бинарного дерева (пустые поля указателей содержат пустые ссылки).
Рисунок 9.8 Естественное представление бинарного дерева
Формирование бинарного дерева
Предположим, что нужно построить такое бинарное дерево, которое при заданном количестве вершин N имела бы минимальную высоту. Очевидно, минимальная высота дерева достигается, если на всех уровнях, кроме последнего, поместить максимально возможное число вершин. Этого можно добиться, размещая «приходящие» в дерево вершины поровну слева и справа от той вершины, которая будет для них родителем. В результате при каждом увеличении количества вершин мы будем получать деревья, показанные на рисунке 9.9.
Рисунок 9.9 Сбалансированные бинарные деревья для различных N
Дерево, имеющее структуру, показанную на рисунке 9.9, называется сбалансированным деревом (balanced tree, AVL-tree). В таком дереве число потомков в левом и правом поддереве любой вершины отличается не более, чем на 1.
Алгоритм формирования сбалансированного бинарного дерева допускает следующую рекурсивную формулировку:
взять одну вершину в качестве корня;
построить тем же способом левое поддерево с Nleft = N Div 2 вершинами;
построить тем же способом правое поддерево с Nright = N Nleft 1 вершинами.
Вышеприведенному алгоритму соответствует рекурсивная функция BinaryTreeCreate, приведенная ниже:
Function BinaryTreeCreate(N: Integer): Pvertex;
Var Nleft, Nright: Integer;
Begin
If N = 0 Then Tree:= Nil
Else Begin
Nleft:= N Div 2;
Nright:= N - Nleft - 1;
New(CurrentVertex);
BinaryTreeCreate:= CurrentVertex;
With CurrentVertex^ Do Begin
<занесение данных в поля Dat>
Left:= BinaryTreeCreate(Nleft);
Right:= BinaryTreeCreate(Nright);
End;
End;
End;
Для использования функции BinaryTreeCreate нужно передать ей значение числа вершин и выполнить вызов в следующей форме:
Root:= BinaryTreeCreate(CountVertex);