avl tree heap data structure c
यह ट्यूटोरियल सी ++ में एवीएल पेड़ और हीप डेटा संरचना का एक विस्तृत विवरण प्रदान करता है। बेहतर समझने के लिए एवीएल ट्री उदाहरणों के साथ:
एवीएल ट्री एक ऊंचाई-संतुलित बाइनरी ट्री है। प्रत्येक नोड एक संतुलित कारक के साथ जुड़ा हुआ है, जिसे इसके बाएं सबट्री और राइट सबट्री की ऊंचाई के बीच अंतर के रूप में गणना की जाती है।
एवीएल वृक्ष का नाम इसके दो आविष्कारकों यानी जी.एम. एबेल्सन-वेलवेटी और ई.एम. लैंडिस, और 1962 में उनके पत्र 'सूचना के संगठन के लिए एक एल्गोरिथ्म' में प्रकाशित हुआ था।
=> संपूर्ण सी ++ प्रशिक्षण श्रृंखला यहां देखें।
ग्रहण में एक नया जावा प्रोजेक्ट बनाएं
आप क्या सीखेंगे:
एवीएल ट्री सी ++ में
पेड़ के संतुलित होने के लिए, प्रत्येक नोड के लिए संतुलित कारक -1 और 1 के बीच होना चाहिए। यदि पेड़ असंतुलित नहीं होगा।
एक उदाहरण AVL ट्री नीचे दिखाया गया है।
उपरोक्त पेड़ में, हम देख सकते हैं कि बाएँ और दाएँ सबटाइम्स की ऊँचाई में अंतर १ है। इसका मतलब है कि यह एक संतुलित BST है। जैसा कि संतुलन कारक 1 है, इसका मतलब यह है कि बायाँ उपप्रकार, सही उप-योग की तुलना में एक स्तर अधिक है।
यदि संतुलन कारक 0 है, तो इसका मतलब है कि बाएं और दाएं उपप्रकार समान स्तर पर हैं यानी उनमें समान ऊंचाई है। यदि बैलेंसिंग फैक्टर -1 है, तो लेफ्ट सबट्री, राइट सबट्री से एक लेवल कम है।
एवीएल पेड़ एक द्विआधारी खोज पेड़ की ऊंचाई को नियंत्रित करता है और यह इसे तिरछा होने से रोकता है। क्योंकि जब एक बाइनरी ट्री तिरछा हो जाता है, तो यह सभी ऑपरेशनों के लिए सबसे खराब स्थिति (O (n)) है। बैलेंस फैक्टर का उपयोग करके, एवीएल ट्री बाइनरी ट्री पर एक सीमा लगाता है और इस प्रकार ओ (लॉग एन) पर सभी ऑपरेशनों को चालू रखता है।
AVL ट्री संचालन
एवीएल पेड़ों द्वारा समर्थित संचालन निम्नलिखित हैं।
(1) एवीएल ट्री सम्मिलन
C ++ AVL ट्री में ऑपरेशन डालें बाइनरी सर्च ट्री के समान है। अंतर केवल इतना है कि बैलेंस फैक्टर को बनाए रखने के लिए, हमें पेड़ को बाएं या दाएं घुमाने की जरूरत है ताकि यह असंतुलित न हो।
# 2) एवीएल ट्री विलोपन
हटाए गए ऑपरेशन को भी उसी तरह से किया जाता है जैसे बाइनरी सर्च ट्री में डिलीट ऑपरेशन। फिर से हमें कुछ एवीएल ट्री रोटेशन का प्रदर्शन करके पेड़ को पुनर्जीवित करने की आवश्यकता है।
एवीएल ट्री कार्यान्वयन
एवीएल पेड़ और उसके संचालन को प्रदर्शित करने के लिए C ++ प्रोग्राम निम्नलिखित है।
// 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 आउटपुट:
एवीएल पेड़ के लिए इनवर्टर ट्रैवर्सल है:
४ ५ 17 ११ १२ १ 5 १ 17
नोड 5 को हटाने के बाद इनवर्टर ट्रैवर्सल:
4 8 11 12 17 18
ध्यान दें कि हमने प्रोग्राम में AVL ट्री को प्रदर्शित करने के लिए ऊपर दिखाए गए उदाहरण ट्री का उपयोग किया है।
एवीएल पेड़ों के अनुप्रयोग
- एवीएल पेड़ों का उपयोग ज्यादातर सेट और शब्दकोशों के इन-मेमोरी प्रकार के लिए किया जाता है।
- एवीएल पेड़ों का उपयोग बड़े पैमाने पर डेटाबेस अनुप्रयोगों में किया जाता है जिसमें सम्मिलन और विलोपन कम होते हैं लेकिन आवश्यक डेटा के लिए अक्सर लुकअप होते हैं।
- इसका उपयोग उन अनुप्रयोगों में किया जाता है जिन्हें डेटाबेस अनुप्रयोगों से अलग खोज में सुधार की आवश्यकता होती है ।
C ++ में HEAP डेटा संरचना
C ++ में एक ढेर एक विशेष पेड़-आधारित डेटा संरचना है और एक पूर्ण बाइनरी ट्री है।
ढेर दो प्रकार के हो सकते हैं:
- मिन-ढेर : न्यूनतम ढेर में, सबसे छोटा तत्व पेड़ की जड़ है और प्रत्येक नोड अपने माता-पिता से अधिक या बराबर है।
- मैक्स-ढेर : अधिकतम-ढेर में, सबसे बड़ा तत्व पेड़ की जड़ है और प्रत्येक नोड अपने माता-पिता से कम या बराबर है।
तत्वों के निम्नलिखित सरणी पर विचार करें:
10 20 30 40 50 60 70
उपरोक्त आंकड़ों के लिए न्यूनतम-ढेर का प्रतिनिधित्व नीचे किया गया है:
उपरोक्त डेटा का उपयोग करने वाला अधिकतम ढेर नीचे दिखाया गया है:
बाइनरी हीप सी ++
एक बाइनरी हीप एक ढेर डेटा संरचना का सामान्य कार्यान्वयन है।
एक बाइनरी हीप में निम्नलिखित गुण होते हैं:
- यह एक पूर्ण बाइनरी ट्री है जब संभवतः सभी स्तर पूरी तरह से भरे हुए होते हैं सिवाय संभवत: अंतिम स्तर और अंतिम स्तर की जितनी संभव हो उतनी अधिक कुंजियाँ शेष रह जाती हैं।
- एक बाइनरी हीप एक मिन-हीप या अधिकतम-ढेर हो सकता है।
एक बाइनरी हीप एक पूर्ण बाइनरी ट्री है और इस प्रकार यह एक सरणी के रूप में सबसे अच्छा प्रतिनिधित्व किया जा सकता है।
आइए बाइनरी हीप के सरणी प्रतिनिधित्व पर ध्यान दें।
निम्नलिखित बाइनरी हीप पर विचार करें।
उपरोक्त आरेख में, बाइनरी हीप के लिए ट्रावर्सल को स्तर आदेश कहा जाता है।
इस प्रकार उपरोक्त बाइनरी हीप के लिए सरणी को HeapArr के रूप में नीचे दिखाया गया है:
जैसा कि ऊपर दिखाया गया है, HeapArr (0) बाइनरी हीप की जड़ है। हम सामान्य रूप में अन्य तत्वों का प्रतिनिधित्व कर सकते हैं:
यदि HeapArr (i) एक i हैवेंएक बाइनरी हीप में नोड, फिर आई से अन्य नोड्स के सूचकांकवेंनोड हैं:
- HeapArr ((i-1) / 2) => मूल नोड लौटाता है।
- HeapArr ((2 * i) +1) => बाएं बच्चे का नोड लौटाता है।
- HeapArr ((2 * i) +2) => सही बाल नोड लौटाता है।
बाइनरी हीप 'ऑर्डरिंग प्रॉपर्टी' को संतुष्ट करता है, जो नीचे दिए गए अनुसार दो प्रकार का है:
- न्यूनतम हीप संपत्ति: न्यूनतम मान मूल में होता है और प्रत्येक नोड का मान उसके माता-पिता से अधिक या उसके बराबर होता है।
- अधिकतम हीप संपत्ति: अधिकतम मूल्य मूल में है और प्रत्येक नोड का मूल्य उसके माता-पिता से कम या बराबर है।
बाइनरी हीप पर संचालन
निम्नलिखित मूल संचालन हैं जो न्यूनतम ढेर पर किए जाते हैं। अधिकतम ढेर के मामले में, आपरेशन तदनुसार रिवर्स होते हैं।
# 1) डालें () - पेड़ के अंत में एक नई कुंजी लगाता है। डाले गए कुंजी के मूल्य के आधार पर, हमें ढेर संपत्ति का उल्लंघन किए बिना, ढेर को समायोजित करना पड़ सकता है।
# 2) हटाएं () - एक कुंजी हटाता है। ध्यान दें ढेर के दोनों सम्मिलित करने और हटाने के संचालन की समय जटिलता हे (लॉग एन) है।
# 3) घटाना () - कुंजी के मूल्य को घटाता है। जब यह ऑपरेशन होता है तो हमें ढेर संपत्ति को बनाए रखने की आवश्यकता हो सकती है। हीप के घटे संचालन की समय जटिलता O (लॉग एन) भी है।
# 4) एक्स्ट्रीमिन () - मिन-हीप से न्यूनतम तत्व निकालता है। इसे न्यूनतम तत्व को हटाने के बाद ढेर संपत्ति को बनाए रखने की आवश्यकता है। इस प्रकार इसकी समय जटिलता हे (लॉग एन) है।
# 5) getMin () - मिन-ढेर के मूल तत्व को वापस करता है। यह सबसे सरल ऑपरेशन है और इस ऑपरेशन की समय जटिलता O (1) है।
हीप डेटा स्ट्रक्चर इम्प्लीमेंटेशन
नीचे दिए गए मिन-हीप की बुनियादी कार्यक्षमता को प्रदर्शित करने के लिए C ++ कार्यान्वयन है।
#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
हटाने के बाद हीप (2): 2 4 12 8 10
ढेर में न्यूनतम तत्व: 2
कैसे देखें
कमी के बाद ढेर की नई जड़: १
हीप्स के अनुप्रयोग
- ढेर बनाएं और छांटें: हीप्सर्ट एल्गोरिथ्म एक बाइनरी हीप का उपयोग करके प्रभावी ढंग से लागू किया गया है।
- प्राथमिकता कतार: बाइनरी हीप ओ (लॉग एन) समय में प्राथमिकता कतारों को सफलतापूर्वक लागू करने के लिए आवश्यक सभी कार्यों का समर्थन करता है।
- ग्राफ़ एल्गोरिदम: ग्राफ़ से संबंधित कुछ एल्गोरिदम प्राथमिकता कतार का उपयोग करते हैं और बदले में, प्राथमिकता कतार बाइनरी हीप का उपयोग करती है।
- Quicksort एल्गोरिथ्म का सबसे खराब मामला जटिलता हीप सॉर्ट का उपयोग करके दूर किया जा सकता है।
निष्कर्ष
इस ट्यूटोरियल में, हमने दो डेटा स्ट्रक्चर्स यानि AVL के पेड़ों और हीप को विस्तार से देखा।
एवीएल पेड़ संतुलित बाइनरी पेड़ हैं जो ज्यादातर डेटाबेस इंडेक्सिंग में उपयोग किए जाते हैं।
एवीएल पेड़ों पर किए गए सभी ऑपरेशन बाइनरी सर्च पेड़ों के समान हैं, लेकिन एवीएल पेड़ों के मामले में एकमात्र अंतर यह है कि हमें संतुलन कारक को बनाए रखने की आवश्यकता है यानी डेटा ऑपरेशंस विभिन्न ऑपरेशनों के परिणामस्वरूप एक संतुलित पेड़ बने रहना चाहिए। यह AVL ट्री रोटेशन ऑपरेशन का उपयोग करके प्राप्त किया जाता है।
हीप्स पूरी तरह से बाइनरी ट्री स्ट्रक्चर्स हैं जिन्हें मिन-हीप या मैक्सिम-हीप में वर्गीकृत किया गया है। मिन-हीप में इसकी जड़ के रूप में न्यूनतम तत्व होता है और बाद के नोड्स उनके मूल नोड से अधिक या बराबर होते हैं। अधिकतम-ढेर में, स्थिति बिल्कुल विपरीत है यानी अधिकतम तत्व हीप की जड़ है।
0 के साथ सरणियों के रूप में हीप्स का प्रतिनिधित्व किया जा सकता हैवेंपेड़ की जड़ के रूप में तत्व। हीप डेटा संरचनाएं मुख्य रूप से हीप सॉर्ट और प्राथमिकता कतारों को लागू करने के लिए उपयोग की जाती हैं।
=> स्क्रैच से C ++ जानने के लिए यहाँ जाएँ।
अनुशंसित पाठ
- कतार डेटा संरचना चित्रण के साथ C ++ में
- चित्रण के साथ C ++ में स्टैक डेटा संरचना
- चित्रण के साथ C ++ में परिपत्र लिंक्ड सूची डेटा संरचना
- सी + + में चित्र संरचना के साथ लिंक्ड सूची डेटा संरचना
- C ++ में डेटा स्ट्रक्चर्स का परिचय
- चित्रण के साथ C ++ में प्राथमिकता कतार डेटा संरचना
- संदेह के साथ सी ++ में संदिग्ध रूप से सूचीबद्ध डेटा संरचना
- उदाहरणों के साथ C ++ में ढेर छाँटें
