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

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

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

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

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

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

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

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

Интерфейс

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

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

Демонстрация работы

Визуализатор древовидных структур, вкладка «BST».

Реализация

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

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

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

Определение двоичного дерева поиска

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

struct TreeNode {
    int key;
    int value;
    TheeNode *left, *right;
    TreeNode (int k, int v, Node *l, Node *r) {
       key = k;
       val = v;
       left = l;
       right = r;
    }
};

Структура данных, являющаяся связной совокупностью таких узлов, называется двоичным деревом (англ. binary tree). Группа деревьев именуется лесом (англ. forest).

Пусть вершина A указывает на вершины B и C. Тогда B и C — потомки A, A — родитель B и C. Односвязный список имеет начальный элемент; по аналогии, двоичное дерево также имеет стартовую вершину — корень. Из корня по указателям можно добраться до любой вершины дерева. Вершины, не имеющие потомков, называются листьями.

Когда речь идёт о двоичном дереве поиска (англ. binary search tree, BST), подразумевается дерево, на элементы которого наложены дополнительные ограничения по размещению. Мы уже сталкивались с подобным: двоичное дерево, в котором ключ вершины не меньше, чем ключи её потомков, именуется пирамидой. В пирамиде непосредственные потомки узла являются равноправными; в двоичном дереве поиска выделяется левый потомок и правый потомок, и дополнительное ограничение сформулировано следующим образом: ключи в левом поддереве не превышают ключа в родителе, а ключи в правом поддереве больше ключа в родителе.

Поиск в двоичном дереве

Пусть имеется указатель на корень дерева TreeNode *root и требуется найти элемент с ключом k. Ключ k можно сравнить с root->key, и если повезёт, то требуемый элемент будет найден. В противном случае можно однозначно сказать, в каком из поддеревьев root может находиться элемент с ключом k: если k < root->key, то его следует искать в поддереве root->left, иначе — в root->right. Рассматриваемое поддерево имеет все свойства исходного двоичного дерева, поэтому действия по поиску можно повторить рекурсивно. Очевидно, что поиск завершается в одном из двух случаев: либо элемент найден, либо текущее поддерево стало пустым, т. е. поиск спустился до листьев и не встретил нужного элемента.

Рекурсивная реализация:		Итеративная реализация:
TreeNode *find(TreeNode *n, int k) { if (n == NULL || k == n->key) return n; if (k < n->key) return find(n->left, k); else return find(n->right, k); }		TreeNode *find(TreeNode *n, int k) { while (n != NULL && k != n->key) if (k < n->key) n = n->left; else n = n->right; return n; }

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

int find(int key) {
    TreeNode *res = find(root, key);
    if (res != NULL)
        return res->value;
    else
        return -1;
}

Худшим случаем для операции поиска является отсутствие нужного элемента в дереве. Тогда поиск спускается от корня до листа и затем возвращает значение NULL. Будем называть высотой дерева h количество вершин (или их связей, что на единицу меньше) на самом длинном пути от корня до какого-либо из листьев. Очевидно, что сложность операции поиска составляет O(h).

Вставка в двоичное дерево поиска

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

Будем идти от корня, спускаясь в те поддеревья, которые должны содержать добавляемый ключ. Когда спуск достигает значения NULL, остаётся только заменить указатель на это значение указателем на новый элемент.

void insert(int key, int value) {
    if (root == NULL) {
        root = new TreeNode(key, value, NULL, NULL);
        return;
    }
    TreeNode *n = root;
    while (true) {
        if (key <= n->key) {
            if (n->left == NULL) {
                n->left = new TreeNode(key, value, NULL, NULL);
                return;
            } else {
                n = n->left;
            }
        } else {
            if (n->right == NULL) {
                n->right = new TreeNode(key, value, NULL, NULL);
                return;
            } else {
                n = n->right;
            }
        }
    }
}

Таким образом, добавляемый элемент всегда становится листом двоичного дерева поиска. Достаточно очевидно, что вычислительная сложность операции вставки равна O(h).