Двоичные (бинарные) деревья
Текст лекции.
Лекция 40 Алгоритмы поиска на основе деревьев.
Краткая аннотация лекции.
В лекции рассматриваются определение и виды деревьев поиска, приемы снижения трудоемкости поиска в древовидных структурах, приводятся описания алгоритмов поиска в двоичных упорядоченных, случайных и сбалансированных в высоту (АВЛ) деревьях, приводятся примеры программной реализации бинарного дерева поиска и АВЛ-дерева.
Цель лекции: изучить алгоритмы поиска на основе деревьев, научиться решать задачи поиска через построение упорядоченного, случайного, оптимального или сбалансированного в высоту деревьев на языке C++.
Поиск данных, являясь одним из приоритетных направлений работы с данными, предполагает использование соответствующих алгоритмов в зависимости от ряда факторов: способ представления данных, упорядоченность множества поиска, объем данных, расположение их во внешней или во внутренней памяти. Поиск – процесс нахождения конкретной информации в ранее созданном множестве данных. Как правило, данные представляют собой структуры, каждая из которых имеет хотя бы один ключ – значение определенного поля конкретной структуры. Ключ поиска – это поле, по значению которого происходит поиск.
Рассмотрим организацию поиска данных, имеющих древовидную структуру. Анализируя дерево только с точки зрения представления данных в виде иерархической структуры, заметим, что выигрыша при организации поиска не получится. Сравнение ключа поиска с эталоном необходимо провести для всех элементов дерева.
Уменьшить число сравнений ключей с эталоном возможно, если выполнить организацию дерева особым образом, то есть расположить его элементы по определенным правилам. При этом в процессе поиска будет просмотрено не все дерево, а отдельное поддерево. Такой подход позволяет классифицировать деревья в зависимости от правил построения. Выделим некоторые популярные виды деревьев, на основе которых рассмотрим организацию поиска.
Двоичные деревья представляют собой иерархическую структуру, в которой каждый узел имеет не более двух потомков. То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). При этом каждое поддерево в свою очередь тоже является деревом. Поиск на таких структурах не дает выигрыша по выполнению по сравнению с линейными структурами того же размера, так как необходимо в худшем случае выполнить обход всего дерева. Поэтому интерес представляют двоичные упорядоченные деревья.