Меню

Структура даних дерева та купи AVL у C ++

avl tree heap data structure c

Спробуйте Наш Інструмент Для Усунення Проблем

Цей посібник містить детальне пояснення дерев AVL та структури даних купи в C ++, а також приклади дерева AVL для кращого розуміння:

Дерево AVL - це бінарне дерево із збалансованою висотою. Кожен вузол асоціюється із збалансованим коефіцієнтом, який обчислюється як різниця між висотою його лівого піддерева та правого піддерева.

Дерево AVL названо на честь двох його винахідників, тобто Г.М. Abelson-Velvety та E.M. Landis, і була опублікована в 1962 р. У статті «Алгоритм організації інформації».

=> Шукайте тут цілу серію навчальних програм C ++.

Дерева AVL та структура даних купи в C ++

Що ви дізнаєтесь:

Дерево AVL в C ++

Щоб дерево було збалансованим, збалансований коефіцієнт для кожного вузла повинен бути від -1 до 1. Якщо це не так, дерево стане незбалансованим.

Приклад дерева AVL показано нижче.

Приклад дерева AVL

У наведеному вище дереві ми можемо помітити, що різниця у висоті лівого та правого піддерев становить 1. Це означає, що це збалансована BST. Оскільки коефіцієнт балансування дорівнює 1, це означає, що ліве піддерево на один рівень вище, ніж праве піддерево.

Якщо коефіцієнт балансування дорівнює 0, то це означає, що ліве та праве піддерева знаходяться на одному рівні, тобто вони містять однакову висоту. Якщо коефіцієнт балансування дорівнює -1, то ліве піддерево на один рівень нижче, ніж праве піддерево.

Дерево AVL контролює висоту бінарного дерева пошуку і запобігає його перекосу. Оскільки, коли бінарне дерево стає перекошеним, це найгірший випадок (O (n)) для всіх операцій. Використовуючи коефіцієнт балансу, дерево AVL накладає обмеження на бінарне дерево і, таким чином, зберігає всі операції на рівні O (log n).

Операції дерева AVL

Нижче наведено операції, підтримувані деревами AVL.

# 1) Вставка дерева AVL

Операція вставки в дереві AVL C ++ така ж, як і у бінарного дерева пошуку. Єдина відмінність полягає в тому, що для того, щоб підтримувати коефіцієнт балансу, нам потрібно повертати дерево вліво або вправо, щоб воно не стало незбалансованим.

# 2) Видалення дерева AVL

Операція видалення також виконується так само, як операція видалення в двійковому дереві пошуку. Знову нам потрібно збалансувати дерево, виконавши деякі обертання дерева AVL.

Впровадження дерева AVL

Далі наведена програма C ++ для демонстрації дерева AVL та його операцій.

// C++ program for AVL Tree #include using namespace std; // An AVL tree node class AVLNode { public: int key; AVLNode *left; AVLNode *right; int depth; }; //get max of two integers int max(int a, int b){ return (a > b)? a : b; } //function to get height of the tree int depth(AVLNode *n) { if (n == NULL) return 0; return n->depth; } // allocate a new node with key passed AVLNode* newNode(int key) { AVLNode* node = new AVLNode(); node->key = key; node->left = NULL; node->right = NULL; node->depth = 1; // new node added as leaf return(node); } // right rotate the sub tree rooted with y AVLNode *rightRotate(AVLNode *y) { AVLNode *x = y->left; AVLNode *T2 = x->right; // Perform rotation x->right = y; y->left = T2; // Update heights y->depth = max(depth(y->left), depth(y->right)) + 1; x->depth = max(depth(x->left), depth(x->right)) + 1; // Return new root return x; } // left rotate the sub tree rooted with x AVLNode *leftRotate(AVLNode *x) { AVLNode *y = x->right; AVLNode *T2 = y->left; // Perform rotation y->left = x; x->right = T2; // Update heights x->depth = max(depth(x->left), depth(x->right)) + 1; y->depth = max(depth(y->left), depth(y->right)) + 1; // Return new root return y; } // Get Balance factor of node N int getBalance(AVLNode *N) { if (N == NULL) return 0; return depth(N->left) - depth(N->right); } //insertion operation for node in AVL tree AVLNode* insert(AVLNode* node, int key) { //normal BST rotation if (node == NULL) return(newNode(key)); if (key key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); else // Equal keys not allowed return node; //update height of ancestor node node->depth = 1 + max(depth(node->left), depth(node->right)); int balance = getBalance(node); //get balance factor // rotate if unbalanced // Left Left Case if (balance > 1 && key left->key) return rightRotate(node); // Right Right Case if (balance node->right->key) return leftRotate(node); // Left Right Case if (balance > 1 && key > node->left->key) { node->left = leftRotate(node->left); return rightRotate(node); } // Right Left Case if (balance <-1 && key right->key) { node->right = rightRotate(node->right); return leftRotate(node); } return node; } // find the node with minimum value AVLNode * minValueNode(AVLNode* node) { AVLNode* current = node; // find the leftmost leaf */ while (current->left != NULL) current = current->left; return current; } // delete a node from AVL tree with the given key AVLNode* deleteNode(AVLNode* root, int key) { if (root == NULL) return root; //perform BST delete if ( key key ) root->left = deleteNode(root->left, key); else if( key > root->key ) root->right = deleteNode(root->right, key); else { // node with only one child or no child if( (root->left == NULL) || (root->right == NULL) ) { AVLNode *temp = root->left ? root->left : root->right; if (temp == NULL) { temp = root; root = NULL; } else // One child case *root = *temp; free(temp); } else { AVLNode* temp = minValueNode(root->right); root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); } } if (root == NULL) return root; // update depth root->depth = 1 + max(depth(root->left), depth(root->right)); // get balance factor int balance = getBalance(root); //rotate the tree if unbalanced // Left Left Case if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root); // Left Right Case if (balance > 1 && getBalance(root->left) left = leftRotate(root->left); return rightRotate(root); } // Right Right Case if (balance right) <= 0) return leftRotate(root); // Right Left Case if (balance right)> 0) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } // prints inOrder traversal of the AVL tree void inOrder(AVLNode *root) { if(root != NULL) { inOrder(root->left); cout

Вихід:

Обхідним переходом для дерева AVL є:

4 5 8 11 12 17 18

Обхід в обробці після видалення вузла 5:

4 8 11 12 17 18

Вихід AVL

Зверніть увагу, що ми використовували приклад дерева, показаний вище, для демонстрації дерева AVL у програмі.

Застосування дерев AVL

  1. Дерева AVL в основному використовуються для наборів пам’яті та словників.
  2. Дерева AVL також широко використовуються в додатках баз даних, в яких вставки та видалення менше, але часто потрібно шукати дані.
  3. Він використовується в додатках, які потребують поліпшеного пошуку, крім додатків баз даних .

Структура даних HEAP на C ++

Купа в C ++ - це спеціальна структура даних на основі дерева і є повним бінарним деревом.

Купи можуть бути двох типів:

  • Мінімальна купа : У min-heap найменшим елементом є корінь дерева, і кожен вузол більше або дорівнює своєму батьківському.
  • Макс-купа : У max-heap найбільшим елементом є корінь дерева, і кожен вузол менше або дорівнює своєму батьківському елементу.

Розглянемо наступний масив елементів:

10 20 30 40 50 60 70

Мінімальна купа для наведених даних представлена ​​нижче:

хв-купа

найкращий диспетчер завдань для Windows 10 -

Максимальна купа, використовуючи наведені вище дані, показана нижче:

максимальна купа

Двійкова купа C ++

Бінарний куп - це загальна реалізація структури даних купи.

Бінарний купи має такі властивості:

  • Це повне двійкове дерево, коли всі рівні заповнені повністю, за винятком, можливо, останнього рівня, а ключі останнього рівня мають якомога більше лівих.
  • Двійкова купа може бути міні-купою або максимальною купою.

Бінарний куп - це повне бінарне дерево, і тому його найкраще представити у вигляді масиву.

Як знайти ключ безпеки мережі на маршрутизаторі -

Давайте розглянемо представлення масиву двійкової купи.

Розглянемо наступну двійкову купу.

двійкова купа

На наведеній вище діаграмі обхід бінарної купи називається порядком рівня.

Таким чином, масив для вищезазначеної двійкової купи показано нижче як HeapArr:

HeapArr

Як показано вище, HeapArr (0) є коренем двійкової купи. Інші елементи ми можемо представити в загальних рисах наступним чином:

Якщо HeapArr (i) - це iговузол у двійковій купі, потім індекси інших вузлів з iгоВузол:

  • HeapArr ((i-1) / 2) => Повертає батьківський вузол.
  • HeapArr ((2 * i) +1) => Повертає лівий дочірній вузол.
  • HeapArr ((2 * i) +2) => Повертає правий дочірній вузол.

Бінарна купа задовольняє властивість упорядкування, яка має два типи, як зазначено нижче:

  • Властивість Min Heap: Мінімальне значення знаходиться в корені, і значення кожного вузла більше або дорівнює його батьківському.
  • Властивість Max Heap: Максимальне значення знаходиться в корені, і значення кожного вузла менше або дорівнює його батьківському.

Операції на двійковій купі

Нижче наведено основні операції, які виконуються на мінімальній купі. У випадку максимального купи операції відповідно обертаються.

# 1) Вставити () - Вставляє новий ключ у кінці дерева. Залежно від значення вставленого ключа, нам, можливо, доведеться відрегулювати купу, не порушуючи властивість купи.

# 2) Видалити () - Видаляє ключ. Примітка що часова складність операцій вставки та видалення купи становить O (log n).

# 3) reduceKey () - Зменшує значення ключа. Можливо, нам доведеться підтримувати властивість купи, коли ця операція відбувається. Складність у часі зменшенняКлючова робота кучі також становить O (log n).

# 4) extractMin () - Видаляє мінімальний елемент з min-heap. Він повинен підтримувати властивість купи після видалення мінімального елемента. Таким чином, його часова складність дорівнює O (log n).

# 5) getMin () - Повертає кореневий елемент min-heap. Це найпростіша операція, і складність часу для цієї операції становить O (1).

Впровадження структури даних купи

Нижче наведено реалізацію C ++ для демонстрації основних функціональних можливостей min-heap.

#include #include using namespace std; // swap two integers void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp; } // Min-heap class class Min_Heap { int *heaparr; // pointer to array of elements in heap int capacity; // maximum capacity of min heap int heap_size; // current heap size public: Min_Heap(int cap){ heap_size = 0; capacity = cap; heaparr = new int(capacity); } // to heapify a subtree with the root at given index void MinHeapify(int ); int parent(int i) { return (i-1)/2; } // left child of node i int left(int i) { return (2*i + 1); } // right child of node i int right(int i) { return (2*i + 2); } // extract minimum element in the heap(root of the heap) int extractMin(); // decrease key value to newKey at i void decreaseKey(int i, int newKey); // returns root of the min heap int getMin() { return heaparr(0); } // Deletes a key at i void deleteKey(int i); // Inserts a new key 'key' void insertKey(int key); void displayHeap(){ for(int i = 0;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); } // Store the minimum value,delete it from heap 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); } } // main program 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: '<

Вихід:

Купи після вставки: 2 4 6 8 10 12

корінь купи: 2

Купи після клавіші видалення (2): 2 4 12 8 10

мінімальний елемент у купі: 2

новий корінь купи після зменшенняКлюч: 1

Висновок купи

Застосування купи

  • Теплий сорт: Алгоритм 'Хепсорт' ефективно реалізований за допомогою двійкової купи.
  • Черги пріоритетів: Бінарна купа підтримує всі операції, необхідні для успішної реалізації пріоритетних черг за час O (log n).
  • Графічні алгоритми: Деякі алгоритми, пов'язані з графіками, використовують чергу пріоритетів, і в свою чергу, черга пріоритетів використовує двійкову купу.
  • Найгіршу складність алгоритму швидкого сортування можна подолати, використовуючи сортування купи.

Висновок

У цьому підручнику ми побачили дві структури даних, тобто дерева AVL та сортування купи детально.

Дерева AVL - це збалансовані двійкові дерева, які в основному використовуються для індексації баз даних.

Всі операції, що виконуються над деревами AVL, подібні до операцій бінарних дерев пошуку, але єдина відмінність у випадку дерев AVL полягає в тому, що нам потрібно підтримувати коефіцієнт балансу, тобто структура даних повинна залишатися збалансованим деревом в результаті різних операцій. Це досягається за допомогою операції обертання дерева AVL.

Купи - це повна двійкова структура дерев, яка класифікується на min-heap або max-heap. Корінь Min-heap має мінімальний елемент, а наступні вузли більше або дорівнюють їхньому батьківському вузлу. У max-heap ситуація прямо протилежна, тобто максимальний елемент - це корінь купи.

Купи можуть бути представлені у вигляді масивів з 0гоелемент як корінь дерева. Структури даних купи в основному використовуються для реалізації черг сортування та пріоритету купи.

=> Завітайте сюди, щоб вивчити C ++ з нуля.

Рекомендована література

^