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

Есть четыре основных варианта хранения:

• Массив
• Хэш таблица
• Деревья
• Списки

Массив — это способ хранения, при котором элементы множества расположены последовательно в ячейках.

Самый экономичный вариант, если известна мощность множества, а элементы - данные одного типа.

Список — способ хранения, при котором память выделяется для каждого элемента отдельно и ровно столько, сколько нужно.

Недостаток: необходимо хранить указатель на следующий элемент и тратить время на работу с ним.

Сложность массива и списка - линейна, $O(n)$.

Хеш-таблица — это обобщение способа хранения множества целых чисел (ключей) в форме вектора битов на случай, когда мощность универсума U очень велика по отношению к мощности множеств, с которыми нужно работать.

Хэш-функция — преобразует значения ключей к интервалу [0, m – 1], где m — размер хеш-таблицы, $m \ll |U|$. Очевидно, что при этом каждому индексу хеш-таблицы будет соответствовать много различных значений ключей. Поэтому, во-первых, в хеш-таблице приходится хранить не биты, а сами значения ключей, а во-вторых, имеется возможность размещать в ней более одного ключа для каждого значения функции отображения (разрешать коллизии).

Если таблица построена правильно и не переполнена, то все функции (удаления, встатвки и тд) выполняются за постоянное время. В худшем случае (если коллизия - повторяющиеся элементы) - сложность линейная $O(n)$.

Дерево двоичного поиска (ДДП) — это способ хранения множества в форме расширяемого упорядоченного списка с сохранением упорядоченности при вставке новых элементов без перемещения уже имеющихся.

ДДП — это дерево с нагруженными узлами, вес в любом узле которого больше любого веса в левом его поддереве и не больше любого веса в правом поддереве. Количество шагов алгоритма поиска элемента множества в таком дереве не превышает его высоты, т. е. имеет сложность $O(\log n)$. Такую же сложность имеют операции вставки нового элемента в дерево и удаления элемента.

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

Node* build(int a, int b, int* data) // Сборка ДДП из массива узлов data
{
    if (b <= a)
        return 0;

    int c = (a + b) / 2;
    Node* s = new Node(data[c]);

    s->left = build(a, c, data);
    s->right = build(c + 1, b, data);

    return s;
}

Недостаток ДДП — в том, что оно хорошо работает только в том случае, если сбалансировано, т. е. длины путей из корня в любой лист примерно одинаковы. Однако при поэлементной вставке в дерево упорядоченной последовательности дерево вырождается, превращаясь в линейный список. Поиск, вставка и удаление в таком дереве будут выполняться не за логарифмическое, а за линейное время. Вероятность вырождения весьма велика. Так, из 7 узлов можно образовать только одно полностью сбалансированное дерево, а полностью вырожденных — 64. Поэтому алгоритмы работы с ДДП часто дополняют автобалансировкой после вставки и удаления. Наиболее употребительны следующие схемы - АВЛ-дерево, RB-дерево, 2-3-дерево.