avl tree heap data structure c
Dieses Lernprogramm enthält eine detaillierte Erläuterung der AVL-Bäume und der Heap-Datenstruktur in C ++ sowie Beispiele für AVL-Bäume zum besseren Verständnis:
AVL Tree ist ein höhenausgeglichener Binärbaum. Jedem Knoten ist ein ausgeglichener Faktor zugeordnet, der als Differenz zwischen der Höhe seines linken Teilbaums und des rechten Teilbaums berechnet wird.
Der AVL-Baum ist nach seinen zwei Erfindern benannt, d. H. G.M. Abelson-Velvety und E. M. Landis und wurde 1962 in ihrer Arbeit „Ein Algorithmus zur Organisation von Informationen“ veröffentlicht.
=> Suchen Sie hier nach der gesamten C ++ - Schulungsserie.
Was du lernen wirst:
AVL-Baum in C ++
Damit der Baum ausgeglichen wird, sollte der ausgeglichene Faktor für jeden Knoten zwischen -1 und 1 liegen. Wenn nicht, wird der Baum nicht ausgeglichen.
Ein Beispiel für einen AVL-Baum ist unten dargestellt.
Im obigen Baum können wir feststellen, dass der Höhenunterschied zwischen dem linken und dem rechten Teilbaum 1 beträgt. Dies bedeutet, dass es sich um eine ausgeglichene BST handelt. Da der Ausgleichsfaktor 1 ist, bedeutet dies, dass der linke Teilbaum eine Ebene höher ist als der rechte Teilbaum.
Wenn der Ausgleichsfaktor 0 ist, bedeutet dies, dass sich der linke und der rechte Teilbaum auf derselben Ebene befinden, d. H. Sie enthalten die gleiche Höhe. Wenn der Ausgleichsfaktor -1 ist, ist der linke Teilbaum eine Ebene niedriger als der rechte Teilbaum.
Der AVL-Baum steuert die Höhe eines binären Suchbaums und verhindert, dass dieser verzerrt wird. Denn wenn ein Binärbaum schief wird, ist dies der schlechteste Fall (O (n)) für alle Operationen. Durch die Verwendung des Ausgleichsfaktors setzt der AVL-Baum dem Binärbaum eine Grenze und hält somit alle Operationen auf O (log n).
AVL-Baumoperationen
Die folgenden Vorgänge werden von AVL-Bäumen unterstützt.
# 1) AVL-Baumeinfügung
Die Einfügeoperation im C ++ AVL-Baum entspricht der des binären Suchbaums. Der einzige Unterschied besteht darin, dass wir den Baum nach links oder rechts drehen müssen, um den Ausgleichsfaktor aufrechtzuerhalten, damit er nicht aus dem Gleichgewicht gerät.
j2ee Interviewfragen für leitende Entwickler
# 2) Löschen des AVL-Baums
Der Löschvorgang wird ebenfalls auf die gleiche Weise ausgeführt wie der Löschvorgang in einem binären Suchbaum. Wieder müssen wir den Baum neu ausbalancieren, indem wir einige AVL-Baumrotationen durchführen.
AVL-Baumimplementierung
Im Folgenden finden Sie das C ++ - Programm zur Demonstration des AVL-Baums und seiner Operationen.
// 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 Ausgabe:
Die Inorder Traversal für den AVL-Baum lautet:
4 5 8 11 12 17 18
Inorder Traversal nach Löschung von Knoten 5:
4 8 11 12 17 18
Beachten Sie, dass wir den oben gezeigten Beispielbaum verwendet haben, um den AVL-Baum im Programm zu demonstrieren.
Anwendungen von AVL-Bäumen
- AVL-Bäume werden hauptsächlich für speicherinterne Arten von Mengen und Wörterbüchern verwendet.
- AVL-Bäume werden auch häufig in Datenbankanwendungen verwendet, in denen weniger Einfügungen und Löschungen erforderlich sind, jedoch häufig nach Daten gesucht werden muss.
- Es wird in Anwendungen verwendet, die neben den Datenbankanwendungen eine verbesserte Suche erfordern .
HEAP-Datenstruktur in C ++
Ein Heap in C ++ ist eine spezielle baumbasierte Datenstruktur und ein vollständiger Binärbaum.
Es gibt zwei Arten von Haufen:
- Min-Haufen : In min-heap ist das kleinste Element die Wurzel des Baums und jeder Knoten ist größer oder gleich seinem übergeordneten Knoten.
- Max-Haufen : In max-heap ist das größte Element die Wurzel des Baums und jeder Knoten ist kleiner oder gleich seinem übergeordneten Knoten.
Betrachten Sie das folgende Array von Elementen:
10 20 30 40 50 60 70
Der Min-Heap für die obigen Daten ist unten dargestellt:
Der maximale Heap unter Verwendung der obigen Daten ist unten gezeigt:
Binärer Heap C ++
Ein binärer Heap ist die übliche Implementierung einer Heap-Datenstruktur.
Ein binärer Heap hat die folgenden Eigenschaften:
- Es ist ein vollständiger Binärbaum, wenn alle Ebenen bis auf die letzte Ebene vollständig gefüllt sind und die letzte Ebene so viele Schlüssel wie möglich übrig hat.
- Ein binärer Heap kann ein Min-Heap oder ein Max-Heap sein.
Ein binärer Heap ist ein vollständiger binärer Baum und kann daher am besten als Array dargestellt werden.
Schauen wir uns die Array-Darstellung des binären Heaps an.
Betrachten Sie den folgenden binären Heap.
Im obigen Diagramm wird das Durchlaufen des binären Heaps als Ebenenreihenfolge bezeichnet.
Daher wird das Array für den obigen binären Heap unten als HeapArr angezeigt:
Wie oben gezeigt, ist HeapArr (0) die Wurzel des binären Heaps. Wir können die anderen Elemente allgemein wie folgt darstellen:
Wenn HeapArr (i) ein i istthKnoten in einem binären Heap, dann die Indizes der anderen Knoten aus dem ithKnoten sind:
- HeapArr ((i-1) / 2) => Gibt den übergeordneten Knoten zurück.
- HeapArr ((2 * i) +1) => Gibt den linken untergeordneten Knoten zurück.
- HeapArr ((2 * i) +2) => Gibt den rechten untergeordneten Knoten zurück.
Der binäre Heap erfüllt die 'Ordnungs-Eigenschaft', die von zwei Typen ist, wie unten angegeben:
wie man ein Array von Strings macht
- Min Heap Eigenschaft: Der Mindestwert befindet sich an der Wurzel und der Wert jedes Knotens ist größer oder gleich seinem übergeordneten Knoten.
- Max Heap-Eigenschaft: Der Maximalwert befindet sich im Stammverzeichnis und der Wert jedes Knotens ist kleiner oder gleich dem übergeordneten Knoten.
Operationen auf binärem Heap
Das Folgende sind die grundlegenden Operationen, die auf minimalem Heap ausgeführt werden. Im Falle des maximalen Heaps kehren sich die Operationen entsprechend um.
# 1) Einfügen () - Fügt am Ende des Baums einen neuen Schlüssel ein. Abhängig vom Wert des eingefügten Schlüssels müssen wir möglicherweise den Heap anpassen, ohne die Heap-Eigenschaft zu verletzen.
# 2) Löschen () - Löscht einen Schlüssel. Hinweis dass die zeitliche Komplexität sowohl der Einfüge- als auch der Löschoperationen des Heaps O ist (log n).
# 3) verringernKey () - Verringert den Wert des Schlüssels. Möglicherweise müssen wir die Heap-Eigenschaft beibehalten, wenn dieser Vorgang ausgeführt wird. Die zeitliche Komplexität der AbnahmeKey-Operation des Heaps ist ebenfalls O (log n).
# 4) extractMin () - Entfernt das minimale Element aus dem Min-Heap. Nach dem Entfernen des minimalen Elements muss die Heap-Eigenschaft beibehalten werden. Somit ist seine zeitliche Komplexität O (log n).
# 5) getMin () - Gibt das Stammelement des Min-Heaps zurück. Dies ist die einfachste Operation und die zeitliche Komplexität für diese Operation ist O (1).
Implementierung der Heap-Datenstruktur
Im Folgenden wird die C ++ - Implementierung angegeben, um die grundlegende Funktionalität von min-heap zu demonstrieren.
#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: '< Ausgabe:
Haufen nach dem Einsetzen: 2 4 6 8 10 12
Wurzel des Haufens: 2
Heap nach Löschtaste (2): 2 4 12 8 10
Mindestelement im Heap: 2
neue Wurzel des Haufens nach AbnahmeKey: 1
Anwendungen von Haufen
- Heapsort: Der Heapsort-Algorithmus wird effektiv unter Verwendung eines binären Heaps implementiert.
- Prioritätswarteschlangen: Der binäre Heap unterstützt alle Vorgänge, die für die erfolgreiche Implementierung der Prioritätswarteschlangen in der Zeit O (log n) erforderlich sind.
- Graph-Algorithmen: Einige der Algorithmen, die sich auf Diagramme beziehen, verwenden eine Prioritätswarteschlange, und die Prioritätswarteschlange verwendet wiederum einen binären Heap.
- Die Komplexität des Quicksort-Algorithmus im schlimmsten Fall kann durch Verwendung der Heap-Sortierung überwunden werden.
Fazit
In diesem Tutorial haben wir zwei Datenstrukturen gesehen, d. H. AVL-Bäume und Heap-Sortierung im Detail.
AVL-Bäume sind ausgeglichene Binärbäume, die hauptsächlich bei der Datenbankindizierung verwendet werden.
Alle Operationen, die an AVL-Bäumen ausgeführt werden, ähneln denen von binären Suchbäumen, aber der einzige Unterschied im Fall von AVL-Bäumen besteht darin, dass wir den Ausgleichsfaktor beibehalten müssen, d. H. Die Datenstruktur sollte aufgrund verschiedener Operationen ein ausgeglichener Baum bleiben. Dies wird durch Verwendung der AVL-Baumrotationsoperation erreicht.
Heaps sind vollständige binäre Baumstrukturen, die in Min-Heap oder Max-Heap klassifiziert sind. Min-Heap hat das Minimum-Element als Wurzel und die nachfolgenden Knoten sind größer oder gleich ihrem übergeordneten Knoten. In max-heap ist die Situation genau umgekehrt, d. H. Das maximale Element ist die Wurzel des Heaps.
Heaps können in Form von Arrays mit der 0 dargestellt werdenthElement als Wurzel des Baumes. Heap-Datenstrukturen werden hauptsächlich zum Implementieren von Heap-Sortier- und Prioritätswarteschlangen verwendet.
=> Besuchen Sie hier, um C ++ von Grund auf neu zu lernen.
Literatur-Empfehlungen
- Warteschlangendatenstruktur in C ++ mit Illustration
- Stapeldatenstruktur in C ++ mit Illustration
- Datenstruktur für zirkuläre verknüpfte Listen in C ++ mit Abbildung
- Datenstruktur der verknüpften Liste in C ++ mit Abbildung
- Einführung in Datenstrukturen in C ++
- Datenstruktur der Prioritätswarteschlange in C ++ mit Abbildung
- Doppelt verknüpfte Listendatenstruktur in C ++ mit Abbildung
- Heap-Sortierung in C ++ mit Beispielen
