Множества

Множества, графы

Бинарное дерево

Бинарное дерево - такое дерево, каждый узел которого содержит не более двух поддеревьев, которые называют соответственно левое и правое поддерево. Такое дерево ещё называют двоичным деревом поиска.

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

struct BinNode

{

BinNode *left_child, *right_child;

};

struct BinTree { BinNode *root};

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

Поиск в таком дереве происходит по аналогичному алгоритму.

Рассмотрим пример. Пусть были добавлены объекты со следующими ключами: 7, 4, 2, 12, 8, 6, 5, 9. "7" помещается в корень. Так как 4<7, соответствующий узел добавляется в левое поддерево. Так как 2<4, "2" помещается в левое поддерево узла "4". Так как 12>7, "12" помещается в правое поддерево узла "7". "8" Будет помещено в левое поддерево узла "12", "6" – в правое поддерево "4", "5" – в левое поддерево "6", "9" – в правое поддерево "8".

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

Наиболее распространены два способа реализации множеств:

а) на основе бинарного дерева;

б) если размер множества ограничен, то наилучшим решением будет использование массива битов, в котором 1 соответствует присутствию элемента со значением, соответствующим номеру бита в массиве; в этом случае сложность вставки, удаления и поиска o(1), а расходы памяти составляют N/8 байт.

class BitSet

{

protected:

char data[1024]; //всего 8192 элемента

// можно использовать динамический вектор вместо статического

public:

BitSet() {memset(data,0,1024);} // «Опустошение» множества

void set(int n) //добавить элемент №n в множество

{

if (n<0 || n>8192) return;

data[n/8] |= (1<<(n%8)); // n/8 — номер байта, n%8 — номер бита

}

void unset(int n) //удалить из множества

{

if (n<0 || n>8192) return;

data[n/8] &= ~(1<<(n%8));

}

bool get(int n) //проверить принадлежность

{

if (n<0 || n>8192) return false;

return data[n/8]&(1<<(n%8))!=0;

}

};