Таблицы символов и деревья бинарного поиска

Получение конкретного фрагмента или фрагментов информации из больших томов ранее сохраненных данных - основополагающая операция, называемая поиском, характерная для многих вычислительных задач. Как и в случае с алгоритмами сортировки, описанными в главах с 6 по 11, и очередями конкретного приоритета, описанными в главе 9, мы работаем с данными, разделенными на записи, или элементы, каждый из которых имеет ключ, используемый при поиске. Цель поиска - отыскание элементов с ключами, которые соответствуют заданному ключу поиска. Обычно, назначением поиска является получение доступа к информации внутри элемента (а не просто к ключу) с целью ее обработки.

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

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

Определение 12.1 Таблица символов - это структура данных элементов с ключами, которая поддерживает две базовых операции: вставку нового элемента и возврат элемента с заданным ключом.

Иногда таблицы символов называют также словарями (dictionary), по аналогии с проверенной временем системой предоставления определений слов путем перечисления их в справочнике в алфавитном порядке. Так, в словаре английского (или любого другого) языка ключи - это слова, а элементы - связанные со словами записи, которые содержат определение, правила произношения и другую информацию. Алгоритмы поиска, используемые для отыскания информации в словаре, обычно основываются на алфавитном расположении записей. Телефонные книги, энциклопедии и другие справочники, в основном, организованы таким же образом, и некоторые из рассматриваемых методов поиска (например, алгоритм бинарного поиска в разделах 2.6 и 12.4), также основываются на том, что записи упорядочены.

Таблицы символов в компьютерах обладают преимушеством в том, что они значительно более динамичны, чем словарь или телефонная книга. Поэтому большинство рассматриваемых методов создают структуры данных, которые не только позволяют использовать эффективные алгоритмы поиска, но и поддерживают эффективные реализации операций добавления новых элементов, удаления или изменения элементов, объединения двух таблиц символов в одну и т.п. В этой главе будут вновь рассматриваться многие из вопросов, связанных с операциями, которые исследовались применительно к очередям по приоритетам в главе 9. Разработка динамических структур данных для поддержки поиска - одна из старейших и наиболее широко изученных проблем в компьютерных науках; она будет находиться в центре нашего внимания как в этой главе, так и в главах 13-16. Как будет показано, для решения задачи реализации таблиц символов разработаны (и продолжают разрабатываться) множество оригинальных алгоритмов.

Теоретики компьютерных наук и программисты интенсивно исследуют и другие применения таблиц символов, кроме упомянутых основных, поскольку эти таблицы - незаменимое вспомогательное средство при организации профаммного обеспечения в компьютерных системах. Таблица символов служит словарем для программы: Ю1ючи - это символические имена, используемые в программе, а элементы содержат информацию, описываюшую именованные объекты. Начиная с зари развития компьютерной техники, когда таблицы символов позволяли программистам переходить от использования числовых адресов в машинных кодах к символическим именам языка ассемблера, и завершая современными приложениями нового тысячелетия, когда символические имена имеют определенное значение в рамках всемирных компьютерных сетей, быстрые алгоритмы поиска играли и будут ифать важную роль при компьютерной обработке.

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

Как и при изучении методов сортировки в главе 6, в этой главе изучение методов поиска начинается с рассмотрения ряда элементарных методов, пригодных для небольших таблиц и в некоторых особых ситуациях, и которые иллюстрируют базовые технологии, используемые более совершенными методами. Затем, в остальной части главы основное внимание уделяется дереву бинарного поиска (binary search tree - BST), основополагающей и широко используемой структуре данных, допускающей применение алгоритмов быстрого поиска.

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

12.1 Абстрактный тип данных таблицы символов

Как и при рассмотрении очередей приоритета, алгоритмы поиска можно рассматривать как принадлежащие к интерфейсам, объявляющим множество общих операций, которые могут быть отделены от конкретных реализаций, что позволяет легко и просто заменять одни реализации другими. Интерес представляют следующие операции:

Вставка нового элемента.

Поиск элемента (или элементов) с заданным ключом.

Удаление указанного элемента.

Выбор к-то по величине элемента в таблице символов.

Сортировка таблицы символов (отображение всех элементов в порядке их ключей).

Объединение двух таблиц символов.

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

В общем случае термин алгоритм поиска используется в значении реализация абстрактного типа данных таблицы символов , хотя, строго говоря, последний термин предполагает определение и построение основополагающей структуры данных таблицы символов и, в дополнение к поиску, реализацию операций абстрактного типа данных. В связи с важностью таблиц символов для столь многих компьютерных приложений они доступны в качестве высокоуровневой абстракций во многих средах программирования. Стандартная библиотека С содержит bsearch, т.е. реализацию алгоритма бинарного поиска, описанного в разделе 12.4, а библиотека стандартных шаблонов С++ предоставляет большое множество таблиц символов, называемых ассоциатив-