Menu

AVL-træ- og bunndatastruktur i C ++

avl tree heap data structure c

Prøv Vores Instrument Til At Fjerne Problemer

Denne vejledning giver en detaljeret forklaring af AVL-træer og bunndatastruktur i C ++ sammen med AVL-træeksempler til bedre forståelse:

AVL Tree er et højdeabalanceret binært træ. Hver knude er forbundet med en afbalanceret faktor, der beregnes som forskellen mellem højden på dens venstre undertræ og det højre undertræ.

konvertere ascii til int c ++

AVL-træet er opkaldt efter dets to opfindere, dvs. G.M. Abelson-Velvety og E.M. Landis, og blev offentliggjort i 1962 i deres papir 'En algoritme til organisering af information'.

=> Se efter hele C ++ træningsserien her.

AVL træer og bunke datastruktur i C ++

Hvad du vil lære:

AVL-træ i C ++

For at træet skal være afbalanceret, skal den afbalancerede faktor for hver node være mellem -1 og 1. Hvis ikke træet bliver ubalanceret.

Et eksempel på AVL-træ vises nedenfor.

Eksempel på AVL-træ

I det ovennævnte træ kan vi bemærke, at forskellen i højderne på venstre og højre undertræ er 1. Dette betyder, at det er en afbalanceret BST. Da balanceringsfaktoren er 1, betyder det, at venstre undertræ er et niveau højere end det højre undertræ.

Hvis balanceringsfaktoren er 0, betyder det, at venstre og højre undertræ er på samme niveau, dvs. de indeholder samme højde. Hvis balanceringsfaktoren er -1, er venstre undertræ et niveau lavere end det højre undertræ.

AVL-træet styrer højden på et binært søgetræ, og det forhindrer det i at blive skævt. For når et binært træ bliver skævt, er det det værste tilfælde (O (n)) for alle operationer. Ved at bruge balancefaktoren pålægger AVL-træet en grænse for det binære træ og holder således alle operationer ved O (log n).

AVL Tree Operations

Følgende er de operationer, der understøttes af AVL-træer.

# 1) AVL-træindsættelse

Indsæt operation i C ++ AVL-træet er det samme som det binære søgetræ. Den eneste forskel er, at for at opretholde balancefaktoren er vi nødt til at dreje træet mod venstre eller højre, så det ikke bliver ubalanceret.

# 2) AVL-træsletning

Sletningshandling udføres også på samme måde som sletningen i et binært søgetræ. Igen er vi nødt til at balancere træet igen ved at udføre nogle AVL-trærotationer.

AVL Tree Implementation

Følgende er C ++ - programmet til at demonstrere AVL-træet og dets operationer.

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

Produktion:

Bestillingsgennemgang for AVL-træet er:

4 5 8 11 12 17 18

Inorder traversal efter sletning af node 5:

hvordan man laver filfil c ++

4 8 11 12 17 18

AVL-udgang

Bemærk, at vi har brugt eksemplet træet vist ovenfor for at demonstrere AVL træet i programmet.

Anvendelser af AVL-træer

  1. AVL-træer bruges mest til slags hukommelser og ordbøger i hukommelsen.
  2. AVL-træer bruges også i vid udstrækning i databaseapplikationer, hvor indsættelser og sletninger er færre, men der ofte søges efter krævede data.
  3. Det bruges i applikationer, der kræver forbedret søgning bortset fra databaseapplikationerne .

HEAP-datastruktur i C ++

En bunke i C ++ er en speciel træbaseret datastruktur og er et komplet binært træ.

Bunke kan være af to typer:

  • Min-bunke : I min-bunke er det mindste element roden til træet, og hver knude er større end eller lig med sin forælder.
  • Max-bunke : I max-heap er det største element roden til træet, og hver node er mindre end eller lig med dets overordnede.

Overvej følgende række elementer:

10 20 30 40 50 60 70

Min-bunken for ovenstående data er vist nedenfor:

min-bunke

Den maksimale bunke ved hjælp af ovenstående data er vist nedenfor:

max bunke

Binær bunke C ++

En binær bunke er den almindelige implementering af en bunke-datastruktur.

En binær bunke har følgende egenskaber:

  • Det er et komplet binært træ, når alle niveauer er fuldstændigt udfyldt undtagen muligvis det sidste niveau, og det sidste niveau har sine nøgler så meget tilbage som muligt.
  • En binær bunke kan være en min-bunke eller max-bunke.

En binær bunke er et komplet binært træ, og det kan således bedst repræsenteres som en matrix.

Lad os se på matrixrepræsentationen af ​​binær bunke.

Overvej følgende binære bunke.

binær bunke

I ovenstående diagram kaldes traversal for den binære bunke niveau orden.

Således vises arrayet for den ovennævnte binære bunke nedenfor som HeapArr:

HeapArr

Som vist ovenfor er HeapArr (0) roden til den binære bunke. Vi kan repræsentere de andre elementer i generelle vendinger som følger:

Hvis HeapArr (i) er et ithnode i en binær bunke, så indekserne for de andre noder fra ithnode er:

  • HeapArr ((i-1) / 2) => Returnerer den overordnede node.
  • HeapArr ((2 * i) +1) => Returnerer venstre barneknude.
  • HeapArr ((2 * i) +2) => Returnerer den rigtige underknude.

Den binære bunke opfylder 'bestillingsegenskaber', som er af to typer som anført nedenfor:

  • Min Heap ejendom: Minimumsværdien er ved roden, og værdien for hver node er større end eller lig med dens overordnede.
  • Max Heap ejendom: Den maksimale værdi er ved roden, og værdien for hver node er mindre end eller lig med dens overordnede.

Operationer på binær bunke

Følgende er de grundlæggende operationer, der udføres på minimum bunke. I tilfælde af den maksimale bunke vender operationerne tilsvarende.

# 1) Indsæt () - Indsætter en ny nøgle i slutningen af ​​træet. Afhængigt af værdien af ​​den indsatte nøgle kan det være nødvendigt at justere bunken uden at krænke bunkeegenskaben.

# 2) Slet () - Sletter en nøgle. Bemærk at tidskompleksiteten for både indsættelses- og sletningsoperationerne i bunken er O (log n).

# 3) faldKey () - Sænker nøgleværdien. Vi bliver muligvis nødt til at vedligeholde bunkeegenskaben, når denne operation finder sted. Tidskompleksiteten af ​​faldets nøgleoperation er også O (log n).

forskel mellem teststrategi og testplan

# 4) extractMin () - Fjerner minimumselementet fra min-bunken. Det er nødvendigt at vedligeholde bunkeegenskaben efter fjernelse af minimumselementet. Dens tidskompleksitet er således O (log n).

# 5) getMin () - Returnerer rodelementet på min-bunken. Dette er den enkleste operation, og tidskompleksiteten for denne operation er O (1).

Implementering af bunndatastruktur

Nedenfor er C ++ implementeringen for at demonstrere den grundlæggende funktionalitet af 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: '<

Produktion:

Bunke efter indsættelse: 2 4 6 8 10 12

dyngens rod: 2

Bunke efter sletning (2): 2 4 12 8 10

minimumselement i bunken: 2

ny rod af bunken efter fald Nøgle: 1

Bunkeoutput

Anvendelser af dynger

  • Heapsort: Heapsort-algoritme implementeres effektivt ved hjælp af en binær heap.
  • Prioriterede køer: Binær heap understøtter alle de operationer, der kræves for succesfuld implementering af prioritetskøerne i O (log n) tid.
  • Grafalgoritmer: Nogle af algoritmerne relateret til grafer bruger prioritetskø, og igen bruger prioritetskøen binær bunke.
  • Worst-case-kompleksiteten af ​​quicksort-algoritme kan overvindes ved hjælp af heap-sortering.

Konklusion

I denne vejledning har vi set to datastrukturer, dvs. AVL-træer og Heap sorterer i detaljer.

AVL-træer er afbalancerede binære træer, der mest bruges i databaseindeksering.

Alle operationer, der udføres på AVL-træer, svarer til de af binære søgetræer, men den eneste forskel i tilfældet med AVL-træer er, at vi har brug for at opretholde balancefaktoren, dvs. datastrukturen skal forblive et afbalanceret træ som et resultat af forskellige operationer. Dette opnås ved hjælp af AVL Tree Rotation-operationen.

Bunker er komplette binære træstrukturer, der klassificeres i min-bunke eller max-bunke. Min-heap har minimumselementet som sin rod, og de efterfølgende noder er større end eller lig med deres overordnede node. I max-heap er situationen nøjagtig modsat, dvs. det maksimale element er roden til bunken.

Bunke kan repræsenteres i form af arrays med 0thelement som træets rod. Heap-datastrukturer bruges hovedsageligt til at implementere bugsortering og prioritetskøer.

=> Besøg her for at lære C ++ fra bunden.

Anbefalet læsning

^