avl tree heap data structure c
Αυτό το σεμινάριο παρέχει μια λεπτομερή επεξήγηση των δέντρων AVL και της δομής δεδομένων σωρού στο C ++ μαζί με παραδείγματα δέντρων AVL για καλύτερη κατανόηση:
Το AVL Tree είναι ένα δυαδικό δέντρο ισορροπημένου ύψους. Κάθε κόμβος σχετίζεται με έναν ισορροπημένο παράγοντα που υπολογίζεται ως η διαφορά μεταξύ του ύψους του αριστερού υποδέντρου και του δεξιού υποδέντρου.
Το δέντρο AVL πήρε το όνομά του από τους δύο εφευρέτες του, δηλαδή το G.M. Abelson-Velvety και E.M. Landis, και δημοσιεύθηκε το 1962 στην εφημερίδα τους «Ένας αλγόριθμος για την οργάνωση των πληροφοριών».
=> Αναζητήστε ολόκληρη τη σειρά προπόνησης C ++ εδώ.
Τι θα μάθετε:
Δέντρο AVL σε C ++
Για να είναι ισορροπημένο το δέντρο, ο ισορροπημένος συντελεστής για κάθε κόμβο πρέπει να είναι μεταξύ -1 και 1. Εάν όχι, το δέντρο θα γίνει ανισορροπημένο.
Ένα παράδειγμα AVL Tree φαίνεται παρακάτω.
Στο παραπάνω δέντρο, μπορούμε να παρατηρήσουμε ότι η διαφορά στα ύψη του αριστερού και του δεξιού υποδένδρου είναι 1. Αυτό σημαίνει ότι είναι ένα ισορροπημένο BST. Καθώς ο συντελεστής εξισορρόπησης είναι 1, αυτό σημαίνει ότι το αριστερό υποδένδρο είναι ένα επίπεδο υψηλότερο από το δεξιό υποδένδρο.
Εάν ο συντελεστής εξισορρόπησης είναι 0, τότε σημαίνει ότι το αριστερό και το δεξί υπόφυτο βρίσκονται στο ίδιο επίπεδο, δηλαδή περιέχουν ίσο ύψος. Εάν ο συντελεστής εξισορρόπησης είναι -1, τότε το αριστερό υποδένδρο είναι ένα επίπεδο χαμηλότερο από το δεξιό υποδένδρο.
Το δέντρο AVL ελέγχει το ύψος ενός δέντρου δυαδικής αναζήτησης και το αποτρέπει από το να στρέψει. Διότι όταν ένα δυαδικό δέντρο γίνεται λοξό, είναι η χειρότερη περίπτωση (O (n)) για όλες τις λειτουργίες. Χρησιμοποιώντας τον συντελεστή ισορροπίας, το δέντρο AVL επιβάλλει ένα όριο στο δυαδικό δέντρο και έτσι διατηρεί όλες τις λειτουργίες στο O (log n).
Λειτουργίες δέντρων AVL
Ακολουθούν οι λειτουργίες που υποστηρίζονται από δέντρα AVL.
# 1) Εισαγωγή AVL Tree
Εισαγωγή λειτουργίας στο δέντρο C ++ AVL είναι η ίδια με αυτή του δέντρου δυαδικής αναζήτησης. Η μόνη διαφορά είναι ότι για να διατηρηθεί ο συντελεστής ισορροπίας, πρέπει να περιστρέψουμε το δέντρο προς τα αριστερά ή προς τα δεξιά, ώστε να μην γίνει ισορροπημένο.
# 2) Διαγραφή δέντρων AVL
Η λειτουργία διαγραφής εκτελείται επίσης με τον ίδιο τρόπο όπως η λειτουργία διαγραφής σε ένα δέντρο δυαδικής αναζήτησης. Και πάλι πρέπει να εξισορροπήσουμε το δέντρο εκτελώντας μερικές περιστροφές δέντρων AVL.
Υλοποίηση δέντρου AVL
Ακολουθεί το πρόγραμμα C ++ για την επίδειξη του δέντρου AVL και των λειτουργιών του.
// 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 Παραγωγή:
Το Inorder traversal για το δέντρο AVL είναι:
4 5 8 11 12 17 18
Διασταύρωση ενδιάμεσου μετά τη διαγραφή του κόμβου 5:
ποια προγράμματα μπορούν να ανοίξουν αρχεία eps
4 8 11 12 17 18
Σημειώστε ότι χρησιμοποιήσαμε το παράδειγμα δέντρου που εμφανίζεται παραπάνω για να δείξουμε το δέντρο AVL στο πρόγραμμα.
Εφαρμογές των δέντρων AVL
- Τα δέντρα AVL χρησιμοποιούνται κυρίως για είδη σετ και λεξικά στη μνήμη.
- Τα δέντρα AVL χρησιμοποιούνται επίσης εκτενώς σε εφαρμογές βάσης δεδομένων στις οποίες οι εισαγωγές και οι διαγραφές είναι λιγότερες, αλλά υπάρχουν συχνές αναζητήσεις για δεδομένα που απαιτούνται.
- Χρησιμοποιείται σε εφαρμογές που απαιτούν βελτιωμένη αναζήτηση εκτός από τις εφαρμογές βάσης δεδομένων .
Δομή δεδομένων HEAP σε C ++
Ένας σωρός στο C ++ είναι μια ειδική δομή δεδομένων που βασίζεται σε δέντρα και είναι ένα πλήρες δυαδικό δέντρο.
Οι σωροί μπορούν να είναι δύο τύπων:
- Ελάχιστο σωρό : Στο ελάχιστο σωρό, το μικρότερο στοιχείο είναι η ρίζα του δέντρου και κάθε κόμβος είναι μεγαλύτερος ή ίσος με τον γονέα του.
- Μέγιστος σωρός : Στο μέγιστο σωρό, το μεγαλύτερο στοιχείο είναι η ρίζα του δέντρου και κάθε κόμβος είναι μικρότερος ή ίσος με τον γονέα του.
Εξετάστε την ακόλουθη σειρά στοιχείων:
10 20 30 40 50 60 70
Το ελάχιστο σωρό για τα παραπάνω δεδομένα παρουσιάζεται παρακάτω:
Ο μέγιστος σωρός χρησιμοποιώντας τα παραπάνω δεδομένα φαίνεται παρακάτω:
Δυαδικός σωρός C ++
Ένας δυαδικός σωρός είναι η κοινή εφαρμογή μιας δομής δεδομένων σωρού.
Ένας δυαδικός σωρός έχει τις ακόλουθες ιδιότητες:
- Είναι ένα πλήρες δυαδικό δέντρο όταν όλα τα επίπεδα γεμίζουν εντελώς εκτός από το τελευταίο επίπεδο και το τελευταίο επίπεδο έχει τα κλειδιά του όσο το δυνατόν περισσότερο.
- Ένας δυαδικός σωρός μπορεί να είναι ένας ελάχιστος σωρός ή ένας μέγιστος σωρός.
Ένας δυαδικός σωρός είναι ένα πλήρες δυαδικό δέντρο και έτσι μπορεί καλύτερα να αναπαρασταθεί ως πίνακας.
Ας δούμε την παράσταση του δυαδικού σωρού.
Εξετάστε τον ακόλουθο δυαδικό σωρό.
Στο παραπάνω διάγραμμα, η διασταύρωση του δυαδικού σωρού ονομάζεται επίπεδο σειράς.
Έτσι, ο πίνακας για τον παραπάνω δυαδικό σωρό εμφανίζεται παρακάτω ως HeapArr:
Όπως φαίνεται παραπάνω, το HeapArr (0) είναι η ρίζα του δυαδικού σωρού. Μπορούμε να αντιπροσωπεύσουμε τα άλλα στοιχεία σε γενικούς όρους ως εξής:
Εάν το HeapArr (i) είναι ένα iουκόμβος σε δυαδικό σωρό, στη συνέχεια τα ευρετήρια των άλλων κόμβων από το iουο κόμβος είναι:
- HeapArr ((i-1) / 2) => Επιστρέφει τον γονικό κόμβο.
- HeapArr ((2 * i) +1) => Επιστρέφει τον αριστερό θυγατρικό κόμβο.
- HeapArr ((2 * i) +2) => Επιστρέφει τον σωστό θυγατρικό κόμβο.
Ο δυαδικός σωρός ικανοποιεί την 'ιδιότητα παραγγελίας' που είναι δύο τύπων όπως αναφέρεται παρακάτω:
- Ελάχιστη ιδιότητα: Η ελάχιστη τιμή βρίσκεται στη ρίζα και η τιμή κάθε κόμβου είναι μεγαλύτερη ή ίση με τη μητρική του.
- Μέγιστη ιδιότητα Heap: Η μέγιστη τιμή βρίσκεται στη ρίζα και η τιμή κάθε κόμβου είναι μικρότερη ή ίση με τη μητρική του.
Λειτουργίες στο δυαδικό σωρό
Ακολουθούν οι βασικές λειτουργίες που πραγματοποιούνται με ελάχιστο σωρό. Στην περίπτωση του μέγιστου σωρού, οι λειτουργίες αντιστρέφονται ανάλογα.
# 1) Εισαγωγή () - Εισάγει ένα νέο κλειδί στο τέλος του δέντρου. Ανάλογα με την τιμή του κλειδιού που έχει εισαχθεί, ενδέχεται να χρειαστεί να προσαρμόσουμε το σωρό, χωρίς να παραβιάσουμε την ιδιότητα σωρού.
# 2) Διαγραφή () - Διαγράφει ένα κλειδί. Σημείωση ότι η χρονική πολυπλοκότητα και των λειτουργιών εισαγωγής και διαγραφής του σωρού είναι O (log n).
Ανίχνευση διαρροής μνήμης c ++
# 3) μείωση Κλειδί () - Μειώνει την τιμή του κλειδιού. Ίσως χρειαστεί να διατηρήσουμε την ιδιότητα σωρού όταν πραγματοποιείται αυτή η λειτουργία. Η χρονική πολυπλοκότητα της μείωσης Η βασική λειτουργία του σωρού είναι επίσης O (log n).
# 4) απόσπασμα Min () - Αφαιρεί το ελάχιστο στοιχείο από το ελάχιστο σωρό. Πρέπει να διατηρήσει την ιδιότητα σωρού μετά την αφαίρεση του ελάχιστου στοιχείου. Έτσι, η χρονική πολυπλοκότητά του είναι O (log n).
# 5) getMin () - Επιστρέφει το ριζικό στοιχείο του ελάχιστου σωρού. Αυτή είναι η απλούστερη λειτουργία και η χρονική πολυπλοκότητα αυτής της λειτουργίας είναι O (1).
Υλοποίηση δομής δεδομένων σωρού
Δίνεται παρακάτω η εφαρμογή C ++ για να δείξει τη βασική λειτουργικότητα του 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: '< Παραγωγή:
Σωρός μετά την εισαγωγή: 2 4 6 8 10 12
ρίζα του σωρού: 2
Σωρός μετά από deletekey (2): 2 4 12 8 10
ελάχιστο στοιχείο στο σωρό: 2
νέα ρίζα του σωρού μετά τη μείωση Πλήκτρο: 1
Εφαρμογές σωρών
- Χάψορτ: Ο αλγόριθμος Heapsort εφαρμόζεται αποτελεσματικά χρησιμοποιώντας ένα δυαδικό σωρό.
- Ουρές προτεραιότητας: Ο δυαδικός σωρός υποστηρίζει όλες τις λειτουργίες που απαιτούνται για την επιτυχή εφαρμογή των ουρών προτεραιότητας σε χρόνο O (log n).
- Αλγόριθμοι γραφημάτων: Μερικοί από τους αλγόριθμους που σχετίζονται με γραφήματα χρησιμοποιούν ουρά προτεραιότητας και με τη σειρά τους, η ουρά προτεραιότητας χρησιμοποιεί δυαδικό σωρό.
- Η χειρότερη περίπτωση της πολυπλοκότητας του αλγορίθμου γρήγορης ταξινόμησης μπορεί να ξεπεραστεί χρησιμοποιώντας το είδος σωρού.
συμπέρασμα
Σε αυτό το σεμινάριο, έχουμε δει δύο δομές δεδομένων, δηλ. Τα δέντρα AVL και το Heap ταξινομούν λεπτομερώς.
Τα δέντρα AVL είναι ισορροπημένα δυαδικά δέντρα που χρησιμοποιούνται κυρίως στην ευρετηρίαση βάσης δεδομένων.
Όλες οι λειτουργίες που εκτελούνται σε δέντρα AVL είναι παρόμοιες με εκείνες των δέντρων δυαδικής αναζήτησης, αλλά η μόνη διαφορά στην περίπτωση των δέντρων AVL είναι ότι πρέπει να διατηρήσουμε τον παράγοντα ισορροπίας, δηλ. Η δομή δεδομένων θα πρέπει να παραμείνει ισορροπημένο δέντρο ως αποτέλεσμα διαφόρων λειτουργιών. Αυτό επιτυγχάνεται χρησιμοποιώντας τη λειτουργία AVL Tree Rotation.
Οι σωροί είναι πλήρεις δυαδικές δομές δέντρων που ταξινομούνται σε min-heap ή max-heap. Το Min-heap έχει το ελάχιστο στοιχείο ως τη ρίζα του και οι επόμενοι κόμβοι είναι μεγαλύτεροι ή ίσοι με τον γονικό τους κόμβο. Στο μέγιστο σωρό, η κατάσταση είναι ακριβώς αντίθετη, δηλαδή το μέγιστο στοιχείο είναι η ρίζα του σωρού.
Οι σωροί μπορούν να αναπαρασταθούν με τη μορφή συστοιχιών με το 0ουστοιχείο ως η ρίζα του δέντρου. Οι δομές δεδομένων σωρού χρησιμοποιούνται κυρίως για την εφαρμογή ουρών ταξινόμησης και προτεραιότητας σωρού.
=> Επισκεφθείτε εδώ για να μάθετε C ++ από το μηδέν.
Συνιστώμενη ανάγνωση
- Δομή δεδομένων ουράς σε C ++ με απεικόνιση
- Δομή δεδομένων στοίβας σε C ++ με απεικόνιση
- Δομή δεδομένων κυκλικής συνδεδεμένης λίστας σε C ++ με απεικόνιση
- Δομή δεδομένων συνδεδεμένης λίστας σε C ++ με απεικόνιση
- Εισαγωγή στις δομές δεδομένων στο C ++
- Δομή δεδομένων ουράς προτεραιότητας σε C ++ με απεικόνιση
- Διπλά συνδεδεμένη δομή δεδομένων λίστας σε C ++ με απεικόνιση
- Ταξινόμηση σωρού σε C ++ με παραδείγματα
