7. Поиск, использующий бинарное дерево

Бинарные деревья находят широкое применение для хранения таблицы с тем, чтобы сделать сортировку этой таблицы более эффективной. В этом методе все левосторонние потомки некоторой вершины с ключом Кey имеют ключи, которые меньше ключа Кey, а все правосторонние потомки имеют ключи, которые больше или равны ключу Кey. Смешанный обход такого бинарного дерева дает последовательность, упорядоченную по возрастающему значению ключа. Такое дерево может также быть использовано для бинарного поиска, поэтому оно называется деревом бинарного поиска (binary search tree).

Допустим, имеется следующая последовательность ключей:

30, 47, 85, 95, 115, 130, 138, 159, 166, 184, 206, 212, 219, 224, 237, 258, 296, 307, 314

Дерево бинарного поиска, соответствующего этой последовательности, показано на рисунке 10.3.

Алгоритм поиска в дереве бинарного поиска использует упорядоченность дерева. Поиск элемента выполняется следующим образом. Поиск начинается с корневой вершины, и эта вершина становится текущей. Затем аргумент поиска сравнивается с ключом текущей вершины. Если они равны, то требуемый элемент найден. В противном случае, если аргумент поиска меньше ключа текущей вершины, то выполняется переход к левой дочерней вершине, которая становится текущей. Если аргумент поиска больше ключа текущей вершины, то необходимо перейти к правому сыну текущей вершины, который станет текущей вершиной. В любом случае после перехода к новой вершине происходит этап сравнения ключа с аргументом поиска. Со временем либо определяется нужная вершина, либо достигается лист дерева, что свидетельствует об отсутствии искомого элемента в дереве.

Рисунок 10.3  Бинарное дерево поиска

Бинарный поиск, рассмотренный ранее, фактически использует отсортированный массив как некоторое неявное дерево бинарного поиска. Срединный элемент этого массива можно представить как корень такого дерева, нижнюю половину массива (все те элементы, которые меньше, чем срединный элемент) можно рассматривать как левое поддерево, а верхнюю половину (все те элементы, которые больше, чем срединный элемент)  как правое поддерево.

Упорядоченный массив может быть получен из дерева бинарного поиска при помощи смешанного обхода этого дерева и вставки каждого элемента последовательно в некоторый массив по мере того, как он встречается в дереве. С другой стороны, для некоторого заданного отсортированного массива имеется много соответствующих ему деревьев бинарного поиска. Предпочтительными являются сбалансированные бинарные деревья, рассмотренные в п. 9.4.2, для которых среднее время, затрачиваемое на поиск, пропорционально log₂N.

11. Сортировка

    1. Общие сведения и некоторые определения

Термин «сортировка» (sorting) определяется как «распределение, отбор по сортам или деление на категории, сорта, разряды». В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки – облегчить последующий поиск элементов в таком упорядоченном (отсортированном) множестве. Это почти универсальная, фундаментальная деятельность. Мы встречаемся с отсортированными объектами в телефонных справочниках, в библиотеках, в словарях, на складах – почти везде, где нужно искать хранимые объекты. Даже малышей учат держать свои вещи «в порядке», и они уже сталкиваются с некоторыми видами сортировок задолго до того, как познакомятся с азами арифметики. С точки зрения обработки данных сортировка (упорядочение) таблиц позволяет существенно ускорить процесс поиска данных, о чем свидетельствует материал раздела 10.

Таким образом, разговор о сортировке вполне уместен и важен, если речь идет об обработке данных. Сортировка – это идеальный «объект» для демонстрации огромного разнообразия алгоритмов, которые изобретены для решения одной и той же задачи. Поэтому это еще и идеальный «объект», демонстрирующий необходимость анализа производительности алгоритмов. К тому же на примерах сортировок можно показать как путем усложнения алгоритма, хотя под рукой и есть уже очевидные методы, можно добиться значительного выигрыша в эффективности.

Выбор алгоритма зависит от структуры обрабатываемых данных – это почти закон, но в случае сортировки такая зависимость столь глубока, что соответствующие методы были разбиты на два класса – сортировку массивов и сортировку последовательностей. Часто их называют внутренней и внешней сортировкой, поскольку массивы хранятся в быстрой оперативной, внутренней памяти ЭВМ, допускающей произвольный (прямой) доступ к элементам, а последовательности (файлы) размещаются в более медленной, но более емкой внешней памяти на устройствах, основанных на механических перемещениях (дисках, лентах). Строго говоря, при внутренней сортировке все данные хранятся в оперативной памяти, а при внешней сортировке не все записи там помещаются. При внутренней сортировке имеются более гибкие возможности для построения структур данных и доступа к ним; внешняя же сортировка показывает, как поступать в условиях сильно ограниченного доступа.

Введем некоторые понятия и обозначения. Если у нас есть элементы

a[0], a[1], a[2], …, a[HighIndex],

то сортировка есть перестановка этих элементов в последовательность

a[k₀], a[k₁], …, a[k_HighIndex] = a[0], a[1], …, a[HighIndex],

такую, что при некоторой упорядочивающей функции f выполняются отношения

f(a[0])  f(a[1])  …  f(a[HighIndex]).

где символом «  » обозначено отношение «предшествования», задающее некоторое правило упорядочения.

Обычно упорядочивающая функция не вычисляется по какому-либо правилу, а хранится как явная компонента, ассоциированная с каждым элементом сортируемой таблицы. Эта компонента является полем ключа или, просто, ключом элемента данных. Как и ранее, в разделе 11, ограничимся описанием элемента таблицы и самой таблицы a в форме (10.1) и (10.2).

Если в результате сортировки элементы таблицы располагаются в соответствии с соотношением (10.3) или (10.4), то говорят, что таблица упорядочена по возрастанию (значений ключа Кey). Если после сортировки элементы располагаются так, что значения ключа уменьшаются при увеличении индекса, то выполнено упорядочение по убыванию. В дальнейшем везде будем считать, что сортировки производят упорядочение элементов по возрастанию ключа.

Метод сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов с равными ключами не изменяется. Устойчивость сортировки часто бывает желательной, если речь идет об элементах, уже упорядоченных (отсортированных) по некоторым вторичным ключам, не влияющим на первичный (основной) ключ.