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

Текст этой статьи готов, но ещё не обновлены изображения.

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

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

Словарь (англ. 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).

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

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

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

struct TreeNode {
    int key;
    int value;
    TreeNode *left, *right;
    TreeNode (int k, int v) {
       key = k;
       val = v;
       left = right = NULL;
    }
};

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

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

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

**Примеры двоичных деревьев поиска**
Основные определения		Полностью заполненное дерево и вырожденное дерево

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

Поиск в двоичном дереве: сверху — успешный поиск ключа 31, снизу — поиск отсутствующего ключа 23

Пусть имеется указатель на корень дерева 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).

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

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

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

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

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

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

Порядок добавления элементов в двоичное дерево поиска играет очень важную роль. Минимальная высота двоичного дерева поиска, содержащего N элементов, равна ⌈log₂N⌉; в этом случае заполнение дерева элементами равномерно, высоты поддеревьев любой вершины различаются не более чем на единицу, а само дерево именуется сбалансированным. Но существует и обратный случай, когда каждое добавление элемента увеличивает высоту дерева на 1, в результате дерево вырождается в односвязный список, а его высота становится равной N. Итоговая форма дерева зависит только от порядка добавления элементов.

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

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

Расположение элемента, который требуется удалить, определяется тем же методом, что был использован в процедурах поиска и вставки. Однако далее возможны различные варианты действий:

Если удаляемый элемент является листом (не имеет потомков), то достаточно убрать ссылку на него из его родителя;
Если удаляемый элемент имеет только одного потомка, то ссылка на удаляемый элемент в родителе заменяется ссылкой на этого потомка;
Наконец, наиболее нетривиальной является ситуация, когда удаляемый элемент имеет двух потомков. Рассмотрим её отдельно.

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

Чтобы при этом не нарушилось основное свойство двоичного дерева, ключ этого потомка должен быть не меньше всех ключей левого поддерева удаляемого узла и меньше всех ключей правого поддерева удаляемого узла. Как можно догадаться, этому условию удовлетворяет только один потомок — узел с максимальным ключом в левом поддереве, непосредственный предшественник удаляемого узла. Найти его можно, переходя по правым ссылкам в поддереве n->left, где n — удаляемый элемент. Далее производится обмен этих узлов и уничтожение ссылки на удаляемый узел.

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

Желающие всё же могут ознакомиться здесь с примером реализации удаления элемента. Для наглядности данная процедура использует несколько вспомогательных методов.

TreeNode *parent(TreeNode *n) {
    if (n == root)
        return NULL;
    TreeNode *p = root;
    while (true) {
        if (n->key <= p->key) {
            if (p->left->key == key)
                break;
            p = p->left;
        } else {
            if (p->right->key == key)
                break;
            p = p->right;
        }
    }
    return p;
}

TreeNode *predecessor(TreeNode *n) {
    TreeNode *l = n->left;
    while (l->right != NULL)
        l = l->right;
    return l;
}

void exclude(TreeNode *n) {
    TreeNode *p = parent(n);
    TreeNode *c = n->left ? n->left : n->right;
    if (p == NULL)
        root = c;
    else if (p->left == n)
        p->left = c;
    else
        p->right = c;
}

void remove(int key) {
    TreeNode *n = find(key, root);
    if (n == NULL)
        return;
    if (n->left && n->right) {
        TreeNode *pred = predecessor(n);
        n->key = pred->key;
        n->value = pred->value;
        n = pred;
    }
    exclude(n);
    delete n;
}

Функция exclude() принимает указатель на узел n, имеющий не более одного непосредственного потомка, определяет для этого узла его родителя p (с помощью функции parent()) и потомка c, а затем исправляет ссылку (p => n) на (p => с), исключая, таким образом, n из дерева поиска.

Таким образом, первые два случая удаления обрабатываются за счёт функции exclude(). Если же удаляемый узел имеет двух потомком, то с помощью метода predecessor() определяется его непосредственный предшественник, его данные копируются на место удаляемого узла, а ссылка на удаляемый узел перемещается на предшественника. Теперь удаляемый узел вновь имеет не более 1 потомка и может быть обработан методом exclude().

Операция удаления требует определения родителя элемента, в отдельных случаях — отыскания предшественника, а также ещё O(1) действий. Итоговая вычислительная сложность составляет O(h).

Рекурсивный обход двоичного дерева поиска

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

void traverse(TreeNode *n) {
    if (n == NULL)
        return;
    traverse(n->left);
    printf("%d", n->value);
    traverse(n->right);
}

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

Данный обход (левое поддерево — родитель — правое поддерево) является лишь одним из шести возможных. На иллюстрации приведены результаты каждого типа обхода для одного и того же дерева.

Ниже приведён код реализации словаря на двоичном дереве поиска. Ключами и значениями являются целые числа. Операция удаления опущена.

class Map {

    struct TreeNode {
        int key;
        int value;
        TreeNode *left, *right;
        TreeNode (int k, int v) {
            key = k;
            val = v;
            left = right = NULL;
        } 
    } root;

public:
 
    Map() {
        root = NULL;
    }

    int find(int key) {
        TreeNode *res = root;
        while (res != NULL && res->key != key)
            res = res->key < key ? res->left : res->right;
        return res ? res->value : -1;
    }

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

};

Некоторые вопросы для размышления:

Как может выглядеть рекурсивная реализация вставки и удаления элемента двоичного дерева поиска?
Как реализовать отыскание максимума (минимума) в двоичном дереве поиска? Можно ли организовать очередь с приоритетами на двоичном дереве поиска?
Как, в общем случае, реализовать операции поиска элемента, предшествующего данному, и элемента, следующего за данным?

Множество на деревьях поиска в STL

В стандартной библиотеке шаблонов C++ присутствует шаблон set<T>. Для возможности его использования требуется подключить заголовочный файл <set> и пространство имён std. В том же заголовочном файле описан шаблон multiset<T>, представляющий множество, в котором могут храниться несколько одинаковых значений. Оба шаблона обычно реализованы на балансирующихся двоичных деревьях поиска.

#include <iostream>
#include <set>
using namespace std;
int main() {
    set<int> s;
    for (int i = 1; i < 6; i++)
        s.insert(i * i);
    for (int i = 0; i < 30; i++) {
        if (s.find(i) != s.end())
            cout << i << ' ';
    return 0;       //результат "1 4 9 16 25"
}

STL предоставляет следующий набор методов для множества (тип It обозначает итератор, тип size_t — беззнаковое целое):

`set<T>()`	— конструктор множества; поддерживается инициализация парой итераторов;
`pair<It, bool> insert(T x);`	— добавление значения `x` в множество. Метод возвращает пару, первый элемент которой указывает на элемент со значением `val`, а второй равен `true`, если элемент был добавлен, либо `false`, если такой элемент уже был в множестве. Эквивалент этого метода для шаблона `multiset` возвращает только итератор, указывающий на добавленный элемент;
`size_t erase(T x);`	— исключение значения `x` из множества. Возвращает количество исключённых элементов. Метод также поддерживает удаление элемента на определённой позиции, если передать ему не значение, а итератор (или пару итераторов);
`It find(T x);`	— поиск элемента `x` в множестве. Метод возвращает итератор, указывающий на найденный элемент, либо итератор `set::end()`, если элемент не был найден;
`size_t count(T x);`	— подсчёт количества элементов, равных `x`;
`size_t size();`	— получение количества элементов в множестве;
`size_t max_size();`	— получение максимального возможного (для данного компьютера и реализации STL) количества элементов в множестве;
`bool empty();`	— проверка множества на пустоту;
`void clear();`	— очистка множества (исключение всех элементов);
`It lower_bound(T x);`	— получение итератора, указывающего на минимальный элемент, не меньший `x`. Если такого элемента нет, возвращается итератор `set::end()`;
`It upper_bound(T x);`	— получение итератора, указывающего на минимальный элемент, больший `x`. Если такого элемента нет, возвращается итератор `set::end()`;
`pair<It, It> equal_range(T x)`	— получение пары итераторов, аналогичных результатам двух описанных выше методов.

Элементы внутри set и multiset являются упорядоченными по возрастанию.

Словарь на деревьях поиска в STL

В стандартной библиотеке шаблонов C++ присутствует шаблон map<T1, T2>. Для возможности его использования требуется подключить заголовочный файл <map> и пространство имён std. В том же заголовочном файле описан шаблон multimap<T>, представляющий словарь, в котором могут храниться несколько пар с одинаковыми ключами. Оба шаблона обычно реализованы на балансирующихся двоичных деревьях поиска.

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
    map<int, string> m;
    m.insert(make_pair(1828, "Tolstoy"));  
    m.insert(make_pair(1799, "Pushkin"));
    m.insert(make_pair(1821, "Dostoevsky"));
    map<int, string>::iterator it, end;
    it  = m.lower_bound(1750);
    end = m.upper_bound(1850);
    for (; it != end; it++) {
       cout << it->second << "(" << it->first << ") ";
    }
    return 0;       //результат "Pushkin (1799) Dostoevsky (1821) Tolstoy (1828) "
}