avl tree heap data structure c
Acest tutorial oferă o explicație detaliată a arborilor AVL și a structurii datelor Heap în C ++, împreună cu exemplele arborelui AVL pentru o mai bună înțelegere:
AVL Tree este un arbore binar echilibrat în înălțime. Fiecare nod este asociat cu un factor echilibrat care se calculează ca diferență între înălțimea subarborelui său stâng și subarborele drept.
Arborele AVL este numit după cei doi inventatori ai săi, adică G.M. Abelson-Velvety și E.M. Landis și a fost publicat în 1962 în lucrarea lor „Un algoritm pentru organizarea informațiilor”.
=> Căutați întreaga serie de formare C ++ aici.
Ce veți învăța:
Arborele AVL în C ++
Pentru ca arborele să fie echilibrat, factorul echilibrat pentru fiecare nod ar trebui să fie între -1 și 1. Dacă nu arborele va deveni dezechilibrat.
Un exemplu AVL Tree este prezentat mai jos.
În arborele de mai sus, putem observa că diferența de înălțime a subarborilor din stânga și din dreapta este 1. Aceasta înseamnă că este un BST echilibrat. Deoarece factorul de echilibrare este 1, aceasta înseamnă că subarborele din stânga este cu un nivel mai mare decât subarborele din dreapta.
Dacă factorul de echilibrare este 0, atunci înseamnă că subarborii din stânga și din dreapta sunt la același nivel, adică conțin înălțime egală. Dacă factorul de echilibrare este -1, atunci subarborele din stânga este cu un nivel mai mic decât subarborele din dreapta.
Arborele AVL controlează înălțimea unui arbore de căutare binar și îl împiedică să se îndoiască. Deoarece atunci când un arbore binar devine înclinat, acesta este cel mai rău caz (O (n)) pentru toate operațiile. Prin utilizarea factorului de echilibru, arborele AVL impune o limită arborelui binar și astfel păstrează toate operațiunile la O (log n).
Operații AVL Tree
Următoarele sunt operațiile acceptate de arborii AVL.
# 1) Inserarea arborelui AVL
Operația de inserare în arborele C ++ AVL este aceeași cu cea a arborelui de căutare binară. Singura diferență este că, pentru a menține factorul de echilibru, trebuie să rotim arborele la stânga sau la dreapta, astfel încât să nu devină dezechilibrat.
# 2) Ștergerea arborelui AVL
Operația de ștergere se efectuează, de asemenea, în același mod ca și operația de ștergere într-un arbore de căutare binară. Din nou, trebuie să reechilibrăm arborele efectuând unele rotații AVL Tree.
Implementarea arborelui AVL
Urmează programul C ++ pentru a demonstra arborele AVL și operațiunile sale.
// 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 Ieșire:
Trecerea în ordine pentru arborele AVL este:
4 5 8 11 12 17 18
Trecerea în ordine după ștergerea nodului 5:
4 8 11 12 17 18
Rețineți că am folosit arborele de exemplu prezentat mai sus pentru a demonstra Arborele AVL din program.
Aplicații ale copacilor AVL
- Arborii AVL sunt folosiți mai ales pentru tipuri de seturi și dicționare în memorie.
- Arborii AVL sunt, de asemenea, utilizați pe scară largă în aplicațiile de baze de date în care inserțiile și ștergerile sunt mai puține, dar există căutări frecvente pentru datele necesare.
- Este utilizat în aplicații care necesită o căutare îmbunătățită, în afară de aplicațiile bazei de date .
Structura datelor HEAP în C ++
O grămadă în C ++ este o structură de date specială bazată pe arbore și este un arbore binar complet.
Greutățile pot fi de două tipuri:
- Min-heap : În min-heap, cel mai mic element este rădăcina arborelui și fiecare nod este mai mare sau egal cu părintele său.
- Max-heap : În max-heap, cel mai mare element este rădăcina arborelui și fiecare nod este mai mic sau egal cu părintele său.
Luați în considerare următoarea matrice de elemente:
10 20 30 40 50 60 70
Min-heap pentru datele de mai sus este reprezentat mai jos:
Heapul maxim care utilizează datele de mai sus este prezentat mai jos:
ce strat al modelului osi este utilizat pentru semnale, biți, cabluri și conectori?
Binary Heap C ++
Un heap binar este implementarea comună a unei structuri de date heap.
O grămadă binară are următoarele proprietăți:
- Este un arbore binar complet când toate nivelurile sunt complet umplute, cu excepția eventualului ultim nivel și ultimul nivel are cheile sale cât mai mult posibil.
- Un heap binar poate fi un min-heap sau max-heap.
O grămadă binară este un arbore binar complet și, prin urmare, poate fi reprezentat cel mai bine ca o matrice.
Să analizăm reprezentarea matricei a heap-ului binar.
Luați în considerare următoarea grămadă binară.
În diagrama de mai sus, traversarea grămezii binare se numește ordine de nivel.
Astfel matricea pentru heap-ul binar de mai sus este prezentată mai jos ca HeapArr:
După cum se arată mai sus, HeapArr (0) este rădăcina heap-ului binar. Putem reprezenta celelalte elemente în termeni generali după cum urmează:
Dacă HeapArr (i) este un ianod într-o grămadă binară, apoi indicii celorlalte noduri din ianodul sunt:
- HeapArr ((i-1) / 2) => Returnează nodul părinte.
- HeapArr ((2 * i) +1) => Returnează nodul copil stâng.
- HeapArr ((2 * i) +2) => Returnează nodul copil potrivit.
Heapul binar îndeplinește „proprietatea de comandă”, care este de două tipuri, după cum se arată mai jos:
- Proprietatea Min Heap: Valoarea minimă este la rădăcină și valoarea fiecărui nod este mai mare sau egală cu părintele său.
- Proprietatea Max Heap: Valoarea maximă este la rădăcină și valoarea fiecărui nod este mai mică sau egală cu părintele său.
Operații pe Heap Binar
Următoarele sunt operațiunile de bază care sunt efectuate pe heap minim. În cazul heapului maxim, operațiile se inversează corespunzător.
# 1) Insert () - Inserează o nouă cheie la capătul arborelui. În funcție de valoarea cheii introduse, este posibil să trebuiască să ajustăm heap-ul, fără a încălca proprietatea heap-ului.
care este cel mai bun downloader mp3
# 2) Șterge () - Șterge o tastă. Notă că complexitatea în timp atât a operațiilor de inserare, cât și de ștergere a heap-ului este O (jurnal n).
# 3) reduceKey () - Scade valoarea tastei. Este posibil să avem nevoie să menținem proprietatea heap atunci când are loc această operațiune. Complexitatea de timp a operației de reducere a cheii este, de asemenea, O (jurnal n).
# 4) extractMin () - Elimină elementul minim din min-heap. Trebuie să mențină proprietatea heap după eliminarea elementului minim. Astfel, complexitatea sa de timp este O (log n).
# 5) getMin () - Returnează elementul rădăcină al min-heap-ului. Aceasta este cea mai simplă operație și complexitatea timpului pentru această operație este O (1).
Implementarea structurii de date Heap
Mai jos este implementarea C ++ pentru a demonstra funcționalitatea de bază a 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: '< Ieșire:
Heap după inserare: 2 4 6 8 10 12
rădăcina grămezii: 2
Heap după ștergere (2): 2 4 12 8 10
element minim în grămadă: 2
nouă rădăcină a heap-ului după scădere Key: 1
Aplicațiile grămezilor
- Heapsort: Algoritmul Heapsort este implementat în mod eficient folosind un heap binar.
- Cozi prioritare: Heapul binar acceptă toate operațiunile necesare pentru implementarea cu succes a cozilor de prioritate în timp O (jurnal n).
- Algoritmi grafic: Unii dintre algoritmii legați de grafice utilizează coada prioritară și, la rândul ei, coada prioritară utilizează heap binar.
- Complexitatea celui mai rău caz al algoritmului quicksort poate fi depășită folosind sortarea heap.
Concluzie
În acest tutorial, am văzut două structuri de date, adică arborii AVL și sortarea Heap în detaliu.
Arborii AVL sunt arbori binari echilibrați care sunt utilizați în cea mai mare parte în indexarea bazelor de date.
Toate operațiunile efectuate pe arborii AVL sunt similare cu cele ale arborilor binari de căutare, dar singura diferență în cazul arborilor AVL este că trebuie să menținem factorul de echilibru, adică structura datelor ar trebui să rămână un arbore echilibrat ca urmare a diferitelor operații. Acest lucru se realizează prin utilizarea operației AVL Tree Rotation.
Grămezile sunt structuri binare complete de arbori care sunt clasificate în min-heap sau max-heap. Min-heap are elementul minim ca rădăcină și nodurile ulterioare sunt mai mari sau egale cu nodul părinte. În max-heap, situația este exact opusă, adică elementul maxim este rădăcina heap-ului.
Greutățile pot fi reprezentate sub formă de matrice cu 0aelement ca rădăcină a copacului. Structurile de date Heap sunt utilizate în principal pentru a implementa cozi de sortare și prioritate.
=> Vizitați aici pentru a afla C ++ de la zero.
Lectură recomandată
- Structura datelor în coadă în C ++ cu ilustrație
- Stivați structura datelor în C ++ cu ilustrație
- Structură de date cu listă circulară în C ++ cu ilustrație
- Structura de date a listei legate în C ++ cu ilustrație
- Introducere în structurile de date în C ++
- Structura de date a cozii prioritare în C ++ cu ilustrație
- Structură de date de listă dublă legată în C ++ cu ilustrație
- Sortare în grămadă în C ++ cu exemple
