Menu

Datová struktura stromu AVL a haldy v C ++

avl tree heap data structure c

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Tento kurz poskytuje podrobné vysvětlení stromů AVL a datové struktury haldy v C ++ spolu s příklady stromů AVL pro lepší pochopení:

AVL Tree je výškově vyvážený binární strom. Každý uzel je spojen s vyváženým faktorem, který se počítá jako rozdíl mezi výškou jeho levého podstromu a pravého podstromu.

Strom AVL je pojmenován podle svých dvou vynálezců, tj. G.M. Abelson-Velvety a E.M. Landis a byly publikovány v roce 1962 ve své práci „Algoritmus pro organizaci informací“.

=> Podívejte se na celou sérii školení C ++ zde.

Stromy AVL a haldy datové struktury v C ++

Co se naučíte:

Strom AVL v C ++

Aby byl strom vyvážený, měl by být vyvážený faktor pro každý uzel mezi -1 a 1. Pokud ne, strom se stane nevyváženým.

Níže je uveden příklad stromu AVL.

Příklad stromu AVL

Ve výše uvedeném stromu si můžeme všimnout, že rozdíl ve výškách levého a pravého podstromu je 1. To znamená, že se jedná o vyvážený BST. Jelikož vyrovnávací faktor je 1, znamená to, že levý podstrom je o jednu úroveň vyšší než pravý podstrom.

Pokud je vyrovnávací faktor 0, znamená to, že levý a pravý podstrom jsou na stejné úrovni, tj. Obsahují stejnou výšku. Pokud je vyrovnávací faktor -1, pak je levý podstrom o jednu úroveň nižší než pravý podstrom.

Strom AVL řídí výšku binárního vyhledávacího stromu a zabraňuje jeho zkosení. Protože když se binární strom zkosí, je to nejhorší případ (O (n)) pro všechny operace. Použitím faktoru rovnováhy ukládá strom AVL omezení na binární strom a udržuje tak všechny operace na O (log n).

Provoz stromu AVL

Následují operace podporované stromy AVL.

nejlepší software pro aktualizaci ovladačů Windows 10

# 1) Vkládání stromu AVL

Operace vložení do stromu C ++ AVL je stejná jako operace binárního vyhledávacího stromu. Jediný rozdíl je v tom, že v zájmu udržení rovnovážného faktoru musíme strom otočit doleva nebo doprava, aby nedošlo k nevyváženosti.

# 2) Odstranění stromu AVL

Operace odstranění se také provádí stejným způsobem jako operace odstranění v binárním vyhledávacím stromu. Opět musíme vyvážit strom provedením několika rotací stromu AVL.

Implementace stromu AVL

Následuje program C ++, který demonstruje strom AVL a jeho operace.

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

Inorder traversal pro strom AVL je:

4 5 8 11 12 17 18

Pohyb v pořadí po odstranění uzlu 5:

4 8 11 12 17 18

Výstup AVL

Všimněte si, že jsme použili ukázkový strom zobrazený výše k demonstraci stromu AVL v programu.

Aplikace stromů AVL

  1. Stromy AVL se většinou používají pro druhy sad a slovníků v paměti.
  2. Stromy AVL se také hojně používají v databázových aplikacích, ve kterých je vkládání a mazání méně, ale jsou vyžadována častá vyhledávání požadovaných dat.
  3. Používá se v aplikacích, které vyžadují vylepšené vyhledávání kromě databázových aplikací .

Datová struktura HEAP v C ++

Halda v C ++ je speciální stromová datová struktura a je úplným binárním stromem.

Hromady mohou být dvou typů:

  • Min. Hromada : V haldě min je nejmenším prvkem kořen stromu a každý uzel je větší nebo roven svému nadřazenému prvku.
  • Max. Hromada : V max-heap je největším prvkem kořen stromu a každý uzel je menší nebo roven svému nadřazenému prvku.

Zvažte následující pole prvků:

10 20 30 40 50 60 70

Hromada min pro výše uvedená data je uvedena níže:

min. hromada

Maximální hromada využívající výše uvedená data je uvedena níže:

max. hromada

Binární halda C ++

Binární halda je běžná implementace haldy datové struktury.

Binární halda má následující vlastnosti:

  • Jedná se o kompletní binární strom, kdy jsou všechny úrovně zcela vyplněny, s výjimkou poslední úrovně a poslední úrovni zbývají klíče co nejvíce.
  • Binární halda může být min. Halda nebo max. Halda.

Binární halda je úplný binární strom, a proto jej lze nejlépe reprezentovat jako pole.

Pojďme se podívat na reprezentaci pole binární haldy.

Zvažte následující binární haldu.

binární hromada

Ve výše uvedeném diagramu se traversal pro binární haldu nazývá pořadí úrovní.

Pole výše uvedené binární haldy je tedy zobrazeno níže jako HeapArr:

HeapArr

Jak je uvedeno výše, HeapArr (0) je kořenem binární haldy. Ostatní prvky můžeme obecně představovat takto:

Pokud HeapArr (i) je ithuzel v binární haldě, pak indexy ostatních uzlů z ithuzly jsou:

  • HeapArr ((i-1) / 2) => Vrátí nadřazený uzel.
  • HeapArr ((2 * i) +1) => Vrátí levý podřízený uzel.
  • HeapArr ((2 * i) +2) => Vrátí pravý podřízený uzel.

Binární halda splňuje „objednávací vlastnost“, která je dvou typů, jak je uvedeno níže:

  • Vlastnost Min Heap: Minimální hodnota je v kořenovém adresáři a hodnota každého uzlu je větší nebo stejná jako jeho nadřazená položka.
  • Vlastnost Max. Haldy: Maximální hodnota je v kořenovém adresáři a hodnota každého uzlu je menší nebo stejná jako jeho nadřazená položka.

Operace na binární haldě

Následuje základní operace, které se provádějí na minimální hromadě. V případě maximální haldy se operace odpovídajícím způsobem obrátí.

# 1) Vložit () - Vloží nový klíč na konec stromu. V závislosti na hodnotě vloženého klíče možná budeme muset upravit haldu, aniž bychom porušili vlastnost haldy.

# 2) Odstranit () - Vymaže klíč. Poznámka že časová složitost operací vkládání a mazání haldy je O (log n).

# 3) poklesKey () - Snižuje hodnotu klíče. Při této operaci možná budeme muset udržovat vlastnost haldy. Časová složitost operace changeKey haldy je také O (log n).

# 4) extractMin () - Odstraní minimální prvek z haldy min. Po odebrání minimálního prvku potřebuje udržovat vlastnost haldy. Jeho časová složitost je tedy O (log n).

# 5) getMin () - Vrátí kořenový prvek min haldy. Toto je nejjednodušší operace a časová složitost pro tuto operaci je O (1).

Implementace haldy datové struktury

Níže je uvedena implementace C ++, která demonstruje základní funkce 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ýstup:

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

kořen haldy: 2

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

minimální prvek v haldě: 2

nový kořen haldy po snížení Klíč: 1

Výstup haldy

Aplikace hromád

  • Heapsort: Algoritmus Heapsort je efektivně implementován pomocí binární haldy.
  • Prioritní fronty: Binární halda podporuje všechny operace potřebné pro úspěšnou implementaci prioritních front v čase O (log n).
  • Algoritmy grafů: Některé z algoritmů souvisejících s grafy používají prioritní frontu a prioritní fronta zase používá binární haldu.
  • Nejhorší složitost algoritmu quicksort lze překonat pomocí heap sort.

Závěr

V tomto tutoriálu jsme viděli dvě datové struktury, tj. AVL stromy a Heap třídění podrobně.

Stromy AVL jsou vyvážené binární stromy, které se většinou používají při indexování databáze.

Všechny operace prováděné na stromech AVL jsou podobné jako u binárních vyhledávacích stromů, ale jediný rozdíl v případě stromů AVL spočívá v tom, že musíme udržovat faktor rovnováhy, tj. Datová struktura by měla zůstat vyváženým stromem v důsledku různých operací. Toho je dosaženo použitím operace AVL Tree Rotation.

Haldy jsou kompletní binární stromové struktury, které jsou klasifikovány jako min. Haldy nebo max. Haldy. Min-heap má minimální prvek jako kořen a následující uzly jsou větší nebo stejné jako jejich nadřazený uzel. V max-haldě je situace přesně opačná, tj. Maximální prvek je kořen haldy.

Hromady mohou být reprezentovány ve formě polí s 0thprvek jako kořen stromu. Struktury dat haldy se používají hlavně k implementaci front haldy a priorit.

=> Navštivte zde a dozvíte se C ++ od nuly.

Doporučené čtení

^