avl tree heap data structure c
Ovaj vodič nudi detaljno objašnjenje AVL stabala i strukture podataka gomile na C ++u, zajedno s primjerima AVL stabla za bolje razumijevanje:
AVL stablo je binarno stablo uravnoteženo po visini. Svaki čvor povezan je s uravnoteženim faktorom koji se izračunava kao razlika između visine njegova lijevog i desnog podstabla.
Stablo AVL dobilo je ime po dvojici izumitelja tj. G.M. Abelson-Velvety i E.M. Landis, a objavljen je 1962. u njihovom radu 'Algoritam za organizaciju informacija'.
=> Ovdje potražite cijelu seriju treninga za C ++.
Što ćete naučiti:
AVL stablo u C ++
Da bi stablo bilo uravnoteženo, uravnoteženi faktor za svaki čvor trebao bi biti između -1 i 1. Ako ne, stablo će postati neuravnoteženo.
Primjer AVL stabla prikazan je u nastavku.
U gornjem stablu možemo primijetiti da je razlika u visini lijevog i desnog podstabla 1. To znači da je to uravnoteženi BST. Kako je faktor uravnoteženja 1, to znači da je lijevo podstablo jedna razina više od desnog podstabla.
Ako je faktor uravnoteženja 0, to znači da su lijevo i desno podstabla na istoj razini, tj. Sadrže jednaku visinu. Ako je faktor uravnoteženja -1, onda je lijevo podstablo za jednu razinu niže od desnog podstabla.
Stablo AVL kontrolira visinu binarnog stabla pretraživanja i sprječava njegovo iskrivljenje. Jer kada binarno stablo postane iskrivljeno, to je najgori slučaj (O (n)) za sve operacije. Korištenjem faktora ravnoteže, AVL stablo nameće ograničenje binarnom stablu i tako zadržava sve operacije na O (log n).
Operacije AVL stabla
Slijede operacije koje podržavaju AVL stabla.
# 1) Umetanje AVL stabla
Operacija umetanja u stablo C ++ AVL ista je kao i kod binarnog stabla pretraživanja. Jedina je razlika u tome što da bismo održali faktor ravnoteže, moramo okretati stablo ulijevo ili udesno kako ne bi postalo neuravnoteženo.
# 2) Brisanje AVL stabla
Operacija brisanja također se izvodi na isti način kao i operacija brisanja u binarnom stablu pretraživanja. Opet trebamo uravnotežiti stablo izvođenjem nekih rotacija AVL stabla.
Implementacija AVL stabla
Slijedi program C ++ za demonstraciju AVL stabla i njegovih operacija.
// 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 Izlaz:
Preokret za AVL stablo je:
4 5 8 11 12 17 18
Neobavezno zaobilaženje nakon brisanja čvora 5:
4 8 11 12 17 18
Imajte na umu da smo koristili prethodno prikazano stablo za demonstraciju AVL stabla u programu.
Primjene AVL stabala
- AVL stabla uglavnom se koriste za vrste skupova i rječnike u memoriji.
- AVL stabla također se široko koriste u aplikacijama baza podataka u kojima je umetanja i brisanja manje, ali često se traže podaci koji se traže.
- Koristi se u aplikacijama koje zahtijevaju poboljšano pretraživanje osim aplikacija baze podataka .
Struktura podataka HEAP u C ++
Hrpa u C ++-u posebna je struktura podataka koja se temelji na stablu i cjelovito je binarno stablo.
Hrpe mogu biti dvije vrste:
- Min-hrpa : U min-hrpi najmanji je element korijen stabla i svaki čvor je veći ili jednak svom roditelju.
- Max-hrpa : U max-heap-u najveći je element korijen stabla i svaki čvor je manji ili jednak svom roditelju.
Razmotrite sljedeći niz elemenata:
kako deklarirati višedimenzionalni niz u javi
10 20 30 40 50 60 70
Minimalna hrpa za gornje podatke predstavljena je u nastavku:
Maksimalna hrpa koja koristi gornje podatke prikazana je u nastavku:
Binarna hrpa C ++
Binarna hrpa uobičajena je primjena strukture podataka hrpe.
Binarna hrpa ima sljedeća svojstva:
- Potpuno je binarno stablo kada su sve razine u potpunosti ispunjene, osim možda posljednje razine, a zadnja razina ima svoje ključeve što je više moguće.
- Binarna hrpa može biti min-heap ili max-heap.
Binarna hrpa je cjelovito binarno stablo i stoga je najbolje predstaviti kao niz.
Pogledajmo prikaz niza binarne hrpe.
Razmotrite sljedeću binarnu hrpu.
U gornjem dijagramu zaokret za binarnu hrpu naziva se redoslijedom razine.
Stoga je niz za gornju binarnu hrpu prikazan ispod kao HeapArr:
Kao što je gore prikazano, HeapArr (0) je korijen binarne hrpe. Ostale elemente možemo predstaviti općenito na sljedeći način:
Ako je HeapArr (i) ithčvor u binarnoj hrpi, zatim indeksi ostalih čvorova iz ithčvor su:
- HeapArr ((i-1) / 2) => Vraća nadređeni čvor.
- HeapArr ((2 * i) +1) => Vraća lijevi podređeni čvor.
- HeapArr ((2 * i) +2) => Vraća desni podređeni čvor.
Binarna hrpa zadovoljava 'svojstvo naručivanja', koje je dvije vrste kako je navedeno u nastavku:
- Svojstvo Min Heap: Minimalna vrijednost nalazi se u korijenu, a vrijednost svakog čvora veća je ili jednaka nadređenom.
- Svojstvo Max Heap: Maksimalna vrijednost nalazi se u korijenu, a vrijednost svakog čvora manja je ili jednaka nadređenom.
Operacije na binarnoj hrpi
Slijede osnovne operacije koje se izvode na minimalnoj hrpi. U slučaju maksimalne hrpe, operacije se u skladu s tim preokreću.
# 1) Umetni () - Umeće novi ključ na kraj stabla. Ovisno o vrijednosti umetnutog ključa, možda ćemo morati prilagoditi hrpu, bez kršenja svojstva hrpe.
# 2) Izbriši () - Briše ključ. Bilješka da je vremenska složenost operacija umetanja i brisanja hrpe O (log n).
# 3) reduceKey () - Smanjuje vrijednost ključa. Možda ćemo trebati održavati svojstvo hrpe kad se izvede ova operacija. Vremenska složenost smanjenjaKljučni rad hrpe također je O (log n).
# 4) extractMin () - Uklanja minimalni element iz min-hrpe. Potrebno je održavati svojstvo hrpe nakon uklanjanja minimalnog elementa. Stoga je njegova vremenska složenost O (log n).
# 5) getMin () - Vraća korijenski element min-hrpe. Ovo je najjednostavnija operacija, a vremenska složenost ove operacije je O (1).
koliko vrsta datoteka postoji? piton
Implementacija strukture podataka gomile
Dolje je data implementacija C ++ za demonstraciju osnovne funkcionalnosti min-heap-a.
#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: '< Izlaz:
Hrpa nakon umetanja: 2 4 6 8 10 12
korijen hrpe: 2
Hrpa nakon tipke za brisanje (2): 2 4 12 8 10
minimalni element u hrpi: 2
novi korijen hrpe nakon smanjenjaKljuč: 1
Primjene gomila
- Teška sorta: Heapsort algoritam se učinkovito implementira pomoću binarne hrpe.
- Prioritetni redovi: Binarna hrpa podržava sve operacije potrebne za uspješnu implementaciju redova prioriteta u O (log n) vremenu.
- Grafički algoritmi: Neki od algoritama koji se odnose na grafikone koriste red prioriteta, a red prioriteta koristi binarnu hrpu.
- Složenost algoritma brzog sortiranja u najgorem slučaju može se prevladati pomoću sortiranja hrpe.
Zaključak
U ovom uputstvu vidjeli smo dvije podatkovne strukture, tj. AVL stabla i Heap detaljno razvrstavanje.
AVL stabla su uravnotežena binarna stabla koja se uglavnom koriste u indeksiranju baze podataka.
Sve operacije izvedene na AVL stablima slične su operacijama binarnih stabala pretraživanja, ali jedina razlika u slučaju AVL stabala je ta što moramo održavati faktor ravnoteže, tj. Struktura podataka treba ostati uravnoteženo stablo kao rezultat različitih operacija. To se postiže korištenjem AVL rotacije stabla.
Hrpe su cjelovite binarne strukture stabla koje se klasificiraju u min-heap ili max-heap. Min-heap ima minimalni element kao korijen, a sljedeći čvorovi veći su ili jednaki njihovom nadređenom čvoru. U max-heap-u situacija je upravo suprotna tj. Maksimalni element je korijen hrpe.
Hrpe se mogu predstaviti u obliku nizova s 0thelement kao korijen stabla. Strukture podataka hrpe uglavnom se koriste za implementaciju redova sortiranja hrpe i prioriteta.
=> Posjetite ovdje da biste C ++ naučili od nule.
Preporučena literatura
- Struktura podataka u redu čekanja u C ++ s ilustracijom
- Složite strukturu podataka u C ++ s ilustracijom
- Kružno povezana struktura podataka popisa na C ++ s ilustracijom
- Povezana struktura podataka popisa na C ++ s ilustracijom
- Uvod u strukture podataka na C ++
- Struktura podataka prioritetnog reda u C ++ s ilustracijom
- Dvostruko povezana struktura podataka popisa na C ++ s ilustracijom
- Razvrstavanje hrpe u C ++ s primjerima
