avl tree heap data structure c
Ce didacticiel fournit une explication détaillée des arborescences AVL et de la structure des données de tas en C ++ ainsi que des exemples d'arborescence AVL pour une meilleure compréhension:
AVL Tree est un arbre binaire à hauteur équilibrée. Chaque nœud est associé à un facteur équilibré qui est calculé comme la différence entre la hauteur de son sous-arbre gauche et du sous-arbre droit.
L'arbre AVL est nommé d'après ses deux inventeurs, à savoir G.M. Abelson-Velvety et E.M. Landis, et a été publié en 1962 dans leur article «Un algorithme pour l'organisation de l'information».
=> Recherchez la série complète de formations C ++ ici.
Ce que vous apprendrez:
Arborescence AVL en C ++
Pour que l'arbre soit équilibré, le facteur d'équilibre pour chaque nœud doit être compris entre -1 et 1. Sinon, l'arbre deviendra déséquilibré.
Un exemple d'arborescence AVL est illustré ci-dessous.
Dans l'arborescence ci-dessus, nous pouvons remarquer que la différence de hauteur des sous-arbres gauche et droit est de 1. Cela signifie qu'il s'agit d'un BST équilibré. Comme le facteur d'équilibrage est 1, cela signifie que le sous-arbre gauche est un niveau plus haut que le sous-arbre droit.
Si le facteur d'équilibrage est 0, cela signifie que les sous-arbres gauche et droit sont au même niveau, c'est-à-dire qu'ils contiennent une hauteur égale. Si le facteur d'équilibrage est -1, alors le sous-arbre gauche est un niveau plus bas que le sous-arbre droit.
L'arbre AVL contrôle la hauteur d'un arbre de recherche binaire et l'empêche de devenir biaisé. Parce que lorsqu'un arbre binaire devient biaisé, c'est le pire des cas (O (n)) pour toutes les opérations. En utilisant le facteur d'équilibre, l'arbre AVL impose une limite à l'arbre binaire et conserve ainsi toutes les opérations en O (log n).
Opérations dans l'arborescence AVL
Voici les opérations prises en charge par les arborescences AVL.
# 1) Insertion d'arbre AVL
L'opération d'insertion dans l'arborescence AVL C ++ est la même que celle de l'arborescence de recherche binaire. La seule différence est que pour maintenir le facteur d’équilibre, nous devons faire pivoter l’arbre vers la gauche ou la droite pour qu’il ne se déséquilibre pas.
# 2) Suppression de l'arborescence AVL
L'opération de suppression est également effectuée de la même manière que l'opération de suppression dans une arborescence de recherche binaire. Encore une fois, nous devons rééquilibrer l'arbre en effectuant des rotations AVL Tree.
Implémentation de l'arborescence AVL
Voici le programme C ++ pour illustrer l'arborescence AVL et ses opérations.
// 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 Production:
La traversée dans l'ordre pour l'arborescence AVL est:
4 5 8 11 12 17 18
Traversée en ordre après suppression du nœud 5:
4 8 11 12 17 18
Notez que nous avons utilisé l'exemple d'arborescence ci-dessus pour illustrer l'arborescence AVL dans le programme.
Applications des arbres AVL
- Les arborescences AVL sont principalement utilisées pour les sortes d'ensembles et de dictionnaires en mémoire.
- Les arborescences AVL sont également largement utilisées dans les applications de base de données dans lesquelles les insertions et les suppressions sont moins nombreuses mais où les recherches de données sont fréquentes.
- Il est utilisé dans les applications qui nécessitent une recherche améliorée en dehors des applications de base de données .
Structure de données HEAP en C ++
Un tas en C ++ est une structure de données spéciale basée sur une arborescence et est un arbre binaire complet.
Les tas peuvent être de deux types:
- Min-tas : Dans min-heap, le plus petit élément est la racine de l'arborescence et chaque nœud est supérieur ou égal à son parent.
- Max-tas : Dans max-heap, l'élément le plus grand est la racine de l'arborescence et chaque nœud est inférieur ou égal à son parent.
Considérez le tableau d'éléments suivant:
10 20 30 40 50 60 70
Le tas min pour les données ci-dessus est représenté ci-dessous:
Le tas maximum utilisant les données ci-dessus est indiqué ci-dessous:
Tas binaire C ++
Un tas binaire est l'implémentation courante d'une structure de données de tas.
Un tas binaire a les propriétés suivantes:
- C'est un arbre binaire complet lorsque tous les niveaux sont complètement remplis sauf peut-être le dernier niveau et le dernier niveau a ses clés le plus à gauche possible.
- Un tas binaire peut être un tas min ou max.
Un tas binaire est un arbre binaire complet et peut donc être représenté au mieux sous forme de tableau.
Examinons la représentation tableau du tas binaire.
Considérez le tas binaire suivant.
Dans le diagramme ci-dessus, le parcours du tas binaire est appelé ordre de niveau.
Ainsi, le tableau pour le tas binaire ci-dessus est affiché ci-dessous comme HeapArr:
Comme indiqué ci-dessus, HeapArr (0) est la racine du tas binaire. Nous pouvons représenter les autres éléments en termes généraux comme suit:
Si HeapArr (i) est un ienœud dans un tas binaire, puis les index des autres nœuds du ienoeud sont:
- HeapArr ((i-1) / 2) => Renvoie le nœud parent.
- HeapArr ((2 * i) +1) => Renvoie le nœud enfant gauche.
- HeapArr ((2 * i) +2) => Renvoie le nœud enfant droit.
Le tas binaire satisfait la «propriété de commande» qui est de deux types comme indiqué ci-dessous:
- Propriété Min Heap: La valeur minimale est à la racine et la valeur de chaque nœud est supérieure ou égale à son parent.
- Propriété Max Heap: La valeur maximale est à la racine et la valeur de chaque nœud est inférieure ou égale à son parent.
Opérations sur le tas binaire
Voici les opérations de base qui sont effectuées sur un tas minimum. Dans le cas du tas maximum, les opérations s'inversent en conséquence.
# 1) Insérer () - Insère une nouvelle clé à la fin de l'arborescence. Selon la valeur de la clé insérée, nous devrons peut-être ajuster le tas, sans violer la propriété du tas.
# 2) Supprimer () - Supprime une clé. Noter que la complexité temporelle des opérations d'insertion et de suppression du tas est O (log n).
# 3) diminutionClé () - Diminue la valeur de la clé. Nous pourrions avoir besoin de conserver la propriété de tas lorsque cette opération a lieu. La complexité temporelle de l'opération de diminutionKey du tas est également O (log n).
# 4) extraitMin () - Supprime l'élément minimum du min-heap. Il doit conserver la propriété du tas après avoir supprimé l'élément minimum. Ainsi sa complexité temporelle est O (log n).
# 5) getMin () - Renvoie l'élément racine du tas min. Il s'agit de l'opération la plus simple et la complexité temporelle de cette opération est O (1).
Implémentation de la structure de données du tas
Vous trouverez ci-dessous l'implémentation C ++ pour illustrer les fonctionnalités de base de 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: '< Production:
Tas après insertion: 2 4 6 8 10 12
racine du tas: 2
Tas après deletekey (2): 2 4 12 8 10
élément minimum dans le tas: 2
quels programmes peuvent ouvrir un fichier dwg
nouvelle racine du tas après diminution Clé: 1
Applications des tas
- Heapsort: L'algorithme Heapsort est efficacement implémenté à l'aide d'un tas binaire.
- Files d'attente prioritaires: Le tas binaire prend en charge toutes les opérations requises pour implémenter avec succès les files d'attente prioritaires en temps O (log n).
- Algorithmes graphiques: Certains des algorithmes liés aux graphiques utilisent la file d'attente prioritaire et, à son tour, la file d'attente prioritaire utilise le tas binaire.
- La complexité du pire des cas de l'algorithme de tri rapide peut être surmontée en utilisant le tri de tas.
Conclusion
Dans ce tutoriel, nous avons vu en détail deux structures de données, à savoir les arbres AVL et le tri Heap.
Les arborescences AVL sont des arborescences binaires équilibrées qui sont principalement utilisées dans l'indexation de bases de données.
Toutes les opérations effectuées sur les arbres AVL sont similaires à celles des arbres de recherche binaires, mais la seule différence dans le cas des arbres AVL est que nous devons maintenir le facteur d'équilibre, c'est-à-dire que la structure de données doit rester un arbre équilibré à la suite de diverses opérations. Ceci est réalisé en utilisant l'opération AVL Tree Rotation.
Les tas sont des structures arborescentes binaires complètes qui sont classées en tas min ou tas max. Min-heap a l'élément minimum comme racine et les nœuds suivants sont supérieurs ou égaux à leur nœud parent. Dans max-heap, la situation est exactement opposée, c'est-à-dire que l'élément maximum est la racine du tas.
Les tas peuvent être représentés sous forme de tableaux avec le 0eélément comme racine de l'arbre. Les structures de données de tas sont principalement utilisées pour implémenter le tri de tas et les files d'attente de priorité.
=> Visitez ici pour apprendre le C ++ à partir de zéro.
lecture recommandée
- Structure de données de file d'attente en C ++ avec illustration
- Empiler la structure de données en C ++ avec illustration
- Structure de données de liste liée circulaire en C ++ avec illustration
- Structure de données de liste liée en C ++ avec illustration
- Introduction aux structures de données en C ++
- Structure de données de file d'attente prioritaire en C ++ avec illustration
- Structure de données de liste doublement liée en C ++ avec illustration
- Tri de tas en C ++ avec des exemples
