7. Хеширование при хранении и поиске данных. Возникновение и разрешение коллизий.

Хеширование - одностороннее преобразование данных в целое число (hash). Структура данных, использующая хеширование, называется hash map (хеш-таблица). В ней хеш используется в качестве индекса для словаря.

Если несколько элементов имеют одинаковый хеш, возникает коллизия. Решить коллизию можно представив элемент в виде линейного списка

8. Представления и реализации бинарных деревьев, обходы бинарных деревьев.

Бинарные деревья похожи на линейные списки. Элементы бинарных деревьев хранят в себе значение, а также 2 ссылки (left and right).

Существует 3 варианта обхода деревьев:

1. прямой обход: корень -> левое поддерево -> правое поддерево

2. центрированный обход -> левое поддерево -> корень -> правое поддерево

3. обратный обход: левое поддерево -> правое поддерево -> корень

реализация (псевдокод):

struct TreeNode {

int value;

TreeNode* left;

TreeNode* right;

}

void print_tree_direct(TreeNode* root) {

if(root == nullptr) return;

print_tree_direct(root->left);

std::cout << root->value;

print_tree_direct(root->right);

}

void print_tree_center(TreeNode* root) {

if(root == nullptr) return;

std::cout << root->value;

print_tree_center(root->left);

print_tree_center(root->right);

}

void print_tree_inverse(TreeNode* root) {

if(root == nullptr) return;

print_tree_inverse(root->left);

print_tree_inverse(root->right);

std::cout << root->value;

}

9. Бинарные деревья поиска.

Бинарное дерево поиска (англ. binary search tree, BST) — структура данных для работы с упорядоченными множествами.

Бинарное дерево поиска обладает следующим свойством: если x— узел бинарного дерева с ключом k, то все узлы в левом поддереве должны иметь ключи, меньшие k, а в правом поддереве большие k.

10. Алгоритмы построения идеально сбалансированного дерева. Алгоритм построения лозы бинарного дерева.

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

Алгоритм построения идеально сбалансированного дерева очень прост: 1. элемент посередине ставим в корень. Левая часть массива становится левым поддеревом, правая часть массива становится правым поддеревом.

2. Для каждого непустого поддерева выполняем операцию 1.

Если нам нужно, чтобы дерево было бинарным, предварительно отсортируй массив по возрастанию.

Лоза - бинарное дерево, в котором отсутствуют либо только левые поддеревья, либо только правые поддеревья.Иначе говоря, Лоза - бинарное дерево, которое выглядит как линейный список.

Создать с нуля лозу достаточно просто. Однако создать лозу из обычного бинарного дерева сложнее, ведь для этого требуется многократно применять обратные операции поворота дерева (см. вопрос 11 про АВЛ деревья)

11. АВЛ-деревья.

https://ru.wikipedia.org/wiki/АВЛ-дерево

АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ — аббревиатура, образованная первыми буквами создателей (советских учёных) Адельсон-Вельского Георгия Максимовича и Ландиса Евгения Михайловича.

Балансировка АВЛ дерева осуществляется с помощью вращений:

1. малое левое вращение - когда разница высот L-поддерева и b-поддерева равна 2 и высота С <= высота R.

2. большое левое вращение - когда разница высот L-поддерева и b-поддерева равна 2 и высота c-поддерева > высота R.

3. малое правое вращение - когда разница высот R-поддерева и b-поддерева равна 2 и высота С <= высота L.

4. большое правое вращение - когда разница высот R-поддерева и b-поддерева равна 2 и высота c-поддерева > высота L.

каждое такое вращение уменьшает полную высоту не более чем на один.

Добавление элемента - сложность O(log(n))

1. проходим дерево и ищем элемент

2. если элемента нет, добавляем.

3. отступаем назад до корня. Балансируем при необходимости

Удаление элемента - сложность O(log(n))

1. удаляем элемент из дерева

2. отступаем назад до корня. Балансируем при необходимости.

12. В-деревья. Сильноветвящееся (т.е. не бинарное) сбалансированное дерево поиска. Используется если необходимо уменьшить количество операций чтения каждого элемента. Это полезно, если данных становится настолько много, что для их хранения не хватает оперативной памяти и вместо нее используется жесткий диск. Уменьшение операций достигается увеличением количества ветвей дерева.

class BTreeNode {