Menu

Dátová štruktúra stromu a haldy AVL v C ++

  • Hlavná
  • Iné
  • Dátová štruktúra stromu a haldy AVL v C ++

avl tree heap data structure c

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Tento výukový program poskytuje podrobné vysvetlenie stromov AVL a haldy dátovej štruktúry v C ++ spolu s príkladmi stromu AVL pre lepšie pochopenie:

AVL Tree je výškovo vyvážený binárny strom. Ku každému uzlu je priradený vyvážený faktor, ktorý sa počíta ako rozdiel medzi výškou jeho ľavého podstromu a pravého podstromu.

Strom AVL je pomenovaný po svojich dvoch vynálezcoch, t. J. G.M. Abelson-Velvety a E.M. Landis a boli publikované v roku 1962 vo svojej práci „Algoritmus pre organizáciu informácií“.

=> Celú sériu školení pre C ++ nájdete tu.

čo je najlepší downloader hudby pre Android

Stromy AVL a haldy dátovej štruktúry v C ++

Čo sa dozviete:

Strom AVL v C ++

Aby bol strom vyvážený, vyvážený faktor pre každý uzol by mal byť medzi -1 a 1. Ak nie, strom sa stane nevyváženým.

Nižšie je uvedený príklad stromu AVL.

Príklad stromu AVL

Vo vyššie uvedenom strome si môžeme všimnúť, že rozdiel vo výškach ľavého a pravého podstromu je 1. To znamená, že ide o vyvážený BST. Pretože vyrovnávací faktor je 1, znamená to, že ľavý podstrom je o jednu úroveň vyššie ako pravý podstrom.

Ak je vyrovnávací faktor 0, znamená to, že ľavý a pravý podstrom sú na rovnakej úrovni, t. J. Obsahujú rovnakú výšku. Ak je vyrovnávací faktor -1, potom je ľavý podstrom o jednu úroveň nižší ako pravý podstrom.

Strom AVL riadi výšku binárneho vyhľadávacieho stromu a zabraňuje jeho skoseniu. Pretože keď sa binárny strom skreslí, je to najhorší prípad (O (n)) pre všetky operácie. Použitím faktora rovnováhy ukladá AVL strom limit binárnemu stromu a tým udržuje všetky operácie na O (log n).

Operácie so stromom AVL

Nasledujú operácie podporované stromami AVL.

# 1) Vkladanie stromu AVL

Operácia vloženia do stromu C ++ AVL je rovnaká ako operácia binárneho vyhľadávacieho stromu. Jediný rozdiel je v tom, že aby sme udržali rovnovážny faktor, musíme strom otočiť doľava alebo doprava, aby sa nestal nevyváženým.

# 2) Vymazanie stromu AVL

Operácia odstránenia sa tiež vykonáva rovnakým spôsobom ako operácia odstránenia v binárnom vyhľadávacom strome. Opäť musíme vyvážiť strom vykonaním niektorých rotácií stromu AVL.

Implementácia stromu AVL

Nasleduje program C ++ na demonštráciu stromu AVL a jeho operácií.

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

Výkon:

Prechod v poradí pre strom AVL je:

4 5 8 11 12 17 18

Prechod v poradí po odstránení uzla 5:

4 8 11 12 17 18

AVL výstup

Všimnite si, že sme použili ukážkový strom zobrazený vyššie na demonštráciu stromu AVL v programe.

Aplikácie stromov AVL

  1. Stromy AVL sa väčšinou používajú pre druhy súborov a slovníkov v pamäti.
  2. Stromy AVL sa tiež hojne používajú v databázových aplikáciách, v ktorých je vkladanie a mazanie menej, ale sú potrebné časté vyhľadávania požadovaných údajov.
  3. Používa sa v aplikáciách, ktoré okrem databázových aplikácií vyžadujú vylepšené vyhľadávanie .

Dátová štruktúra HEAP v C ++

Halda v C ++ je špeciálna stromová dátová štruktúra a je úplným binárnym stromom.

Hromady môžu byť dvoch typov:

  • Hromada min : V halde min je najmenším prvkom koreň stromu a každý uzol je väčší alebo rovnaký ako jeho rodič.
  • Max. Hromada : V max-halde je najväčším prvkom koreň stromu a každý uzol je menší alebo rovnaký ako jeho rodič.

Zvážte nasledujúce pole prvkov:

10 20 30 40 50 60 70

Minimálna hromada vyššie uvedených údajov je uvedená nižšie:

min. halda

Maximálna halda využívajúca vyššie uvedené údaje je uvedená nižšie:

max hromada

Binárna halda C ++

Binárna halda je bežná implementácia haldy dátovej štruktúry.

ako nainštalovať zatmenie pre c ++

Binárna halda má nasledujúce vlastnosti:

  • Je to kompletný binárny strom, keď sú všetky úrovne úplne vyplnené, okrem poslednej úrovne a poslednej úrovne zostáva čo najviac kľúčov.
  • Binárna hromada môže byť minimálna alebo maximálna.

Binárna hromada je úplný binárny strom, a preto ho možno najlepšie predstaviť ako pole.

Pozrime sa na predstavu poľa binárnej haldy.

Zvážte nasledujúcu binárnu haldu.

binárna halda

Vo vyššie uvedenom diagrame sa prechod binárnej haldy nazýva usporiadanie úrovne.

Pole pre vyššie uvedenú binárnu haldu je teda zobrazené nižšie ako HeapArr:

HeapArr

Ako je uvedené vyššie, HeapArr (0) je koreňom binárnej haldy. Ostatné prvky môžeme všeobecne predstaviť nasledovne:

Ak je HeapArr (i) ithuzol v binárnej halde, potom indexy ostatných uzlov z ithuzly sú:

  • HeapArr ((i-1) / 2) => Vráti nadradený uzol.
  • HeapArr ((2 * i) +1) => Vráti ľavý podradený uzol.
  • HeapArr ((2 * i) +2) => Vráti pravý podradený uzol.

Binárna hromada spĺňa „objednávaciu vlastnosť“, ktorá je dvoch typov, ako je uvedené nižšie:

  • Vlastnosť minimálnej haldy: Minimálna hodnota je v koreňovom adresári a hodnota každého uzla je väčšia alebo rovnaká ako jeho nadradený objekt.
  • Max. Vlastnosť haldy: Maximálna hodnota je v koreňovom adresári a hodnota každého uzla je menšia alebo rovnaká ako jeho nadradená položka.

Operácie na binárnej kope

Nasledujú základné operácie, ktoré sa vykonávajú s minimálnou hromadou. V prípade maximálnej haldy sa operácie zodpovedajúcim spôsobom obrátia.

# 1) Vložiť () - Vloží nový kľúč na koniec stromu. V závislosti na hodnote vloženého kľúča bude pravdepodobne potrebné upraviť haldu, bez toho aby došlo k porušeniu vlastnosti haldy.

# 2) Odstrániť () - Vymaže kľúč. Poznámka že časová zložitosť operácií vkladania a mazania haldy je O (log n).

# 3) poklesKey () - Znižuje hodnotu kľúča. Keď bude táto operácia prebiehať, možno budeme musieť zachovať vlastnosť haldy. Časová zložitosť operácie changeKey haldy je tiež O (log n).

# 4) extractMin () - Odstráni minimálny prvok z minimálnej haldy. Po odstránení minimálneho prvku musí zachovať vlastnosť haldy. Jeho časová zložitosť je teda O (log n).

# 5) getMin () - Vráti koreňový prvok min haldy. Toto je najjednoduchšia operácia a časová zložitosť pre túto operáciu je O (1).

najlepší bezplatný softvér na kopírovanie DVD s Windows

Implementácia haldy dátovej štruktúry

Ďalej je uvedená implementácia C ++ na demonštrovanie základnej funkčnosti min haldy.

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

Výkon:

Halda po vložení: 2 4 6 8 10 12

koreň haldy: 2

Halda po deletekey (2): 2 4 12 8 10

minimálny prvok v halde: 2

nový koreň haldy po poklese Kľúč: 1

Hromadný výstup

Aplikácie hromad

  • Heapsort: Algoritmus Heapsort je efektívne implementovaný pomocou binárnej haldy.
  • Prioritné rady: Binárna halda podporuje všetky operácie potrebné na úspešnú implementáciu prioritných frontov v čase O (log n).
  • Algoritmy grafov: Niektoré z algoritmov súvisiacich s grafmi používajú prioritný front a naopak prioritný front používa binárnu haldu.
  • Najhoršiu zložitosť algoritmu quicksort možno prekonať použitím haldy.

Záver

V tomto tutoriáli sme videli dve dátové štruktúry, t. J. AVL stromy a haldy, zoradené podrobne.

Stromy AVL sú vyvážené binárne stromy, ktoré sa väčšinou používajú pri indexovaní databáz.

Všetky operácie vykonávané na stromoch AVL sú podobné operáciám vykonaným na stromoch binárneho vyhľadávania, ale jediný rozdiel v prípade stromov AVL spočíva v tom, že musíme zachovať rovnovážny faktor, t. J. Dátová štruktúra by mala zostať vyváženým stromom v dôsledku rôznych operácií. To sa dosiahne použitím operácie AVL Tree Rotation.

Haldy sú úplné binárne stromové štruktúry, ktoré sú klasifikované ako min. Halda alebo max. Halda. Min-halda má ako koreň minimálny prvok a nasledujúce uzly sú väčšie alebo rovnaké ako ich nadradený uzol. V prípade max-haldy je situácia presne opačná, tzn. Maximálny prvok je koreňom haldy.

Hromady môžu byť reprezentované vo forme polí s 0thprvok ako koreň stromu. Haldové dátové štruktúry sa používajú hlavne na implementáciu frontov na triedenie a prioritu front.

=> Navštívte tu a naučte sa C ++ od nuly.

Odporúčané čítanie

^