учебники, программирование, основы, введение в,

 

Ссылочные реализации структур данных. Списки и деревья. Реализации множества: с помощью бинарного поиска, на базе сбалансированных деревьев, хеширование

Ссылочные реализации структур данных
Большинство структур данных реализуется на базе массива. Все реализации можно разделить на два класса: непрерывные и ссылочные. В непрерывных реализациях элементы структуры данных располагаются последовательно друг за другом в непрерывном отрезке массива, причем порядок их расположения в массиве соответствует их порядку в реализуемой структуре. Рассмотренные выше реализации очереди и стека относятся к непрерывным.
В ссылочных реализациях элементы структуры данных хранятся в произвольном порядке. При этом вместе с каждым элементом хранятся ссылки на один или несколько соседних элементов. В качестве ссылок могут выступать либо индексы ячеек массива, либо адреса памяти. Можно представить себе шпионскую сеть, в которой каждый участник знает лишь координаты одного или двух своих коллег. Контрразведчикам, чтобы обезвредить сеть, нужно пройти последовательно по всей цепочке, начиная с выявленного шпиона.
Ссылочные реализации обладают двумя ярко выраженными недостатками: 1) для хранения ссылок требуется дополнительная память; 2) для доступа к некоторому элементу структуры необходимо сначала добраться до него, проходя последовательтно по цепочке других элементов. Казалось бы, зачем нужны такие реализации?
Все недостатки ссылочных реализаций компенсируются одним чрезвычайно важным достоинством: в них можно добавлять и удалять элементы в середине структуры данных, не перемещая остальные элементы.
Массовые операции
Массовые операции — это операции, затрагивающие значительную часть всех элементов структуры данных. Пусть нужно добавить или удалить один элемент. Если при этом приходится, например, переписывать значительную часть остальных элементов с одного места на другое, то говорят, что добавление или удаление приводит к массовым операциям. Массовые операции — это бедствие для программиста, то, чего он всегда стремится избежать. Хорошая реализация структуры данных — та, в которой массовых операций либо нет совсем, либо они происходят очень редко. Например, добавление элемента должно выполняться за ограниченное число шагов, независимо от того, содержит ли структура десять или десять тысяч элементов.
В непрерывных реализациях добавление или удаление элементов в середине структуры неизбежно приводит к массовым операциям. Поэтому структуры, в которых можно удалять или добавлять элементы в середине, обязательно должны быть реализованы ссылочным образом.
Пример неудачного использования непрерывных реализаций — файловые системы в некоторых старых операционных системах, например, в уже упомянутой ОС ЕС или в системе РАФОС, применявшейся на СМ ЭВМ, на старых советских персональных компьютерах Электроника и т.п. В современных файловых системах файлы фрагментированы, т.е. кусочки большого файла, непрерывного с точки зрения пользователя,на самом деле могут быть разбросаны по всему диску. Раньше это было не так, файлы должны были обязательно занимать непрерывный участок на диске. При постоянной работе файлы уничтожались и создавались заново на новом месте — и всякое редактирование текстового файла приводило к его обновлению. В результате свободное пространство на диске становилось фрагментированным, т.е. состоящим из множества небольших кусков. Возникала ситуация, когда большой файл невозможно записать на диск: хотя свободного места в сумме много, нет достаточно большого свободного фрагмента. Приходилось постоянно выполять длительную и опасную процедуру сжатия диска, которая часто приводила к потере всех данных на нем.
Список
Классический пример структуры данных последовательного доступа, в которой можно удалять и добавлять элементы в середине структуры, — это линейный список. Различают однонаправленный и двунаправленный списки (иногда говорят односвязный и двусвязный).
Элемены списка как бы выстроены в цепочку друг за другом. У списка есть начало и конец. Имеется также указатель списка, который располагается между элементами. Если мысленно вообразить, что соседние элементы списка связаны между собой веревкой, то указатель — это ленточка, которая вешается на веревку. В любой момент времени в списке доступны лишь два элемента — элементы до указателя и за указателем.
В однонаправленном списке указатель можно передвигать лишь в одном направлении — вперед, в направлении от начала к концу. Кроме того, можно установить указатель в начало списка, перед его первым элементом. В отличие от однонаправленного списка, двунаправленный абсолютно симметричен, указатель в нем можно передвигать вперед и назад, а также устанавливать как перед первым, так и за последним элементами списка.
В двунаправленном списке можно добавлять и удалять элементы до и за указателем. В однонаправленном списке добавлять элементы можно также с обеих сторон от указателя, но удалять элементы можно только за указателем.
Удобно считать, что перед первым элементом списка располагается специальный пустой элемент, который называется головой списка. Голова списка присутствует всегда, даже в пустом списке. Благодаря этому можно предполагать, что перед указателем всегда есть какой-то элемент, что упрощает процедуры добавления и удаления элементов.
В двунаправленном списке считают, что вслед за последним элементом списка вновь следует голова списка, т.е. список зациклен в кольцо.
Можно было бы точно так же зациклить и однонаправленной список. Но гораздо чаще считают, что за последним элементом однонаправленного списка ничего не следует. Однонаправленный список, таким образом, представляет собой цепочку, начинающуюся с головы списка, за которой следует первый элемент, затем второй и так далее вплоть до последнего элемента, а заканчивается цепочка ссылкой в никуда.
Ссылочная реализация списка
Мы рассмотрели абстрактное понятие списка. Но в программировании зачастую отождествляют понятие списка с его ссылочной реализацией на базе массива или непосредственно на базе оперативной памяти.
Основная идея реализации двунаправленного списка заключается в том, что вместе с каждым элементом хранятся ссылки на следующий и предыдущий элементы. В случае реализации на базе массива ссылки представляют собой индексы ячеек массива. Чаще, однако, элементы списка не располагают в каком-либо массиве, а просто размещают каждый по отдельности в оперативной памяти, выделенной данной задаче. (Обычно элементы списка размещаются в так называемой динамической памяти, или куче — это область оперативной памяти, в которой можно при необходимости захватывать куски нужного размера, а после использования освобождать, т.е. возвращать обратно в кучу.) В качестве ссылок в этом случае используют адреса элементов в оперативной памяти.
Голова списка хранит ссылки на первый и последний элементы списка. Поскольку список зациклен в кольцо, то следующим за головой списка будет его первый элемент, а предыдущим — последний элемент. Голова списка хранит только ссылки и не хранит никакого элемента. Это как бы пустой ящик, в который нельзя ничего положить и который используется только для того, чтобы написать на нем адреса следующего и предыдущего ящиков, т.е. первого и последнего элементов списка. Когда список пуст, голова списка зациклена сама на себя.
Указатель списка реализуется в виде ссылки на следующий и предыдущий элементы, он просто отмечает некоторое место в цепочке элементов.
В случае однонаправленного списка хранится только ссылка на следующий элемент, таким способом экономится память. Голова однонаправленного списка хранит ссылку на первый элемент списка. Последний элемент списка хранит нулевую ссылку, т.е. ссылку в никуда, т.к. в программах нулевой адрес никогда не используется.
Ценность ссылочной реализации списка состоит в том, что процедуры добавления и удаления элементов не приводят к массовым операциям. Рассмотрим, например, операцию удаления элемента за указателем. Читая ссылку на следующий элемент в удаляемом элементе, мы находим, какой элемент должен будет следовать за указателем после удаления текущего элемента. После этого достаточно связать элемент до указателя с новым элементом за указателем. А именно, обозначим через X адрес элемента до указателя, через Y — адрес нового элемента за указателем. В поле следующий для элемента с адресом X надо записать значение Y, в поле предыдущий для элемента с адресом Y — значение X. Таким образом, при удалении элемента за указателем он исключается из цепочки списка, для этого достаточно лишь поменять ссылки в двух соседних элементах. Аналогично, для добавления элемента достаточно включить его в цепочку, а для этого также нужно всего лишь модифицировать ссылки в двух соседних элементах. Добавляемый элемент может располагаться где угодно, следовательно, нет никаких проблем с захватом и освобождением памяти под элементы.
Деревья и графы
Граф — это фигура, которая состоит из вершин и ребер, соединяющих вершины. Например, схема линий метро — это граф. Ребра могут иметь направления, т.е. изображаться стрелочками; такие графы называются ориентированными. Допустим, надо построить схему автомобильного движения по улицам города. Почти во всех городах есть много улиц с односторонним движением. Поэтому такая транспортная схема должна представляться ориентированным графом. Улице с односторонним движением соответствует стрелка, с двусторонним — пара стрелок в противоположных направлениях. Вершины такого графа соответствуют перекресткам и тупикам.
Дерево — это связный граф без циклов. Кроме того, в дереве выделена одна вершина, которая называется корнем дерева. Остальные вершины упорядочиваются по длине пути от корня дерева.
Зафиксируем некоторую вершину X. Вершины, соединенные с X ребрами и расположенные дальше нее от корня дерева, называются детьми или сыновьями вершины X. Сыновья упорядочены слева направо. Вершины, у которых нет сыновей, называются терминальными. Дерево обычно изображают перевернутым, корнем вверх. .
Деревья в программировании используются значительно чаще, чем графы. Так, на построении дереьев основаны многие алгоритмы сортировки и поиска. Компиляторы в процессе перевода программы с языка высокого уровня на машинный язык представляют фрагменты программы в виде деревьев, которые называются синтаксическими. Деревья естественно применять всюду, где имеются какие-либо иерархические структуры, т.е. структуры, которые могут вкладываться друг в друга. Примером может служить оглавление книги
Пусть книга состоит из частей, части — из глав, главы — из параграфов. Сама книга представляется корнем дерева, из которого выходят ребра к вершинам, соответствующим частям книги. В свою очередь, из каждой вершины-части книги выходят ребра к вершинам-главам, входящим в эту часть, и так далее. Файловую систему компьютера также можно представить в виде дерева. Вершинам соответствуют каталоги (их также называют директориями или папками) и файлы. Из вершины-каталога выходят ребра к вершинам, соответствующим всем каталогам и файлам, которые содержатся в данном каталоге. Файлы представляются терминальными вершинами дерева. Корню дерева соответствует корневой каталог диска. Программы, осуществляющие работу с файлами, такие, как Norton Commander в системе MS DOS или Проводник Windows, могут изображать файловую систему графически в виде дерева.
Ссылочные реализации как будто специально придуманы для реализации деревьев. Вершина дерева представляется в виде объекта, содержащего ссылки на родительскую вершину и на всех сыновей, а также некоторую дополнительную информацию, зависящую от конкретной задачи. Объект, представляющий вершину дерева, занимает область фиксированного размера, которая обычно размещается в динамической памяти. Число сыновей обычно ограничено, исходя из смысла решаемой задачи. Так, очень часто рассматриваются бинарные деревья, в которых число сыновей у произвольной вершины не превышает двух. Если один или несколько сыновей у вершины отсутствуют, то соответствующие ссылки содержат нулевые значения. Таким образом, у терминальных вершин все ссылки на сыновей нулевые.
При работе с деревьями очень часто используются рекурсивные алгоритмы, т.е. алгоритмы, которые могут вызывать сами себя. При вызове алгоритма ему передается в качестве параметра ссылка на вершину дерева, которая рассматривается как корень поддерева, растущего из этой вершины. Если вершина терминальная, т.е. у нее нет сыновей, то алгоритм просто применяется к данной вершине. Если же у вершины есть сыновья, то он рекурсивно вызывается также для каждого из сыновей. Порядок обхода поддеревьев зависит от сути алгоритма. В главе, посвященной языку Си, уже был рассмотрен простейший рекурсивный алгоритм, подсчитывающий число терминальных вершин бинарного дерева.
Ниже приведен еще один рекурсивный алгоритм, определяющий высоту дерева. Высотой дерева называется максимальная из длин всевозможных путей от корня дерева к терминальным вершинам. Под длиной пути понимается число вершин, входящих в него, включая первую и последнюю вершины. Так, дерево, состоящее из одной корневой вершины, имеет высоту 1, дерево, приведенное на рисунке в начале этого раздела — высоту 4.
цел алгоритм высота_дерева(вход: вершина V)
| Дано: V - ссылка на корень поддерева
| Надо: Подсчитать высоту поддерева
начало
| цел h, m, s;
| h := 1;
| если у вершины V есть сыновья
| | то    // Ищем поддерево максимальной высоты
| | m := 0;
| | цикл для каждого сына X вершины V выполнить
| | | s := высота_дерева(X);  // Рекурсия!
| | | если s > m
| | | | то m := s;
| | | конец если
| | конец цикла
| | h := h + m;
| конец если
| ответ := h;
конец алгоритма

Множество

Множество — это структура данных, содержащая конечный набор элементов некоторого типа. Каждый элемент содержится только в одном экземпляре, т.е. разные элементы множества не равны между собой. Элементы множества никак не упорядочены. В множество M можно добавить элемент x, из множества M можно удалить элемент x. Если при добавлении элемента x он уже содержится в множестве M, то ничего не происходит. Аналогично, никакие действия не совершаются при удалении элемента x, когда он не содержится в множестве M. Наконец, для заданного элемента x можно определить, содержится ли он в множестве M. Множество — это потенциально неограниченная структура, оно может содержать любое конечное число элементов.
В некоторых языках программирования накладывают ограничения на тип элементов и на максимальное количество элементов множества. Так, иногда рассматривают множество элементов дискретного типа, число элементов которого не может превышать некоторой константы, задаваемой при создании множества. (Тип называется дискретным, если все возможные значения данного типа можно занумеровать целыми числами.) Для таких множеств употребляют название Bitset (``набор битов'') или просто Set. Как правило, для реализации таких множеств используется битовая реализация множества на базе массива целых чисел. Каждое целое число рассматривается в двоичном представлении как набор битов, содержащий 32 элемента. Биты внутри одного числа нумеруются справа налево (от младших разрядов к старшим); нумерация битов продолжается от одного числа к другому, когда мы перебираем элементы массива. К примеру, массив из десяти целых чисел содержит 320 битов, номера которых изменяются от 0 до 319. Множество в данной реализации может содержать любой набор целых чисел в диапазоне от 0 до 319. Число N содержится в множестве тогда и только тогда, когда бит с номером N равен единице (программисты говорят бит установлен). Соответственно, если число N не содержится в множестве, то бит с номером N равен нулю (программисты говорят бит очищен). Пусть, например, множество содержит элементы 0, 1, 5, 34. Тогда в первом элементе массива установлены биты с номерами 0, 1, 5, во втором — бит с номером 2 = 34 - 32. Соответственно, двоичное представление первого элемента массива равно 10011 (биты нумеруются справа налево), второго — 100, это числа 19 и 4 в десятичном представлении. Все остальные элементы массива нулевые.
Хотя в языке программирования Паскаль слово Set, в переводе множество, закреплено за ограниченным множеством элементов дискретного типа, такими множествами далеко не исчерпываются потребности программирования. Например, множество точек на плоскости или множество текстовых строк не являются таковыми. Для множеств общего вида битовая реализация не подходит. Ниже будут рассмотрены несколько других реализаций, используемых для любых множеств.
В программировании довольно часто рассматривают структуру чуть более сложную, чем просто множество: нагруженное множество. Пусть каждый элемент множества содержится в нем вместе с дополнительной информацией, которую называют нагрузкой элемента. При добавлении элемента в множество нужно также указывать нагрузку, которую он несет. В разных языках программирования и в различных стандартных библиотеках такие структуры называют Отображением (Map) или Словарем (Dictionary). Действительно, элементы множества как бы отображаются на нагрузку, которую они несут (заметим, что в математике понятие функции или отображения определяется строго как множество пар; первым элементом каждой пары является конкретное значение аргумента функции, вторым — значение, на которое функция отображает аргумент). В интерпретации Cловаря элемент множества — это иностранное слово, нагрузка элемента — это перевод слова на русский язык (разумеется, перевод может включать несколько вариантов, но здесь перевод рассматривается как единый текст).
Подчеркнем еще раз, что все элементы содержатся в нагруженном множестве в одном экземпляре, т.е. разные элементы множества не могут быть равны друг другу. В отличие от самих элементов, их нагрузки могут совпадать (так, различные иностранные слова могут иметь одинаковый перевод). Поэтому иногда элементы нагруженного множества называют ключами, их нагрузки — значениями ключей. Каждый ключ уникален. Принято говорить, что ключи отображаются на их значения.
В качестве примера нагруженного множества наряду со словарем можно рассмотреть множество банковских счетов. Банковский счет — это уникальный идентификатор, состоящий в случае российских банков из 20 десятичных цифр. Нагрузка счета — это вся информация, которая ему соответствует, включающая имя и адрес владельца счета, код валюты, сумму остатка, информацию о последних транзакциях и т.п.
Наиболее часто применяемая операция в нагруженном множестве — это определение нагрузки для заданного элемента x (значения ключа x). Реализация этой операции включает поиск элемента x в множестве, поэтому эффективность любой реализации множества определяется прежде всего быстротой поиска.

Реализации множества: последовательный и бинарный поиск, хеширование

Рассмотрим для простоты реализацию обычного, не нагруженного, множества. (Реализация нагруженного множества аналогична реализации обычного, просто параллельно с элементами нужно дополнительно хранить нагрузки элементов.) В наивной реализации множества его элементы хранятся в массиве, начиная с первой ячейки. Специальная переменная содержит текущее число элементов множества, т.е. количество используемых в данный момент ячеек массива.
При добавлении элемента x к множеству сначала необходимо определить, содержится ли он в множестве (если содержится, то множество не меняется). Для этого используется процедура поиска элемента, которая отвечает на вопрос, принадлежит ли элемент x множеству, и, если принадлежит, выдает индекс ячейки массива, содержащей x. Та же процедура поиска используется и при удалении элемента из множества. При добавлении элемента он дописывается в конец (в ячейку массива с индексом число элементов) и переменная число элементов увеличивается на единицу. Для удаления элемента достаточно последний элемент множества переписать на место удаляемого и уменьшить переменную число элементов на единицу.
В наивной реализации элементы множества хранятся в массиве в произвольном порядке. Это означает, что при поиске элемента x придется последовательно перебрать все элементы, пока мы либо не найдем x, либо не убедимся, что его там нет. Пусть множество содержит 1,000,000 элементов. Тогда, если x содержится в множестве, придется просмотреть в среднем 500,000 элементов, если нет — все элементы. Поэтому наивная реализация годится только для небольших множеств.

Бинарный поиск

Пусть можно сравнивать элементы множества друг с другом, определяя, какой из них больше. (Например, для текстовых строк применяется лексикографическое сравнение: первые буквы сравниваются по алфавиту; если они равны, то сравниваются вторые буквы и т.д.) Тогда можно существенно убыстрить поиск, применяя алгоритм бинарного поиска. Для этого элементы множества хранятся в массиве в возрастающем порядке. Идея бинарного поиска иллюстрируется следующей шуточной задачей: : "Как поймать льва в пустыне? Надо разделить пустыню забором пополам, затем ту половину, в которой находится лев, снова разделить пополам и так далее, пока лев не окажется пойманным".
В алгоритме бинарного поиска мы на каждом шагу делим отрезок массива, в котором может находиться искомый элемент x, пополам. Рассматриваем элемент y в середине отрезка. Если x меньше y, то выбираем левую половину отрезка, если больше, то правую. Таким образом, на каждом шаге размер отрезка массива, в котором может находиться элемент x, уменьшается в два раза. Поиск заканчивается, когда размер отрезка массива (т.е. расстояние между его правым и левым концами) становится равным единице, т.е. через [log2n]+1 шагов, где n — размер массива. В нашем примере это произойдет после 20 шагов (т.к. log21000000 < 20). Таким образом, вместо миллиона операций сравнения при последовательном поиска нужно выполнить всего лишь 20 операций при бинарном.
Запишем алгоритм бинарного поиска на псевдокоде. Дан упорядоченный массив a вещественных чисел (вещественные числа используются для определенности; бинарный поиск можно применять, если на элементах множества определен линейный порядок, т.е. для любых двух элементов можно проверить их равенство или определить, какой их них больше). Пусть текущее число элементов равно n. Элементы массива упорядочены по возрастанию:

a[0] < a[1] < · ·· < a[n - 1]

Мы ищем элемент x. Требуется определить, содержится ли x в массиве. Если элемент x содержится в массиве, то надо определить индекс i ячейки массива, содержащей x:

найти i:   a[i] = x

Если же x не содержится в массиве, то надо определить индекс x, такой, что при добавлении элемента x в i-ю ячейку массива элементы массива останутся упорядоченными, т.е.

найти i:   a[i-1] < x =< a[i]

(считается, что a[-1] = -∞, a[n] = + ∞). Объединив оба случая, получим неравенство

a[i-1] < x =< a[i]

Используем схему построения цикла с помощью инварианта. В процессе выполнения хранятся два индекса b и e (от слов begin и end), такие, что

a[b] < x =< a[e]

Индексы b и e ограничивают текущий отрезок массива, в котором осуществляется поиск. Приведенное неравенство является инвариантом цикла. Перед началом выполнения цикла рассматриваются разные исключительные случаи — когда массив пустой (n=0), когда x не превышает минимального элемента массива (x =< a[0]) и когда x больше максимального элемента (x > a[n-1]). В общем случае выполняется неравенство

a[0] < x =< a[n-1])

Полагая b = 0, e = n - 1, мы обеспечиваем выполнение инварианта цикла перед началом выполнения цикла. Условие завершения состоит в том, что длина участка массива, внутри которого может находится элемент x, равна единице:

b - e = 1

В этом случае

a[e-1] < x =< a[e]

т.е. искомый индекс i равен e, а элемент x содержится в массиве тогда и только тогда, когда x = a[e]. В цикле мы вычисляем середину c отрезка [b,e]

с = целая часть ((b+e)/2)

и выбираем ту из двух половин [b,c] или [c,e], которая содержит x. Для этого достаточно сравнить x со значением a[c] в середине отрезка. Завершение цикла обеспечивается тем, что величина e - b монотонно убывает после каждой итерации цикла.
Приведем текст алгоритма бинарного поиска:

лог алгоритм бинарный_поиск(
    вход: цел n, вещ a[n], вещ x, выход: цел i
)
| Дано: n — число элементов в массиве a,
|       a[0] < a[1] < ... < a[n-1]
| Надо: ответ := (x содержится в массиве),
|       вычислить i, такое, что 
|           a[i-1] < x <= a[i]
|       (считая a[-1] = -беск., a[n] = +беск.)
начало
| цел b, e, c;
|
| // Рассматриваем сначала исключительные случаи
| если (n == 0)
| | то i = 0;
| | ответ := ложь;
| иначе если (x <= a[0])
| | i := 0;
| | ответ := (x == a[0]);
| иначе если (x > a[n-1])
| | i := n
| | ответ := ложь;
| иначе
| | // Общий случай
| | утверждение: a[0] < x <= a[n-1];
| | b := 0; e := n-1;
| |
| | цикл пока e - b > 1
| | | инвариант: a[b] < x  и  x <= a[e];
| | | c := целая часть((a + b) / 2);
| | | если x <= a[c]
| | | | то e := c;
| | | иначе
| | | |    b := c;
| | | конец если
| | конец цикла
| |
| | утверждение: e - b == 1  и
| |              a[b] < x <= a[e];
| | i := e;
| | ответ := (x == a[i]);
| конец если
конец алгоритма

Реализации множества на базе деревьев

Реализация множества с помощью бинарного поиска во всех отношениях лучше наивной реализации. Вместе с тем, она все же имеет недостатки: 1) при добавлении и удалении элементов в середине массива приходится переписывать элементы в конце массива на новое место, чтобы освободить место для добавляемого элемента либо закрыть образовавшуюся лакуну при удалении элемента; 2) поиск выполняется гарантированно быстро, но все-таки не мгновенно. От первого из этих недостатков можно избавиться, применяя вместо непрерывной реализации на базе массива ссылочную реализацию, при которой элементы множества содержатся в вершинах бинарного дерева. Элементы в вершинах упорядочены таким образом, что, если зафиксировать некоторую вершину V и рассмотреть два поддерева, соответствующих левому и правому сыновьям вершины, то все элементы в вершинах левого поддерева должны быть меньше, чем элемент в вершине V, а все элементы в вершинах правого поддерева должны быть больше него.
Для такого дерева можно также применять алгоритм бинарного поиска. Максимальное число сравнений при поиске в таком дереве равняется его высоте ( т.е. максимальной длине пути от корня к терминальной вершине).
Чтобы поиск выполнялся быстро, дерево должно быть сбалансированным, т.е. все его ветви должны иметь почти одинаковую длину.
Точное определение сбалансированности следующее: будем считать, что у каждой вершины, включая терминальные, ровно два сына, при необходимости добавляя внешние, или нулевые, вершины. Например, у терминальной вершины оба сына нулевые. (Это в точности сответствует представлению дерева в языке Си, где каждая вершина хранит два указателя на сыновей; если сына нет, то соответствующий указатель нулевой.) Обычные вершины дерева будем называть собственными. Рассмотрим путь от корня дерева к внешней (нулевой) вершине. Длиной пути считается количество собственных вершин в нем. Дерево называется сбалансированным, если длины всех возможных путей от корня дерева к внешним вершинам различаются не более чем на единицу. Иногда в литературе такие деревья называют почти сбалансированными, понимая под сбалансированностью строгое равенство длин всех путей от корня к внешним узлам; мы, однако, будем придерживаться нестрогого определения. Пример сбалансированного дерева представлен на рисунке.
Высота сбалансированного дерева h оценивается логарифмически в зависимости от числа вершин n:

h <= log2n + 1

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

AVL-деревья

Так называемые AVL-деревья (названные в честь их двух изобретателей Г.М. Адельсона-Вельского и Е.М. Ландиса) хранят дополнительно в каждой вершине разность между высотами левого и правого поддеревьев, которая в сбалансированном дереве может принимать только три значения: -1, 0, 1. Строго говоря, AVL-деревья не являются сбалансированными в смысле приведенного выше определения. Требуется только, чтобы для любой вершины AVL-дерева разность высот ее левого и правого поддеревьев была по абсолютной величине не больше единицы. При этом длины путей от корня к внешним вершинам могут различаться больше, чем на единицу. Можно, тем не менее, доказать, что и в случае AVL-деревьев их высота оценивается сверху логарифмически в зависимости от числа вершин:

h <= C log2 n

где константа C = 1.5. Обычно константы не очень важны в практическом программировании — принципиально лишь, по какому закону увеличивается время работы алгоритма при увеличении n. В данном случае зависимость логарифмическая, т.е. наилучшая из всех возможных (поскольку поиск невозможен быстрее чем за log2 n операций).
Новый элемент всегда добавляется в дерево в соответствии с упорядоченностью как левый или правый сын некоторой вершины, у которой данного сына до этого не было (или, как мы считаем, сын являлся внешним). Новая вершина добавляется как терминальная. После этого выполняется процедура восстановления балансировки. В ней используются следующие элементарные преобразования дерева, сохраняющие упорядоченность вершин:

  1. вращение вершины x поддерева влево:

Здесь вершина x поддерева, которая является его корнем, опускается вниз и влево. Бывший правый сын d вершины x становится новым корнем поддерева, а x становится левым сыном d. (Вершины x и d, начальник и подчиненный, как бы меняются ролями: бывший начальник становится подчиненным.) Поддерево c, которое было левым сыном вершины d, переходит в подчинение от вершины d к вершине x и становится ее правым сыном. Отметим, что упорядоченность вершин сохраняется: a < b < c< d < e. Таким образом, для выполнения преобразования надо лишь заменить фиксированное количество указателей в вершинах x, d, c и, возможно, в родительской для x вершине;

  1. вращение вершины x поддерева вправо:

Здесь вершина x опускается вниз и вправо, ее бывший левый сын b становится новым корнем поддерева, а x — его правым сыном. Поддерево c переходит в подчинение от b к x.
Операции вращения носят локальный характер и позволяют при необходимости исправить баланс поддерева с корнем x. Например, для восстановления баланса дерева, показанного на следующем рисунке, достаточно выполнить одно вращение вершины b влево:
В случае AVL-деревьев операции вращения повторяются в цикле при восстановлении баланса после добавления или удаления элемента, число вращений не превышает С · h, где h — высота дерева, C — константа. Таким образом, как поиск элемента, так и его добавление или удаление выполняется за логарифмическое время: t <= C · log2n.

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

Исторически AVL-деревья, изобретенные в 1962 г., были одной из первых схем реализации почти сбалансированных деревьев. В настоящее время, однако, более популярна другая схема: красно-черные деревья, или RB-деревья, от англ. Red-Black Trees. Красно-черные деревья были введены Р. Байером в 1972 г. В стандартной библиотеке классов языка C++ исполнители множество и нагруженное множество — классы set и map — реализованы именно как красно-черные деревья.
Вместо баланс-фактора, применяемого в AVL-деревьях, RB-деревья используют цвета вершин. Каждая вершина окрашена либо в красный, либо в черный цвет. (В реализации за цвет отвечает логическая переменная.) При этом выполняется несколько дополнительных условий:

  1. каждая внешняя (или нулевая) вершина считается черной;
  2. корневая вершина дерева черная;
  3. у красной вершины дети черные;
  4. всякий путь от корня дерева к произвольной внешней вершине имеет одно и то же количество черных вершин.

Последний пункт определения означает сбалансированность дерева по черным вершинам.
Ниже приведен пример красно-черного дерева. Черные вершины изображены темно-серым цветом, красные — белым.
Из пункта 3) определения следует, что в произвольном пути от корня к терминальной вершине не может быть двух красных вершин подряд. Это означает, что, поскольку число черных вершин в любом пути одинаково, длины разных путей к терминальным вершинам отличаются не более чем вдвое. Это свойство близко по своей сути к сбалансированности. Несложно показать, что для красно-черного дерева справедлива следующая оценка сверху на высоту дерева в зависимости от числа вершин:

h <= 2 log2 (n+1)

Из этого следует, что поиск в красно-черном дереве также выполняется за логарифмическое время.
Новая вершина добавляется в красно-черное дерево как терминальная после процедуры поиска (этим RB-дерево ничем не отличается от других упорядоченных деревьев). Новая вершина окрашивается в красный цвет. При этом пункт 3) в определении красно-черного дерева может нарушиться. Поэтому после добавления, а также удаления вершины выполняется процедура восстановления структуры красно-черного дерева, играющая ту же роль, что и восстановление балансировки AVL-дерева. Преимущество красно-черных деревьев состоит в том, что процедура восстановления более простая. Во многих случаях она ограничивается перекрашиванием вершин. В ней также могут выполняться операции вращения вершины влево и вправо, но число вращений может быть не больше двух при добавлении элемента и не больше четырех при удалении. Всего число операций при восстановлении структуры RB-дерева оценивается сверху через высоту дерева:

число операций <= K · h

где h — высота дерева, K — константа. Поскольку для высоты RB-дерева справедлива приведенная выше логарифмическая оценка от числа вершин n, получаем оценку

число операций <= C log2 n

где C - константа. Таким образом, добавление и удаление элементов выполняется в случае красно-черных деревьев за логарифмическое время в зависимости от числа вершин дерева.
Хеширование
Рассмотрим другую реализацию множества, в которой поиск элемента чаще всего происходит почти мгновенно. Правда, в исключительных случаях поиск может быть долгим, и поэтому такая реализация не подходит для программ, в которых требуется повышенная надежность, например, при управлении реальными процессами.
Идея хеш-реализации состоит в том, что мы сводим работу с одним большим множеством к работе с массивом небольших множеств. Рассмотрим, к примеру, записную книжку. Она содержит список фамилий людей с их телефонами (телефоны — это нагрузка элементов множества). Страницы записной книжки помечены буквами алфавита; страница, помеченная некоторой буквой, содержит только фамилии, начинающиеся с этой буквы. Таким образом, все множество фамилий разбито на 28 подмножеств, соответствующих буквам русского алфавита. При поиске фамилии мы сразу открываем записную книжку на странице, помеченной первой буквой фамилии, и в результате поиск значительно убыстряется.
Разбиение множества на подмножества осуществляется с помощью так называемой хеш-функции. Хеш-функция определена на элементах множества и принимает целые неотрицательные значения. Она должна быть подобрана таким образом, чтобы 1) ее можно было легко вычислять; 2) она должна принимать всевозможные различные значения приблизительно с равной вероятностью; 3) желательно, чтобы на близких значениях аргумента она принимала далекие друг от друга значения (свойство, противоположное математическому понятию непрерывности). В приведенном примере значение хеш-функции для данной фамилии равно номеру первой буквы фамилии в русском алфавите.
Параметром реализации является число подмножеств, которое также называют размером хеш-таблицы. Пусть он равен N. Тогда хеш-функция должна принимать значения 0, 1, 2, ... , N - 1. Если изначально у нас есть некоторая функция H(x), принимающая произвольные целые неотрицательные значения, то в качестве хеш-функции можно использовать функцию h(x), равную остатку от деления H(x) на N.
Множество M разбивается на N непересекающихся подмножеств, занумерованных индексами от 0 до N - 1. Подмножество Mi с индексом i содержит все элементы x из M, значения хеш-функции для которых равняются i:
Mi = {x €  M : h(x) = i}
При поиске элемента x сначала вычисляется значение его хеш-функции: t = h(x). Затем мы ищем x в подмножестве Mt . Поскольку это подмножество небольшое, то поиск осуществляется быстро. Для эффективной реализации каждое подмножество должно в большинстве случаев содержать не больше одного элемента. Следовательно, размер хеш-таблицы N должен быть больше, чем среднее число элементов множества. Обычно N выбирают превышающим число элементов множества примерно в три раза. В примере с записной книжкой это означает, что в ней должно быть записано около 10 фамилий. В таком случае большинство страниц либо пустые, либо содержат одну фамилию, хотя не исключены и коллизии, когда на одной странице записаны несколько фамилий.
Мы привели только идею хеш-реализации множества. Различные конкретные схемы по-разному реализуют массив подмножеств и борются с коллизиями. Приведем наиболее универсальную схему, использующую ссылочную реализацию. Каждое подмножество представляется в виде линейного однонаправленного списка, содержащего элементы подмножества. Таким образом, имеемся N списков. Головы всех списков хранятся в одном массиве размера N, который называется хеш-таблицей. Элемент хеш-таблицы с индексом i представляет собой голову i-го списка. Голова содержит ссылку на первый элемент списка, первый элемент — на второй и так далее. Последний элемент в цепочке содержит нулевую ссылку, т.е. ссылку в никуда. Если список пустой, то элемент хеш-таблицы с индексом i содержит нулевую ссылку.
Циклы для каждого и итераторы
Часто бывает необходимо перебрать все элементы структуры данных и для каждого элемента выполнить некоторое действие. Обычно при записи алгоритмов на неформальном языке используется конструкция цикл для каждого; например, в случае множества M можно записать следующий фрагмент программы:
цикл для каждого элемента x из множества M
| действие(x);
конец цикла
В большинстве структур данных такой цикл можно реализовать, пользуясь другими действиями, возможными для структуры этого типа. Например, для списка можно использовать следующий фрагмент программы:
установить указатель в начало списка;
цикл пока указатель не в конце списка
| действие(элемент за указателем);
| передвинуть указатель вперед;
конец цикла
Множество отличается от всех других структур данных тем, что цикл для каждого невозможно смоделировать, пользуясь другими предписаниями множества. Поэтому выполнение такого цикла должно быть обеспечено реализацией множества. Метод построения цикла для каждого в сильной степени зависит от используемого языка программирования и от конкретной библиотеки классов или подпрограмм. Как правило, создается некоторый объект, позволяющий последовательно перебирать элементы структуры. Внутреннее устройство такого объекта зависит от структуры данных и скрыто от программиста. Объект такого типа обычно называют итератором или энумератором. С итератором возможны два действия:

  1. проверить, есть ли еще элементы структуры данных, которые не были перебраны на предыдущих шагах;
  2. получить следующий элемент структуры данных.

Реализация структуры данных должна обеспечить реализацию предписания, которое создает и инициализирует объект типа итератор, предназначенный для перебора элементов структуры.
В случае множества М цикл для каждого записывается с помощью итератора примерно так:
итератор := начать перебор элементов множества M;
цикл пока итератор.есть еще элементы
| x := итератор.получить следующий элемент множества;
| действие(x);
конец цикла
Мы рассмотрели наиболее важные структуры данных, используемые в программировании, и методы их реализации. Конечно, этими примерами не исчерпывается все многообразие структур данных. Однако, большинство реальных примеров либо аналогичны рассмотренным, либо получаются комбинацией нескольких элементарных структур — например, реализация массива множеств может использовать списки или деревья. Искусство программиста состоит в том, чтобы выбрать структуру данных, наиболее подходящую для решаемой задачи, чтобы в ней отсутствовали массовые операции, память расходовалась экономно и поиск выполнялся быстро. И, пожалуй, один из главных критериев — это простота и изящество программы, которая получается в результате.
http://localhost:3232/img/empty.gif

 

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика