Множество и словарь. Реализация на деревьях поиска

Редактирование данной статьи ещё не завершено.

Общие сведения

Иногда решение задачи требует применения абстрактного типа данных «Множество», однако отсутствует возможность отмечать каждое допустимое значение отдельной логической переменной (если множество имеет большую мощность или бесконечно, как, например, множество строк или вещественных чисел). В этом случае необходима такая реализация множества, которая явно хранит выбранные элементы внутри себя, а также позволяет оперативно их отыскивать, добавлять и удалять. Такие требования роднят множество с другим типом данных, именуемым словарём.

Словарь (англ. dictionary, map) — абстрактный тип данных, позволяющий хранить набор значений, обращение к которым происходит по ключам. Ключи должны допускать сравнение друг с другом. Примеры словарей достаточно разнообразны:

• Обычный толковый словарь хранит определения слов (являющиеся значениями), сопоставленные с самими словами (являющимися ключами);
• Банковская база данных может хранить данные клиентов, сопоставленные с номерами счетов;
• Экзаменационная ведомость содержит оценки, сопоставленные с фамилиями студентов, и т. д.

Множество можно рассматривать как словарь, в котором ключ элемента совпадает с его значением. Массив можно рассматривать как словарь, в котором ключи являются целыми числами. С другой стороны, словарь можно рассматривать как массив, тип индексов которого может не быть целочисленным. Например, содержимое телефонного справочника можно рассматривать как массив телефонных номеров, индексами в котором являются фамилии абонентов. Отсюда другое название словаря — ассоциативный массив (англ. assotiative array).

Как и для случая множеств, возможна такая реализация словаря, в которой каждому ключу могут быть сопоставлены несколько значений (тогда для обозначения применяется термин multimap).

Интерфейс

Стандартный интерфейс множества был рассмотрен в статье «Множество (реализация на битовых векторах)». Операции словаря похожи на операции множества, но в качестве параметров принимают ключи, а не непосредственные значения элементов.

void insert(T1 key, T2 value)	— добавление пары (key, value) в словарь;
void remove(T1 key)	— исключение из словаря значения, сопоставленного с ключом key;
T2 find(T1 key)	— получение значения, сопоставленного с ключом key.

Реализация

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

• Неупорядоченный массив пар. В этом случае добавление пары в конец массива имеет сложность O(1), поиск по ключу требует просмотра всего массива (O(N)), удаление также может потребовать сдвига всех элементов (O(N)).
• Отсортированный по ключам массив пар. Добавление пары в нужное место может потребовать сдвига всех элементов (O(N)), бинарный поиск по ключу требует O(logN), удаление может потребовать сдвига всех элементов (O(N)).
• Список пар позволит производить добавление и удаление за O(1), то поиск будет требовать O(N).

Можно видеть, что все предложенные варианты содержат операции с линейным временем работы, которое серьёзно ограничивает область их применения. Тем не менее, возможен подход, который позволяет достичь вычислительной сложности O(logN) для каждой из операций. Этот подход основан на применении структур данных, называемых деревьями поиска.