Дерево AVL — это бинарное дерево, сбалансированное по высоте. Каждый узел связан со сбалансированным коэффициентом, который вычисляется как разница между высотой его левого поддерева и правого поддерева.
Дерево AVL названо в честь двух его изобретателей Абельсона-Велвети и Лэндиса в 1962 году, и опубликовано в их статье “Алгоритм организации информации”.
Дерево AVL
Чтобы дерево было сбалансированным, коэффициент сбалансированности для каждого узла должен составлять от -1 до 1. В противном случае дерево станет несбалансированным.
Пример дерева AVL показан ниже:
В приведенной выше схеме дерева можно заметить, что разница в высотах левого и правого поддеревьев равна 1. Это означает, что он сбалансированный по BST. Поскольку коэффициент балансировки равен 1, это означает, что левое поддерево на один уровень выше, чем правое поддерево.
Если коэффициент балансировки равен 0, то это означает, что левое и правое поддеревья находятся на одном уровне, т.е., они имеют одинаковую высоту. Если коэффициент балансировки равен -1, то левое поддерево будет на один уровень ниже правого поддерева.
Дерево AVL управляет высотой бинарного дерева поиска и предотвращает его перекос. Когда бинарное дерево становится искаженным, это наихудший случай (O (n)) для всех операций. Используя коэффициент баланса, дерево AVL накладывает ограничение на бинарное (двоичное) дерево и, таким образом, сохраняет все операции в O (log n).
Операции с деревом AVL
Ниже приведены операции, поддерживаемые деревом AVL:
1) Вставка
Операция вставки в дереве AVL на C++ такая же, как и в бинарном дереве поиска. Единственное отличие состоит в том, что для поддержания коэффициента баланса нам нужно повернуть дерево влево или вправо, чтобы оно не стало несбалансированным.
2) Удаление
Операция удаления выполняется также, как операция удаления в бинарном дереве поиска. И снова нам нужно перебалансировать дерево, выполнив несколько поворотов дерева AVL.
Реализация дерева AVL
Ниже приведена программа на C++ для демонстрации дерева AVL и его операций:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 |
// Программа на C++ для дерева AVL #include<iostream> using namespace std; // Узел дерева AVL class AVLNode { public: int key; AVLNode *left; AVLNode *right; int depth; }; //получить максимум два целых числа int max(int a, int b){ return (a > b)? a : b; } //функция для получения высоты дерева int depth(AVLNode *n) { if (n == NULL) return 0; return n->depth; } // выделите новый узел с переданным ключом AVLNode* newNode(int key) { AVLNode* node = new AVLNode(); node->key = key; node->left = NULL; node->right = NULL; node->depth = 1; // новый узел добавлен как лист return(node); } // поверните вправо поддерево с корнем y AVLNode *rightRotate(AVLNode *y) { AVLNode *x = y->left; AVLNode *T2 = x->right; // Выполнить вращение x->right = y; y->left = T2; // Высоты обновления y->depth = max(depth(y->left), depth(y->right)) + 1; x->depth = max(depth(x->left), depth(x->right)) + 1; // Вернуть новый корень return x; } // поворот влево дочернего дерева с корнем x AVLNode *leftRotate(AVLNode *x) { AVLNode *y = x->right; AVLNode *T2 = y->left; // Выполнить вращение y->left = x; x->right = T2; // Высоты обновления x->depth = max(depth(x->left), depth(x->right)) + 1; y->depth = max(depth(y->left), depth(y->right)) + 1; // Вернуть новый корень return y; } // Получить коэффициент баланса узла N int getBalance(AVLNode *N) { if (N == NULL) return 0; return depth(N->left) - depth(N->right); } //операция вставки для узла в дереве AVL AVLNode* insert(AVLNode* node, int key) { //вращение по BST if (node == NULL) return(newNode(key)); if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); else // Одинаковые ключи не допускаются return node; //обновить высоту узла-предка node->depth = 1 + max(depth(node->left), depth(node->right)); int balance = getBalance(node); //получить коэффициент баланса // вращать, если несбалансирован // Лево лево if (balance > 1 && key < node->left->key) return rightRotate(node); // Право право if (balance < -1 && key > node->right->key) return leftRotate(node); // Лево право if (balance > 1 && key > node->left->key) { node->left = leftRotate(node->left); return rightRotate(node); } // Право лево if (balance < -1 && key < node->right->key) { node->right = rightRotate(node->right); return leftRotate(node); } return node; } // найти узел с минимальным значением AVLNode * minValueNode(AVLNode* node) { AVLNode* current = node; // найти крайний левый лист */ while (current->left != NULL) current = current->left; return current; } // удалить узел из дерева AVL с заданным ключом AVLNode* deleteNode(AVLNode* root, int key) { if (root == NULL) return root; //удалить по BST if ( key < root->key ) root->left = deleteNode(root->left, key); else if( key > root->key ) root->right = deleteNode(root->right, key); else { // узел только с одним дочерним элементом или без дочернего элемента if( (root->left == NULL) || (root->right == NULL) ) { AVLNode *temp = root->left ? root->left : root->right; if (temp == NULL) { temp = root; root = NULL; } else *root = *temp; free(temp); } else { AVLNode* temp = minValueNode(root->right); root->key = temp->key; // Удалить преемника по порядку root->right = deleteNode(root->right, temp->key); } } if (root == NULL) return root; // глубина обновления root->depth = 1 + max(depth(root->left), depth(root->right)); // получить коэффициент баланса int balance = getBalance(root); //повернуть дерево, если оно несбалансировано // Лево лево if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root); // Лево право if (balance > 1 && getBalance(root->left) < 0) { root->left = leftRotate(root->left); return rightRotate(root); } // Право право if (balance < -1 && getBalance(root->right) <= 0) return leftRotate(root); // Право лево if (balance < -1 && getBalance(root->right) > 0) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } // печатает обход дерева AVL по порядку void inOrder(AVLNode *root) { if(root != NULL) { inOrder(root->left); cout << root->key << " "; inOrder(root->right); } } // основной код int main() { AVLNode *root = NULL; // построение дерева AVL root = insert(root, 12); root = insert(root, 8); root = insert(root, 18); root = insert(root, 5); root = insert(root, 11); root = insert(root, 17); root = insert(root, 4); //Обход по порядку для вышеуказанного дерева : 4 5 8 11 12 17 18 cout << "Inorder traversal for the AVL tree is: \n"; inOrder(root); root = deleteNode(root, 5); cout << "\nInorder traversal after deletion of node 5: \n"; inOrder(root); return 0; } |
Вывод данных:
| Порядок обхода для дерева AVL является: 4 5 8 11 12 17 18 Обход по порядку после удаления узла 5: 4 8 11 12 17 18 |
Применения дерева AVL
- Дерево AVL в основном используются для типов наборов и словарей в памяти.
- Дерево AVL также широко используются в приложениях баз данных, в которых меньше вставок и удалений, но есть частые запросы на требуемые данные.
- Дерево AVL используется в приложениях, требующих улучшенного поиска, помимо приложений базы данных.
Структура данных кучи
Куча в C++ — это специальная древовидная структура данных, представляющая собой полное бинарное дерево.
Кучи могут быть двух типов:
- Минимальная куча: в min-heap наименьшим элементом является корень дерева, и каждый узел больше или равен его родительскому элементу.
- Максимальная куча: в max-heap самым большим элементом является корень дерева, и каждый узел меньше или равен его родительскому элементу.
Рассмотрим следующий массив элементов:
| 10 20 30 40 50 60 70 |
Минимальная куча для вышеуказанных данных представлена ниже:
Максимальная куча, использующая вышеуказанные данные, показана ниже:
Бинарная куча в C++
Бинарная куча — это обычная реализация структуры данных кучи.
Бинарная куча обладает следующими свойствами:
- Полное бинарное дерево — это когда все уровни полностью заполнены, за исключением, возможно, последнего уровня, и на последнем уровне осталось как можно больше ключей.
- Бинарная куча может быть минимальной или максимальной кучей.
- Бинарная куча — это полное двоичное дерево, и поэтому ее лучше всего представить в виде массива.
Давайте рассмотрим представление массива бинарной кучи:
На приведенной выше схеме обход для бинарной кучи называется порядком уровней.
Массив для вышеупомянутой бинарной кучи (Heap Arr) показан ниже:
Как показано выше, HeapArr[0] является корнем бинарной кучи. Мы можем представить другие элементы в общих чертах следующим образом:
Если HeapArr[i] является i-м узлом в бинарной куче, то индексы других узлов из i-го узла равны:
- HeapArr [(i-1)/2] => Возвращает родительский узел.
- HeapArr [(2*i)+1] => Возвращает левый дочерний узел.
- HeapArr [(2*i)+2] => Возвращает правый дочерний узел.
Бинарная куча удовлетворяет “свойству упорядочения”, которое бывает двух типов, как указано ниже:
- Свойство минимальной кучи: минимальное значение находится в корне, а значение каждого узла больше или равно его родительскому.
- Свойство максимальной кучи: максимальное значение находится в корне, а значение каждого узла меньше или равно его родительскому.
Операции с бинарной кучей
Ниже приведены основные операции, которые выполняются с минимальной кучей. В случае максимальной кучи операции меняются соответственно.
1) Insert() – вставляет новый ключ в конец дерева. В зависимости от значения вставленного ключа нам, возможно, придется настроить кучу, не нарушая свойство кучи.
2) Delete() – удаляет ключ. Обратите внимание, что временная сложность операций вставки и удаления кучи равна O (log n).
3) DecreaseKey() – уменьшает значение ключа. Возможно, нам потребуется поддерживать свойство кучи, когда выполняется эта операция. Временная сложность операции DecreaseKey кучи также равна O (log n).
4) extractMin() – удаляет минимальный элемент из минимальной кучи. Он должен поддерживать свойство кучи после удаления минимального элемента. Таким образом, его временная сложность равна O (log n).
5) getMin() – возвращает корневой элемент минимальной кучи. Это самая простая операция, и временная сложность для этой операции равна O (1).
Реализация структуры данных кучи
Ниже приведена реализация на C++ для демонстрации базовой функциональности min-heap:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
#include<iostream> #include<climits> using namespace std; // поменять местами два целых числа void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp; } // Класс мin-heap class Min_Heap { int *heaparr; // указатель на массив элементов в куче int capacity; // максимальная вместимость минимальной кучи int heap_size; // текущий размер кучи public: Min_Heap(int cap){ heap_size = 0; capacity = cap; heaparr = new int[capacity]; } // чтобы создать поддерево с корнем по заданному индексу void MinHeapify(int ); int parent(int i) { return (i-1)/2; } // левый потомок узла i int left(int i) { return (2*i + 1); } // правый потомок узла i int right(int i) { return (2*i + 2); } // извлечение минимального элемента в куче (корень кучи) int extractMin(); // уменьшите значение ключа до newKey при i void decreaseKey(int i, int newKey); // возвращает корень минимальной кучи int getMin() { return heaparr[0]; } // Удаляет ключ в точке i void deleteKey(int i); // Вставляет новый ключ 'key' void insertKey(int key); void displayHeap(){ for(int i = 0;i<heap_size;i++) cout<<heaparr[i]<<" "; cout<<endl; } }; // Вставляет новый ключ 'key' void Min_Heap::insertKey(int key) { if (heap_size == capacity) { cout << "\nOverflow: Could not insertKey\n"; return; } // Сначала вставьте новый ключ в конце heap_size++; int i = heap_size - 1; heaparr[i] = key; // Исправьте свойство минимальной кучи, если оно нарушено while (i != 0 && heaparr[parent(i)] > heaparr[i]) { swap(&heaparr[i], &heaparr[parent(i)]); i = parent(i); } } void Min_Heap::decreaseKey(int i, int newKey) { heaparr[i] = newKey; while (i != 0 && heaparr[parent(i)] > heaparr[i]) { swap(&heaparr[i], &heaparr[parent(i)]); i = parent(i); } } int Min_Heap::extractMin() { if (heap_size <= 0) return INT_MAX; if (heap_size == 1) { heap_size--; return heaparr[0]; } // Сохраните минимальное значение, удалите его из кучи int root = heaparr[0]; heaparr[0] = heaparr[heap_size-1]; heap_size--; MinHeapify(0); return root; } void Min_Heap::deleteKey(int i) { decreaseKey(i, INT_MIN); extractMin(); } void Min_Heap::MinHeapify(int i) { int l = left(i); int r = right(i); int min = i; if (l < heap_size && heaparr[l] < heaparr[i]) min = l; if (r < heap_size && heaparr[r] < heaparr[min]) min = r; if (min != i) { swap(&heaparr[i], &heaparr[min]); MinHeapify(min); } } // основная программа int main() { Min_Heap h(11); h.insertKey(2); h.insertKey(4); h.insertKey(6); h.insertKey(8); h.insertKey(10); h.insertKey(12); cout<<"Heap after insertion:"; h.displayHeap(); cout<<"root of the heap: "<<h.getMin()<<endl; h.deleteKey(2); cout<<"Heap after deletekey(2):"; h.displayHeap(); cout <<"minimum element in the heap: "<< h.extractMin() <<endl; h.decreaseKey(1, 1); cout <<"new root of the heap after decreaseKey: "<< h.getMin()<<endl; return 0; } |
Вывод данных:
| Куча после вставки: 2 4 6 8 10 12 Корень кучи: 2 Куча после deletekey(2): 2 4 12 8 10 Минимальный элемент в куче: 2 Новый корень кучи после DecreaseKey: 1 |
Применение кучи
- Кучная сортировка: алгоритм сортировки кучи эффективно реализуется с использованием бинарной кучи.
- Очереди приоритетов: бинарная куча поддерживает все операции, необходимые для успешной реализации очередей приоритетов за O (log n) время.
- Алгоритмы графов: некоторые алгоритмы, связанные с графами, используют приоритетную очередь, а приоритетная очередь, в свою очередь, использует бинарную кучу.
- Сложность алгоритма быстрой сортировки в наихудшем случае может быть преодолена с помощью сортировки кучи.
Итог
Деревья AVL — это сбалансированные бинарные деревья, которые в основном используются для индексации базы данных.
Все операции, выполняемые с деревьями AVL, аналогичны операциям с бинарными деревьями поиска, но единственное отличие в случае деревьев AVL заключается в том, что нам нужно поддерживать коэффициент баланса, т.е. структура данных должна оставаться сбалансированным деревом в результате различных операций. Это достигается с помощью операции поворота дерева AVL.
Кучи — это полные бинарные древовидные структуры, которые классифицируются на минимальную кучу или максимальную кучу. Минимальная куча имеет минимальный элемент в качестве своего корня, а последующие узлы больше или равны их родительскому узлу. В максимальной куче ситуация прямо противоположна, т.е. максимальный элемент является корнем кучи.
Кучи могут быть представлены в виде массивов с 0-м элементом в качестве корня дерева. Структуры данных кучи в основном используются для реализации сортировки кучи и очередей приоритетов.
В следующей статье мы с вами поговорим о реализации графов в C++.
С Уважением, МониторБанк