avl tree heap data structure c
Questo tutorial fornisce una spiegazione dettagliata degli alberi AVL e della struttura dei dati dell'heap in C ++ insieme agli esempi di albero AVL per una migliore comprensione:
AVL Tree è un albero binario bilanciato in altezza. Ogni nodo è associato a un fattore bilanciato che viene calcolato come la differenza tra l'altezza della sua sottostruttura sinistra e la sottostruttura destra.
L'albero AVL prende il nome dai suoi due inventori, ovvero G.M. Abelson-Velvety e E.M. Landis, ed è stato pubblicato nel 1962 nel loro articolo 'Un algoritmo per l'organizzazione delle informazioni'.
=> Cerca qui l'intera serie di formazione C ++.
Cosa imparerai:
Albero AVL in C ++
Affinché l'albero sia bilanciato, il fattore di bilanciamento per ciascun nodo dovrebbe essere compreso tra -1 e 1. In caso contrario, l'albero diventerà sbilanciato.
Di seguito è mostrato un esempio di albero AVL.
Nell'albero sopra, possiamo notare che la differenza di altezza dei sottoalberi sinistro e destro è 1. Ciò significa che è un BST bilanciato. Poiché il fattore di bilanciamento è 1, significa che la sottostruttura sinistra è di un livello superiore rispetto alla sottostruttura destra.
Se il fattore di bilanciamento è 0, significa che i sottoalberi sinistro e destro sono allo stesso livello, ovvero contengono la stessa altezza. Se il fattore di bilanciamento è -1, la sottostruttura sinistra è di un livello inferiore rispetto alla sottostruttura destra.
domande e risposte dell'intervista sullo scripting della shell
L'albero AVL controlla l'altezza di un albero di ricerca binario e ne impedisce l'inclinazione. Perché quando un albero binario diventa inclinato, è il caso peggiore (O (n)) per tutte le operazioni. Utilizzando il fattore di bilanciamento, l'albero AVL impone un limite all'albero binario e quindi mantiene tutte le operazioni su O (log n).
Operazioni sugli alberi AVL
Le seguenti sono le operazioni supportate dagli alberi AVL.
# 1) Inserimento dell'albero AVL
L'operazione di inserimento nell'albero C ++ AVL è uguale a quella dell'albero di ricerca binario. L'unica differenza è che per mantenere il fattore di equilibrio, dobbiamo ruotare l'albero a sinistra oa destra in modo che non si sbilanci.
# 2) Eliminazione dell'albero AVL
Anche l'operazione di eliminazione viene eseguita allo stesso modo dell'operazione di eliminazione in un albero di ricerca binario. Ancora una volta abbiamo bisogno di ribilanciare l'albero eseguendo alcune rotazioni dell'albero AVL.
Implementazione dell'albero AVL
Di seguito è riportato il programma C ++ per dimostrare l'albero AVL e le sue operazioni.
// 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 Produzione:
L'attraversamento in ordine per l'albero AVL è:
4 5 8 11 12 17 18
Attraversamento in ordine dopo l'eliminazione del nodo 5:
4 8 11 12 17 18
Notare che abbiamo utilizzato l'albero di esempio mostrato sopra per dimostrare l'albero AVL nel programma.
Applicazioni degli alberi AVL
- Gli alberi AVL vengono utilizzati principalmente per tipi di set e dizionari in memoria.
- Gli alberi AVL sono anche ampiamente utilizzati nelle applicazioni di database in cui gli inserimenti e le eliminazioni sono inferiori ma sono frequenti le ricerche per i dati richiesti.
- Viene utilizzato in applicazioni che richiedono una ricerca migliorata oltre alle applicazioni di database .
Struttura dei dati HEAP in C ++
Un heap in C ++ è una speciale struttura dati basata su albero ed è un albero binario completo.
Gli cumuli possono essere di due tipi:
miglior software per macchine virtuali per Windows
- Min-heap : In min-heap, l'elemento più piccolo è la radice dell'albero e ogni nodo è maggiore o uguale al suo genitore.
- Max-heap : In max-heap, l'elemento più grande è la radice dell'albero e ogni nodo è minore o uguale al suo genitore.
Considera il seguente array di elementi:
10 20 30 40 50 60 70
Il min-heap per i dati di cui sopra è rappresentato di seguito:
L'heap massimo che utilizza i dati sopra è mostrato di seguito:
Heap binario C ++
Un heap binario è l'implementazione comune di una struttura dati di heap.
Un heap binario ha le seguenti proprietà:
- È un albero binario completo quando tutti i livelli sono completamente riempiti tranne forse l'ultimo livello e l'ultimo livello ha le sue chiavi il più possibile.
- Un heap binario può essere min-heap o max-heap.
Un heap binario è un albero binario completo e quindi può essere rappresentato al meglio come un array.
Diamo un'occhiata alla rappresentazione dell'array dell'heap binario.
Considera il seguente heap binario.
Nel diagramma sopra, l'attraversamento per l'heap binario è chiamato ordine dei livelli.
Pertanto l'array per l'heap binario sopra è mostrato di seguito come HeapArr:
Come mostrato sopra, HeapArr (0) è la radice dell'heap binario. Possiamo rappresentare gli altri elementi in termini generali come segue:
Se HeapArr (i) è un ithnodo in un heap binario, quindi gli indici degli altri nodi da ithnodo sono:
- HeapArr ((i-1) / 2) => Restituisce il nodo genitore.
- HeapArr ((2 * i) +1) => Restituisce il nodo figlio sinistro.
- HeapArr ((2 * i) +2) => Restituisce il nodo figlio destro.
L'heap binario soddisfa la 'proprietà di ordinamento' che è di due tipi come indicato di seguito:
- Proprietà Heap minimo: Il valore minimo è alla radice e il valore di ogni nodo è maggiore o uguale al suo genitore.
- Proprietà Max Heap: Il valore massimo è alla radice e il valore di ogni nodo è minore o uguale al suo genitore.
Operazioni su heap binario
Di seguito sono riportate le operazioni di base che vengono eseguite sull'heap minimo. Nel caso dell'heap massimo, le operazioni si invertono di conseguenza.
# 1) Inserisci () - Inserisce una nuova chiave alla fine dell'albero. A seconda del valore della chiave inserita, potremmo dover regolare l'heap, senza violare la proprietà dell'heap.
# 2) Elimina () - Elimina una chiave. Nota che la complessità temporale delle operazioni di inserimento e cancellazione dell'heap è O (log n).
# 3) diminuzioneKey () - Diminuisce il valore della chiave. Potrebbe essere necessario mantenere la proprietà heap quando viene eseguita questa operazione. Anche la complessità temporale dell'operazione decrementKey dell'heap è O (log n).
# 4) extractMin () - Rimuove l'elemento minimo dal min-heap. Deve mantenere la proprietà heap dopo aver rimosso l'elemento minimo. Quindi la sua complessità temporale è O (log n).
# 5) getMin () - Restituisce l'elemento radice del min-heap. Questa è l'operazione più semplice e la complessità temporale per questa operazione è O (1).
Implementazione della struttura dei dati dell'heap
Di seguito è riportata l'implementazione C ++ per dimostrare la funzionalità di base di 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: '< Produzione:
Mucchio dopo l'inserimento: 2 4 6 8 10 12
radice dell'heap: 2
Heap dopo il tasto di cancellazione (2): 2 4 12 8 10
elemento minimo nell'heap: 2
nuova radice dell'heap dopo diminuireKey: 1
cos'è un buon convertitore da youtube a mp3
Applicazioni di cumuli
- Heapsort: L'algoritmo di Heapsort viene efficacemente implementato utilizzando un heap binario.
- Code prioritarie: L'heap binario supporta tutte le operazioni richieste per implementare correttamente le code di priorità nel tempo O (log n).
- Algoritmi del grafico: Alcuni degli algoritmi relativi ai grafici utilizzano la coda di priorità e, a sua volta, la coda di priorità utilizza l'heap binario.
- La complessità nel caso peggiore dell'algoritmo Quicksort può essere superata utilizzando l'ordinamento dell'heap.
Conclusione
In questo tutorial, abbiamo visto in dettaglio due strutture dati, ovvero alberi AVL e ordinamento Heap.
Gli alberi AVL sono alberi binari bilanciati che vengono utilizzati principalmente nell'indicizzazione del database.
Tutte le operazioni eseguite sugli alberi AVL sono simili a quelle degli alberi di ricerca binari ma l'unica differenza nel caso degli alberi AVL è che dobbiamo mantenere il fattore di equilibrio, ovvero la struttura dei dati dovrebbe rimanere un albero bilanciato come risultato di varie operazioni. Ciò si ottiene utilizzando l'operazione AVL Tree Rotation.
Gli heap sono strutture ad albero binario complete classificate in min-heap o max-heap. Min-heap ha l'elemento minimo come radice ei nodi successivi sono maggiori o uguali al loro nodo padre. In max-heap, la situazione è esattamente opposta, ovvero l'elemento massimo è la radice dell'heap.
Gli heap possono essere rappresentati sotto forma di array con lo 0thelemento come radice dell'albero. Le strutture dati dell'heap vengono utilizzate principalmente per implementare l'ordinamento dell'heap e le code di priorità.
=> Visita qui per imparare C ++ da zero.
Lettura consigliata
- Struttura dei dati della coda in C ++ con illustrazione
- Stack Struttura Dati In C ++ Con Illustrazione
- Struttura Dati Elenco Collegato Circolare In C ++ Con Illustrazione
- Struttura Dati Elenco Collegato In C ++ Con Illustrazione
- Introduzione alle strutture dati in C ++
- Priorità Struttura Dati Coda In C ++ Con Illustrazione
- Struttura dei dati della lista doppiamente collegata in C ++ con illustrazione
- Ordinamento heap in C ++ con esempi
