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

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

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

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

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

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

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

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

Интерфейс

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

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