Meny

AVL-träd- och högdatastruktur i C ++

avl tree heap data structure c

Prova Vårt Instrument För Att Eliminera Problem

Denna handledning ger en detaljerad förklaring av AVL-träd och höjdatastruktur i C ++ tillsammans med AVL-trädexempel för bättre förståelse:

AVL Tree är ett höjdbalanserat binärt träd. Varje nod är associerad med en balanserad faktor som beräknas som skillnaden mellan höjden på dess vänstra underträd och det högra underträdet.

AVL-trädet är uppkallat efter sina två uppfinnare, dvs. G.M. Abelson-Velvety och E.M. Landis, och publicerades 1962 i sin uppsats 'En algoritm för organisering av information'.

=> Leta efter hela C ++ träningsserien här.

AVL-träd och höjddatastruktur i C ++

Vad du kommer att lära dig:

AVL-träd i C ++

För att trädet ska balanseras ska den balanserade faktorn för varje nod vara mellan -1 och 1. Om inte trädet blir obalanserat.

Ett exempel på AVL-träd visas nedan.

Exempel på AVL-träd

I ovanstående träd kan vi märka att höjdskillnaden för vänster och höger underträd är 1. Detta betyder att det är en balanserad BST. Eftersom balanseringsfaktorn är 1 betyder det att det vänstra underträdet är en nivå högre än det högra underträdet.

Om balanseringsfaktorn är 0 betyder det att vänster och höger underträd är på samma nivå, dvs att de innehåller samma höjd. Om balanseringsfaktorn är -1 är det vänstra underträdet en nivå lägre än det högra underträdet.

AVL-trädet kontrollerar höjden på ett binärt sökträd och förhindrar att det blir snett. För när ett binärt träd blir snett är det det värsta fallet (O (n)) för alla operationer. Genom att använda balansfaktorn sätter AVL-trädet en gräns på det binära trädet och håller därmed alla operationer vid O (log n).

AVL-trädoperationer

Följande är de funktioner som stöds av AVL-träd.

# 1) AVL-trädinsättning

Infoga operation i C ++ AVL-trädet är detsamma som det binära sökträdet. Den enda skillnaden är att för att bibehålla balansfaktorn måste vi rotera trädet åt vänster eller höger så att det inte blir obalanserat.

# 2) Radering av AVL-träd

Radering utförs också på samma sätt som radering i ett binärt sökträd. Återigen måste vi balansera trädet igen genom att utföra några AVL-trädrotationer.

AVL-trädimplementering

Följande är C ++ - programmet för att demonstrera AVL-trädet och dess verksamhet.

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

Inorder traversal för AVL-trädet är:

4 5 8 11 12 17 18

vad öppnar du jar-filer med

Inorder traversal efter radering av nod 5:

4 8 11 12 17 18

AVL-utgång

Observera att vi har använt exemplet som visas ovan för att demonstrera AVL-trädet i programmet.

Tillämpningar av AVL-träd

  1. AVL-träd används mest för in-memory-sorters uppsättningar och ordböcker.
  2. AVL-träd används också i stor utsträckning i databasapplikationer där infogningar och raderingar är färre men det finns ofta sökningar efter data som krävs.
  3. Den används i applikationer som kräver förbättrad sökning förutom databasapplikationerna .

HEAP Datastruktur i C ++

En hög i C ++ är en speciell trädbaserad datastruktur och är ett komplett binärt träd.

Heaps kan vara av två typer:

  • Min hög : I min-heap är det minsta elementet roten till trädet och varje nod är större än eller lika med sin förälder.
  • Max-hög : I max-heap är det största elementet roten till trädet och varje nod är mindre än eller lika med sin förälder.

Tänk på följande uppsättning element:

10 20 30 40 50 60 70

Min-högen för ovanstående data visas nedan:

min-hög

Maxhögen med ovanstående data visas nedan:

max hög

Binär hög C ++

En binär heap är det vanliga genomförandet av en heap-datastruktur.

En binär hög har följande egenskaper:

  • Det är ett komplett binärt träd när alla nivåer är helt fyllda utom möjligen den sista nivån och den sista nivån har sina nycklar så mycket kvar som möjligt.
  • En binär hög kan vara en minhög eller maxhög.

En binär hög är ett komplett binärt träd och kan därför bäst representeras som en matris.

Låt oss titta på matrisrepresentationen för binär hög.

Tänk på följande binära hög.

binär hög

I ovanstående diagram kallas traversal för den binära högen nivåordning.

Sålunda visas matrisen för ovanstående binära hög som HeapArr:

HeapArr

programtestintervjufrågor för erfarna kandidater

Som visas ovan är HeapArr (0) roten till den binära högen. Vi kan representera de andra elementen i allmänna termer enligt följande:

Om HeapArr (i) är ett ithi en binär hög, sedan index för de andra noder från ithnod är:

  • HeapArr ((i-1) / 2) => Returnerar föräldernoden.
  • HeapArr ((2 * i) +1) => Returnerar vänster barnnod.
  • HeapArr ((2 * i) +2) => Returnerar rätt barnnod.

Den binära högen uppfyller 'beställningsegenskap' som är av två typer som anges nedan:

vad gör jag med en torrentfil
  • Min Heap fastighet: Minimivärdet ligger vid roten och värdet på varje nod är större än eller lika med dess överordnade.
  • Max Heap fastighet: Det maximala värdet är vid roten och värdet för varje nod är mindre än eller lika med dess överordnade.

Operationer på binär hög

Följande är de grundläggande operationerna som utförs på minsta hög. När det gäller den högsta höjden vänder operationerna därefter.

# 1) Infoga () - Infogar en ny nyckel i slutet av trädet. Beroende på värdet på den infogade nyckeln kan vi behöva justera högen utan att bryta mot heapegenskapen.

# 2) Ta bort () - Raderar en nyckel. Notera att tidskomplexiteten för både infoga och ta bort operationer i högen är O (log n).

# 3) minskaKey () - Minskar tangentens värde. Vi kan behöva behålla heapegenskapen när den här operationen äger rum. Tidskomplexiteten för nedgångens nyckeloperation är också O (log n).

# 4) extractMin () - Tar bort minimumelementet från min-högen. Det måste behålla heapegenskapen efter att minimielementet har tagits bort. Således är dess tidskomplexitet O (log n).

# 5) getMin () - Returnerar rotelementet på min-högen. Detta är den enklaste operationen och tidskomplexiteten för denna operation är O (1).

Heap Data Structure Implementation

Nedan följer C ++ -implementeringen för att visa min-heaps grundläggande funktionalitet.

#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:

Hög efter insättning: 2 4 6 8 10 12

högens rot: 2

Hög efter radering (2): 2 4 12 8 10

minsta element i högen: 2

ny rot av högen efter minskningKey: 1

Heap Output

Tillämpningar av högar

  • Heapsort: Heapsort-algoritmen implementeras effektivt med hjälp av en binär heap.
  • Prioriterade köer: Binary heap stöder alla operationer som krävs för att framgångsrikt implementera prioritetsköerna i O (log n) -tid.
  • Grafalgoritmer: Några av algoritmerna relaterade till grafer använder prioritetskö och i sin tur använder prioritetskön binär hög.
  • Värsta fall-komplexiteten hos snabbsortalgoritmen kan övervinnas med hjälp av högsortering.

Slutsats

I den här handledningen har vi sett två datastrukturer, dvs. AVL-träd och Heap sorteras i detalj.

AVL-träd är balanserade binära träd som oftast används i databasindexering.

Alla operationer som utförs på AVL-träd liknar de för binära sökträd, men den enda skillnaden i fallet med AVL-träd är att vi måste behålla balansfaktorn, dvs. datastrukturen ska förbli ett balanserat träd som ett resultat av olika operationer. Detta uppnås genom att använda AVL Tree Rotation-funktionen.

Heaps är kompletta binära trädstrukturer som klassificeras i min-heap eller max-heap. Min-heap har minimielementet som rot och efterföljande noder är större än eller lika med deras överordnade nod. I max-heap är situationen exakt motsatt, dvs. det maximala elementet är roten till högen.

Högar kan representeras i form av matriser med 0thelementet som trädets rot. Heap-datastrukturer används huvudsakligen för att implementera högsorterings- och prioritetsköer.

=> Besök här för att lära dig C ++ från Scratch.

Rekommenderad läsning

^