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

Бинарные деревья поиска Лекция 7 АТД «Словарь» (dictionary) ▪ Словарь (dictionary) – структура данных для хранения пар вида «ключ» – «значение» (key – value) ▪ Альтернативные название – ассоциативный массив (associative array, map) ▪ В словаре может быть только одна пара с заданным ключом Ключ (key) Значение (value) 890 Слон 1200 Кит 260 Лев 530 Жираф 2 АТД «Словарь» (dictionary) Операция Описание Add(map, key, value) Добавляет в словарь map пару (key, value) Lookup(map, key) Возвращает из словаря map значение ассоциированное с ключом key Remove(map, key) Удаляет из словаря map пару с ключом key Min(map) Возвращает из словаря map минимальное значение Max(map) Возвращает из словаря map максимальное значение 3 Реализация АТД «Словарь» ▪ Реализации словарей отличаются вычислительной сложностью операций и объемом требуемой памяти для хранения пар «ключ-значение» ▪ Распространение получили следующие реализации: 1. Деревья поиска (Search trees) 2. Хэш-таблицы (Hash tables) 3. Списки с пропусками (Skip lists) 4. Связные списки, массивы 4 Реализация словаря на основе массива Операция Неотсортированный массив Отсортированный массив Add(map, key, value) 𝑂(1) (добавление в конец) 𝑂(𝑛) (поиск позиции) Lookup(map, key) 𝑂(𝑛) 𝑂(𝑙𝑜𝑔𝑛) (бинарный поиск) Remove(map, key) 𝑂(𝑛) (поиск элемента и перенос последнего на место удаляемого) 𝑂(𝑛) (перемещение элементов) Min(map) 𝑂(𝑛) 𝑂(1) (элемент v[1]) Max(map) 𝑂(𝑛) 𝑂(1) (элемент v[n]) 5 Реализация словаря на основе связного списка Операция Неотсортированный связный список Отсортированный связный список Add(map, key, value) 𝑂(1) (добавление в начало) 𝑂(𝑛) (поиск позиции) Lookup(map, key) 𝑂(𝑛) 𝑂(𝑛) Remove(map, key) 𝑂(𝑛) (поиск элемента) 𝑂(𝑛) (поиск элемента) Min(map) 𝑂(𝑛) 𝑂(1) Max(map) 𝑂(𝑛) 𝑂(𝑛) или 𝑂(1), если поддерживать указатель на последний элемент 6 Бинарные деревья (binary trees) ▪ Бинарное дерево (binary tree) – это дерево (структура данных), в котором каждый узел (node) имеет не более двух дочерних узлов (child nodes) Root node (корень) Depth 0 Parent node (родительский узел) Depth 1 Depth 2 Depth 3 Leaf node (лист) 7 Бинарные деревья поиска (binary search trees) ▪ Двоичное дерево поиска (binary search tree, BST) – это двоичное дерево, в котором: 1) каждый узел x (node) имеет не более двух дочерних узлов (child nodes) и содержит ключ (key) и значение (value) 2) ключи всех узлов левого поддерева узла x меньше значения его ключа 3) ключи всех узлов правого поддерева узла x больше значения его ключа Key: 530 Value: Жираф Left Right Key: 260 Value: Лев Left Right Key: 890 Value: Слон Left Right 8 Бинарные деревья поиска (binary search trees) Словарь Двоичное дерево поиска Ключ (Key) Значение (Value) 530 Жираф 260 Лев 890 Слон 1200 Кит Key: 530 Value: Жираф Left Right Key: 260 Value: Лев Left Right Key: 890 Value: Слон Left Right Key: 1200 Value: Кит Left Right 9 Бинарные деревья поиска (binary search trees) 180 Тигр 15 Барсук 9 элементов глубина (depth) = 3 высота (height) = 3 200 Лев Min 8 Лиса Max 4000 Слон 60 Волк 35 Рысь 90 Ягуар 600 Медведь ▪ Упорядоченный словарь (ordered map) – словарь, обеспечивающий перебор элементов в упорядоченной последовательности ▪ Операции Prev(key), Next(key) 10 Бинарные деревья поиска (binary search trees) 180 Тигр 9 элементов глубина (depth) = 3 высота (height) = 3 15 200 // Проход по возрастанию ключей Барсук Лев Min 8 Лиса node = Min(Map) max = Max(Map) while node 60 != max do Волк // Обработка узла node ... node = Next(node) end35while 90 Рысь Ягуар Max 4000 Слон 600 Медведь ▪ Упорядоченный словарь (ordered map) – словарь, обеспечивающий перебор элементов в упорядоченной последовательности ▪ Операции Prev(key), Next(key) 11 Бинарные деревья поиска (binary search trees) #include #include #include struct bstree { int key; char *value; }; /* Ключ */ /* Данные */ struct bstree *left; struct bstree *right; 12 Создание элемента BST struct bstree *bstree_create(int key, char *value) { struct bstree *node; } node = malloc(sizeof(*node)); if (node != NULL) { node->key = key; node->value = strdup(value); node->left = NULL; node->right = NULL; } return node; TCreate = O(1) 13 Создание элемента BST int main() { struct bstree *tree; tree = bstree_create(180, "Tiger"); return 0; } 14 Добавление элемента в BST 180 1. Добавление элемента (180, Тигр) 2. Добавление элемента (200, Лев) 3. Добавление элемента (15, Барсук) 4. Добавление элемента (60, Волк) Тигр 15 200 Барсук Лев 60 Волк Ищем листовой узел (leaf node) для вставки нового элемента 15 Добавление элемента в BST void bstree_add(struct bstree *tree, int key, char *value) { struct bstree *parent, *node; key = 210 180 if (tree == NULL) return; /* Отыскиваем листовой узел */ while (tree != NULL) { parent = tree; if (key < tree->key) { tree = tree->left; } else if (key > tree->key){ tree = tree->right; } else { return; } } Тигр 200 15 Лев Барсук 60 Волк parent 16 Добавление элемента в BST (продолжение) /* Создаем элемент и связываем с узлом */ node = bstree_create(key, value); if (key < parent->key) parent->left = node; else parent->right = node; } TAdd = O(h) ▪ При добавлении элемента необходимо спуститься от корня дерева до листа – это требует количества операций порядка высоты ℎ дерева ▪ Поиск листа – 𝑂(ℎ), создание элемента и корректировка указателей – 𝑂(1) 17 Поиск элемента в BST 1. Сравниваем ключ корневого узла с искомым. Если совпали, то элемент найден 2. Переходим к левому или правому дочернему узлу и повторяем шаг 1 180 Тигр 15 200 Барсук Лев 60 Волк Возможны рекурсивная и нерекурсивная реализации 18 Поиск элемента в BST struct bstree *bstree_lookup(struct bstree *tree, int key) key = 60 { while (tree != NULL) { 180 Тигр if (key == tree->key) { return tree; } else if (key < tree->key) { 15 200 Барсук Лев tree = tree->left; } else { 60 tree = tree->right; Волк } } tree return tree; TLookup = O(h) } 19 Поиск минимального элемента в BST 180 ▪ Минимальный элемент всегда расположен в левом поддереве корневого узла ▪ Требуется найти самого левого потомка корневого узла Тигр 15 200 Барсук Лев 60 Волк 20 Поиск минимального элемента в BST struct bstree *bstree_min(struct bstree *tree) { if (tree == NULL) return NULL; while (tree->left != NULL) tree = tree->left; return tree; } TMin = O(h) 21 Поиск максимального элемента в BST 180 ▪ Максимальный элемент всегда расположен в правом поддереве корневого узла ▪ Требуется найти самого правого потомка корневого узла Тигр 15 200 Барсук Лев 60 Волк 22 Поиск минимального элемента в BST struct bstree *bstree_max(struct bstree *tree) { 180 Тигр if (tree == NULL) return NULL; 15 while (tree->right != NULL) tree = tree->right; return tree; } 200 Барсук Лев 60 Волк TMax = O(h) 23 Пример int main() { struct bstree *tree, *node; tree = bstree_create(180, "Tiger"); bstree_add(tree, 200, "Lion"); bstree_add(tree, 60, "Wolf"); node = bstree_lookup(tree, 200); printf("Value = %s\n", node->value); node = bstree_min(tree); printf("Min: value = %s\n", node->value); return 0; } 24 Удаление элемента из BST 180 Тигр 1. Находим узел 𝑧 с заданным ключом – 𝑂(𝑛) 2. Возможны 3 ситуации: 15 o узел 𝑧 не имеет дочерних узлов o узел 𝑧 имеет 1 дочерний узел o узел 𝑧 имеет 2 дочерних узла 200 Барсук 10 Заяц Лев 60 Волк 90 Кабан 25 Удаление элемента из BST 180 Удаление узла “Лев” (случай 1) Тигр 1. Находим и удаляем узел “Лев” из памяти (free) 2. Родительский указатель (left или right) устанавливаем в значение NULL “Тигр”->right = NULL 15 200 Барсук 10 Заяц Лев 60 Волк 90 Кабан 26 Удаление элемента из BST 180 Удаление узла “Волк” (случай 2) Тигр 1. Находим узел “Волк” 15 2. Родительский указатель узла “Волк” (left или right) устанавливаем на его дочерний элемент 3. Удаляем узел “Волк” из памяти Барсук 10 Заяц “Барсук”->right = “Волк”->right 200 Лев 60 Волк 90 Кабан 27 Удаление элемента из BST 180 Тигр Удаление узла “Барсук” (случай 3) 15 1. Находим узел “Барсук” 2. Находим узел с минимальным ключом в правом поддереве узла “Барсук” – самый левый лист в поддереве (узел “Рысь”) 3. Заменяем узел “Барсук” узлом “Рысь” 200 Барсук 10 Лев 60 Заяц Волк 90 45 Кабан Рысь 55 Кабарга 70 Тапир 150 Марал 28 Удаление элемента из BST 180 180 Удаление узла “Барсук” (случай 3) Тигр 15 200 Барсук 10 Тигр Лев Заяц 60 Заяц Волк Лев Рысь 10 60 200 45 Волк 90 45 90 Кабан Рысь 55 Кабарга 70 Тапир 150 Марал Кабан 55 Кабарга 70 Тапир 150 Марал 29 Анализ эффективности BST 1 1. Операции имеют трудоемкость пропорциональную высоте ℎ дерева Value NULL 2. В худшем случае высота дерева 𝑶(𝒏) (вставка элементов в отсортированной последовательности) 2 Value NULL 3. В среднем случае высота дерева 𝑶(𝒍𝒐𝒈𝒏) bstree_add(tree, bstree_add(tree, bstree_add(tree, bstree_add(tree, “Item”, “Item”, “Item”, “Item”, 1); 2); 3); 4); Value NULL Дерево вырождается в связный список 3 4 Value 30 Реализация словаря на основе BST Операция Средний случай (average case) Худший случай (worst case) Add(map, key, value) 𝑂(𝑙𝑜𝑔𝑛) 𝑂(𝑛) Lookup(map, key) 𝑂(𝑙𝑜𝑔𝑛) 𝑂(𝑛) Remove(map, key) 𝑂(𝑙𝑜𝑔𝑛) 𝑂(𝑛) Min(map) 𝑂(𝑙𝑜𝑔𝑛) 𝑂(𝑛) Max(map) 𝑂(𝑙𝑜𝑔𝑛) 𝑂(𝑛) 31 Сбалансированные деревья поиска ▪ Сбалансированное по высоте дерево поиска (self-balancing binary search tree) – дерево поиска, в котором высоты поддеревьев узла различаются не более чем на заданную константу k ▪ Баланс высоты поддерживается при выполнении операций добавления и удаления элементов ▪ Типы сбалансированных деревьев поиска: Красно-черные деревья (Red-black tree): ℎ ≤ 2 log 2 (𝑛 + 1) АВЛ-деревья (AVL-tree): ℎ < 1.4405 ∙ log 2 (𝑛 + 2) − 0.3277 B-деревья Все операции на красно-черном дереве и АВЛ-дереве Деревья Ван Эмде Боаса в худшем случае выполняются за время 𝑂(𝑙𝑜𝑔𝑛) … 32 Литература ▪ [DSABook, Глава 9] ▪ Керниган Б.У., Пайк Р. Практика программирования. – М.: Вильямс, 2004. [С. 67] «2.8 Деревья» ▪ Прочитать в [CLRS, С. 328] раздел об удалении узла из бинарного дерева поиска (функции Tree-Delete, Transplant) ▪ Прочитать про обходы дерева в глубину (pre-order, in-order и post-order) ▪ Как освободить память, выделенную для всего дерева, зная указатель на корень? 33