Meny

AVL Tree and Heap Datastruktur i C ++

  • Hoved
  • Annen
  • AVL Tree and Heap Datastruktur i C ++

avl tree heap data structure c

Prøv Instrumentet Vårt For Å Eliminere Problemer

Denne opplæringen gir en detaljert forklaring på AVL-trær og haugdatastruktur i C ++ sammen med AVL-treeksempler for bedre forståelse:

AVL Tree er et høydeavbalansert binært tre. Hver node er assosiert med en balansert faktor som beregnes som forskjellen mellom høyden på venstre undertre og høyre undertre.

AVL-treet er oppkalt etter sine to oppfinnere, dvs. G.M. Abelson-Velvety og E.M. Landis, og ble publisert i 1962 i deres papir 'En algoritme for organisering av informasjon'.

=> Se etter hele C ++ treningsserien her.

AVL Trees And Heap Data Structure i C ++

Hva du vil lære:

AVL Tree In C ++

For at treet skal balanseres, bør den balanserte faktoren for hver node være mellom -1 og 1. Hvis ikke treet blir ubalansert.

Et eksempel på AVL-tre vises nedenfor.

Example AVL tree

I det ovennevnte treet kan vi merke at forskjellen i høyde på venstre og høyre undertrær er 1. Dette betyr at det er en balansert BST. Siden balansefaktoren er 1, betyr dette at venstre undertre er ett nivå høyere enn høyre undertre.

Hvis balanseringsfaktoren er 0, betyr det at venstre og høyre undertrær er på samme nivå, dvs. de inneholder lik høyde. Hvis balanseringsfaktoren er -1, er venstre undertre ett nivå lavere enn høyre undertre.

AVL-treet styrer høyden på et binært søketre, og forhindrer at det blir skjevt. For når et binært tre blir skjevt, er det det verste tilfellet (O (n)) for alle operasjonene. Ved å bruke balansefaktoren pålegger AVL-treet en grense for det binære treet og holder dermed alle operasjonene ved O (log n).

AVL-treoperasjoner

Følgende er operasjonene som støttes av AVL-trær.

hva er forskjellen mellom kvalitetskontroll og kvalitetssikring

#1) AVL Tree Insertion

Sett inn operasjon i C ++ AVL-treet er det samme som det binære søketreet. Den eneste forskjellen er at for å opprettholde balansefaktoren, må vi rotere treet mot venstre eller høyre slik at det ikke blir ubalansert.

#2) AVL Tree Deletion

Slettingsoperasjon utføres også på samme måte som sletteoperasjonen i et binært søketre. Igjen må vi balansere treet på nytt ved å utføre noen AVL-trerotasjoner.

AVL-treimplementering

Følgende er C ++ - programmet for å demonstrere AVL-treet og dets virksomhet.

// 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

Produksjon:

Bestillingspassasje for AVL-treet er:

4 5 8 11 12 17 18

Bestill traversal etter sletting av node 5:

4 8 11 12 17 18

AVL-utgang

Merk at vi har brukt eksemplet treet vist ovenfor for å demonstrere AVL treet i programmet.

Anvendelser av AVL-trær

  1. AVL-trær brukes mest til slags sett og ordbøker i minnet.
  2. AVL-trær brukes også mye i databaseapplikasjoner der innsettinger og slettinger er færre, men det er ofte oppslag etter nødvendige data.
  3. Den brukes i applikasjoner som krever forbedret søk bortsett fra databaseapplikasjonene .

HEAP Datastruktur I C ++

En haug i C ++ er en spesiell trebasert datastruktur og er et komplett binært tre.

Hauger kan være av to typer:

  • Min-haug : I min-haug er det minste elementet roten til treet, og hver node er større enn eller lik foreldrene.
  • Max-haug : I max-heap er det største elementet roten til treet, og hver node er mindre enn eller lik foreldrene.

Vurder følgende utvalg av elementer:

10 20 30 40 50 60 70

Min-haugen for dataene ovenfor er representert nedenfor:

min-haug

Maks haugen ved hjelp av dataene ovenfor er vist nedenfor:

maks haug

Binær haug C ++

En binær bunke er den vanlige implementeringen av en bunndatastruktur.

En binær haug har følgende egenskaper:

  • Det er et komplett binært tre når alle nivåene er helt fylt bortsett fra muligens det siste nivået og det siste nivået har nøklene så mye igjen som mulig.
  • En binær haug kan være en min-haug eller maks-haug.

En binær haug er et komplett binært tre, og dermed kan den best representeres som en matrise.

La oss se på matrixrepresentasjonen av binær bunke.

Vurder følgende binære dyng.

binær haug

hva er en torrentfil og hvordan åpner jeg den

I diagrammet ovenfor kalles traversal for den binære bunken nivårekkefølge.

Dermed vises matrisen for den ovennevnte binære bunken nedenfor som HeapArr:

HeapArr

Som vist ovenfor er HeapArr (0) roten til den binære dyngen. Vi kan representere de andre elementene generelt:

Hvis HeapArr (i) er et ithnode i en binær haug, deretter indeksene til de andre nodene fra ithnode er:

  • HeapArr ((i-1) / 2) => Returnerer foreldrenoden.
  • HeapArr ((2 * i) +1) => Returnerer venstre barneknute.
  • HeapArr ((2 * i) +2) => Returnerer den rette underordnede noden.

Den binære bunken tilfredsstiller 'bestillingsegenskap' som er av to typer som angitt nedenfor:

  • Min Heap eiendom: Minimumsverdien er ved roten, og verdien til hver node er større enn eller lik den overordnede.
  • Max Heap eiendom: Maksimumsverdien er ved roten, og verdien av hver node er mindre enn eller lik dens overordnede.

Operasjoner på binær dyng

Følgende er de grunnleggende operasjonene som utføres på minimum bunke. Når det gjelder maksimal dyng, reverserer operasjonene tilsvarende.

# 1) Sett inn () - Setter inn en ny nøkkel på slutten av treet. Avhengig av verdien på nøkkelen som er satt inn, kan det hende vi må justere dyngen, uten å bryte haugegenskapen.

# 2) Slett () - Sletter en nøkkel. Merk at tidskompleksiteten til både innsettings- og sletteoperasjonene til dyngen er O (log n).

# 3) reduceKey () - Reduserer verdien på nøkkelen. Vi må kanskje vedlikeholde haugegenskapen når denne operasjonen finner sted. Tidskompleksiteten til nedgangen Nøkkeloperasjonen til dyngen er også O (log n).

# 4) extractMin () - Fjerner minimumselementet fra min-haugen. Den må vedlikeholde haugegenskapen etter at minimumselementet er fjernet. Dermed er dens tidskompleksitet O (log n).

# 5) getMin () - Returnerer rotelementet til min-haugen. Dette er den enkleste operasjonen, og tidskompleksiteten for denne operasjonen er O (1).

Heap Datastruktur Implementering

Nedenfor er C ++ implementeringen for å demonstrere den grunnleggende funksjonaliteten til 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: '<

Produksjon:

Haug etter innsetting: 2 4 6 8 10 12

roten til dyngen: 2

Haug etter sletting (2): 2 4 12 8 10

minimumselement i dyngen: 2

ny rot av dyngen etter reduksjon Nøkkel: 1

Heap Output

Anvendelser av dynger

  • Heapsort: Heapsort-algoritmen implementeres effektivt ved hjelp av en binær heap.
  • Prioritetskøer: Binary heap støtter alle operasjonene som kreves for å kunne implementere prioritetskøene i O (log n) -tid.
  • Grafalgoritmer: Noen av algoritmene relatert til grafer bruker prioritetskø, og i sin tur bruker prioritetskøen binær heap.
  • Worst-case-kompleksiteten til quicksort-algoritmen kan overvinnes ved å bruke heap sort.

Konklusjon

I denne opplæringen har vi sett to datastrukturer, dvs. AVL-trær og Heap sorterer i detalj.

AVL-trær er balanserte binære trær som mest brukes i databaseindeksering.

c ++ tilfeldig tall mellom 0 og 100

Alle operasjoner utført på AVL-trær ligner på binære søketrær, men den eneste forskjellen i tilfelle AVL-trær er at vi trenger å opprettholde balansefaktoren, dvs. datastrukturen skal forbli et balansert tre som et resultat av forskjellige operasjoner. Dette oppnås ved å bruke AVL Tree Rotation-operasjonen.

Heaps er komplette binære trestrukturer som klassifiseres i min-heap eller max-heap. Min-heap har minimumselementet som rot, og de påfølgende nodene er større enn eller lik deres overordnede node. I max-heap er situasjonen nøyaktig motsatt, dvs. maksimumselementet er roten til bunken.

Hauger kan vises i form av matriser med 0thelement som roten til treet. Heap-datastrukturer brukes hovedsakelig til å implementere haugsortering og prioritetskøer.

=> Besøk her for å lære C ++ fra grunnen.

Anbefalt lesing

^