avl tree heap data structure c
Aquest tutorial proporciona una explicació detallada dels arbres AVL i de l'estructura de dades de Heap en C ++ juntament amb exemples de l'arbre AVL per a una millor comprensió:
L'AVL Tree és un arbre binari d'altura. Cada node està associat a un factor equilibrat que es calcula com la diferència entre l'alçada del subarbre esquerre i el subarbre dret.
L’arbre AVL rep el nom dels seus dos inventors, és a dir, G.M. Abelson-Velvety i E.M. Landis, i es va publicar el 1962 al seu article 'Un algoritme per a l'organització de la informació'.
=> Cerqueu aquí tota la sèrie de formació C ++.
Què aprendreu:
Arbre AVL a C ++
Perquè l'arbre estigui equilibrat, el factor equilibrat de cada node hauria d'estar entre -1 i 1. Si no, l'arbre es desequilibrarà.
A continuació es mostra un exemple d’arbre AVL.
A l’arbre anterior, podem observar que la diferència d’alçada dels subarbres esquerre i dret és 1. Això significa que es tracta d’un BST equilibrat. Com que el factor d'equilibri és 1, això significa que el subarbre esquerre és un nivell més alt que el subarbre dret.
Si el factor d’equilibri és 0, vol dir que els subarbres esquerre i dret es troben al mateix nivell, és a dir, que contenen la mateixa alçada. Si el factor d'equilibri és -1, el subarbre esquerre és un nivell inferior al subarbre dret.
L’arbre AVL controla l’alçada d’un arbre de cerca binari i evita que es torci. Perquè quan un arbre binari es torça, és el pitjor cas (O (n)) per a totes les operacions. En utilitzar el factor d'equilibri, l'arbre AVL imposa un límit a l'arbre binari i, per tant, manté totes les operacions a O (log n).
Operacions d'arbre AVL
A continuació es detallen les operacions admeses pels arbres AVL.
# 1) Inserció de l'arbre AVL
L’operació d’inserció a l’arbre C ++ AVL és la mateixa que l’arbre de cerca binari. L’única diferència és que, per mantenir el factor d’equilibri, hem de girar l’arbre cap a l’esquerra o cap a la dreta perquè no es desequilibri.
# 2) Supressió de l'arbre AVL
L'operació de supressió també es realitza de la mateixa manera que l'operació de supressió en un arbre de cerca binari. Una vegada més, hem de reequilibrar l'arbre realitzant algunes rotacions d'AVL Tree.
Implementació de l'arbre AVL
A continuació es mostra el programa C ++ per demostrar l'arbre AVL i les seves operacions.
// 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 Sortida:
El recorregut per ordre de l'arbre AVL és:
4 5 8 11 12 17 18
Recorregut desordenat després de la supressió del node 5:
4 8 11 12 17 18
Tingueu en compte que hem utilitzat l'arbre d'exemple mostrat anteriorment per demostrar l'arbre AVL al programa.
com obrir un fitxer .bin al Windows 10
Aplicacions dels arbres AVL
- Els arbres AVL s'utilitzen principalment per a tipus de conjunts i diccionaris en memòria.
- Els arbres AVL també s’utilitzen àmpliament en aplicacions de bases de dades en què les insercions i supressions són menors, però hi ha cerques freqüents de dades necessàries.
- S'utilitza en aplicacions que requereixen una cerca millorada a part de les aplicacions de base de dades .
Estructura de dades HEAP a C ++
Un munt en C ++ és una estructura de dades especial basada en arbres i és un arbre binari complet.
Els munts poden ser de dos tipus:
- Min-munt : En min-heap, l'element més petit és l'arrel de l'arbre i cada node és superior o igual al seu pare.
- Pila màxima : A max-heap, l'element més gran és l'arrel de l'arbre i cada node és inferior o igual al seu pare.
Penseu en la següent matriu d'elements:
10 20 30 40 50 60 70
A continuació es representa el mínim per a les dades anteriors:
A continuació es mostra l’emmagatzematge màxim amb les dades anteriors:
c ++ data i hora
Binary Heap C ++
Un muntatge binari és la implementació habitual d’una estructura de dades de muntatge.
Un munt binari té les propietats següents:
- És un arbre binari complet quan tots els nivells s’omplen completament, excepte possiblement l’últim nivell i a l’últim nivell queden les tecles el màxim possible.
- Un munt binari pot ser un min-heap o max-heap.
Un munt binari és un arbre binari complet i, per tant, es pot representar millor com una matriu.
Vegem la representació de matriu del munt binari.
Penseu en el següent munt binari.
En el diagrama anterior, el recorregut del munt binari s’anomena ordre de nivell.
Per tant, la matriu del munt binari anterior es mostra a continuació com a HeapArr:
Com es mostra més amunt, HeapArr (0) és l'arrel del munt binari. Podem representar els altres elements en termes generals de la següent manera:
Si HeapArr (i) és un ithnode en un munt binari, a continuació, els índexs dels altres nodes de l’ithnode són:
- HeapArr ((i-1) / 2) => Retorna el node pare.
- HeapArr ((2 * i) +1) => Retorna el node fill esquerre.
- HeapArr ((2 * i) +2) => Retorna el node fill correcte.
El muntatge binari compleix la 'propietat de comanda' que és de dos tipus, tal com s'indica a continuació:
- Propietat Min Heap: El valor mínim es troba a l'arrel i el valor de cada node és superior o igual al seu pare.
- Propietat Max Heap: El valor màxim es troba a l'arrel i el valor de cada node és inferior o igual al seu pare.
Operacions a l'emmagatzematge binari
A continuació es detallen les operacions bàsiques que es duen a terme en un munt mínim. En el cas del munt màxim, les operacions s'inverteixen en conseqüència.
# 1) Insereix () - Insereix una nova clau al final de l'arbre. Depenent del valor de la clau inserida, és possible que hàgim d'ajustar l'emmagatzematge dinàmic sense violar la propietat de l'emmagatzematge.
# 2) Suprimeix () - Suprimeix una tecla. Nota que la complexitat temporal tant de les operacions d'inserció com de supressió del munt és O (registre n).
# 3) disminuirKey () - Disminueix el valor de la clau. És possible que hàgim de mantenir la propietat de l'emmagatzematge dinàmic quan tingui lloc aquesta operació. La complexitat temporal de l'operació de disminució de tecles del munt també és O (log n).
# 4) extractMin () - Elimina l'element mínim del min-heap. Ha de mantenir la propietat de l'emmagatzematge dinàmic després d'eliminar l'element mínim. Per tant, la seva complexitat temporal és O (log n).
# 5) getMin () - Retorna l'element arrel del min-heap. Aquesta és l'operació més senzilla i la complexitat temporal d'aquesta operació és O (1).
Implementació de l'estructura de dades Heap
A continuació es mostra la implementació de C ++ per demostrar la funcionalitat bàsica de 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: '< Sortida:
Muntatge després de la inserció: 2 4 6 8 10 12
arrel del munt: 2
Pila després deletekey (2): 2 4 12 8 10
element mínim al munt: 2
nova arrel del munt després de disminuir Key: 1
Aplicacions de munts
- Heapsort: L’algorisme Heapsort s’implementa eficaçment mitjançant un munt binari.
- Cues prioritàries: El muntatge binari admet totes les operacions necessàries per implementar amb èxit les cues de prioritat en el temps O (registre n).
- Algorismes de gràfics: Alguns dels algoritmes relacionats amb els gràfics utilitzen cua de prioritat i, al seu torn, la cua de prioritat utilitza un munt binari.
- Es pot superar la complexitat del pitjor dels casos de l’algoritme quicksort mitjançant l’ordenació en pila.
Conclusió
En aquest tutorial, hem vist dues estructures de dades, és a dir, arbres AVL i ordenació Heap en detall.
Els arbres AVL són arbres binaris equilibrats que s’utilitzen principalment en la indexació de bases de dades.
Totes les operacions realitzades als arbres AVL són similars a les dels arbres de cerca binària, però l’única diferència en el cas dels arbres AVL és que hem de mantenir el factor d’equilibri, és a dir, l’estructura de dades hauria de continuar sent un arbre equilibrat com a resultat de diverses operacions. Això s’aconsegueix mitjançant l’operació de rotació de l’arbre AVL.
Els munts són estructures binàries completes que es classifiquen en min-heap o max-heap. Min-heap té l'element mínim com a arrel i els nodes posteriors són majors o iguals al seu node pare. A max-heap, la situació és exactament oposada, és a dir, l’element màxim és l’arrel del heap.
Els munts es poden representar en forma de matrius amb el 0thelement com a arrel de l’arbre. Les estructures de dades de pila s’utilitzen principalment per implementar cues de classificació i prioritat de pila.
=> Visiteu aquí per aprendre C ++ des de zero.
Lectura recomanada
- Estructura de dades de la cua en C ++ amb il·lustració
- Estructura de dades de pila en C ++ amb il·lustració
- Estructura de dades de llistes enllaçades circulars en C ++ amb il·lustració
- Estructura de dades de la llista enllaçada en C ++ amb il·lustració
- Introducció a les estructures de dades en C ++
- Estructura de dades de la cua de prioritat en C ++ amb il·lustració
- Estructura de dades de llistes doblement enllaçades en C ++ amb il·lustració
- Ordena en pila en C ++ amb exemples
