एक दिए गए बाइनरी ट्री के मामले में, इसे बाइनरी सर्च ट्री में इस तरह बदलें कि बाइनरी ट्री की मूल संरचना बरकरार रहे।
इस समाधान में सरणी-आधारित समाधान के बजाय C++ STL के सेट का उपयोग किया जाएगा।
उदाहरण
उदाहरण 1
इनपुट
11 / \ 3 8 / \ 9 5
आउटपुट
9 / \ 5 11 / \ 3 8
उदाहरण 2
इनपुट
11 / \ 31 16 / \ 21 6
आउटपुट
16 / \ 11 21 / \ 6 31
समाधान
हमें इनऑर्डर ट्रैवर्सल करते समय बाइनरी ट्री के आइटम्स को एक सेट में कॉपी करना होगा। इसमें O(n log n) समय लगता है। ध्यान दें कि C++ STL (स्टैंडर्ड टेम्पलेट लाइब्रेरी) में सेट को रेड ब्लैक ट्री, AVL ट्री आदि जैसे सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का उपयोग करके लागू किया जाता है।
सेट को सॉर्ट करने की कोई आवश्यकता नहीं है क्योंकि C++ में सेट सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री को लागू करने के लिए उपयोग किए जाते हैं जिसके कारण सम्मिलन, खोज, विलोपन आदि जैसे प्रत्येक ऑपरेशन में O(log n) समय लगता है।
अब हम ट्री के इनऑर्डर ट्रैवर्सल करते समय सेट के तत्वों को एक-एक करके शुरुआत से ट्री में आसानी से कॉपी कर सकते हैं। ध्यान रखना चाहिए कि जब हम सेट के प्रत्येक आइटम को उसकी शुरुआत से कॉपी करते हैं, तो हम पहले इसे ट्री में इनऑर्डर ट्रैवर्सल करते समय कॉपी करते हैं, फिर इसे सेट से भी हटा देते हैं।
वर्तमान में उपरोक्त समाधान यहां बताए गए बाइनरी ट्री से बाइनरी सर्च ट्री के सरणी-आधारित रूपांतरण की तुलना में सरल और लागू करने में आसान है।
निम्नलिखित प्रोग्राम, बाइनरी ट्री को सेट का उपयोग करके बाइनरी सर्च ट्री (BST) में बदलने के लिए, यहां बताया गया है।
उदाहरण
/* सेट को कंटेनर के रूप में लागू करके बाइनरी ट्री को BST में बदलने के लिए CPP प्रोग्राम। */ #include <bits/stdc++.h> using namespace std; struct Node1 { int data; struct Node1 *left, *right; }; // इनऑर्डर ट्रैवर्सल करते समय नोड्स को सेट में संग्रहीत करने के लिए फ़ंक्शन। void storeinorderInSet(Node1* root1, set<int>& s){ if (!root1) return; // लेफ्ट सबट्री को पहले विज़िट किया जाता है storeinorderInSet(root1->left, s); सेट्स के लिए O(logn) क्रम सम्मिलन द्वारा लिया जाता है s.insert(root1->data); // हम राइट सबट्री को विज़िट करते हैं storeinorderInSet(root1->right, s); } // समय जटिलता = O(nlogn) // इनऑर्डर ट्रैवर्सल करते समय सेट के तत्वों को एक-एक करके ट्री में कॉपी करने के लिए फ़ंक्शन void setToBST(set<int>& s, Node1* root1){ // बेस कंडीशन if (!root1) return; // हम पहले लेफ्ट सबट्री पर जाते हैं और तत्वों को अपडेट करते हैं setToBST(s, root1->left); // इटरेटर प्रारंभ में सेट की शुरुआत की ओर इंगित करता है auto it = s.begin(); // हम सेट (सॉर्टेड) की शुरुआत में तत्व को ट्री में कॉपी करते हैं। root1->data = *it; // अब हम सेट से शुरुआती तत्व को मिटा देते हैं। s.erase(it); // अब हम राइट सबट्री पर जाते हैं और तत्वों को अपडेट करते हैं setToBST(s, root1->right); } // T(n) = O(nlogn) समय // हम बाइनरी ट्री को BST में बदलते हैं। void binaryTreeToBST(Node1* root1){ set<int> s; // हम ट्री के इनऑर्डर ट्रैवर्सल डेटा से सेट को भरते हैं storeinorderInSet(root1, s); // वर्तमान में सेट डिफ़ॉल्ट रूप से सॉर्टेड हैं क्योंकि वे सेल्फ-बैलेंसिंग BST को लागू करने के लिए उपयोग किए जाते हैं // हम इनऑर्डर ट्रैवर्सल करते समय सेट से ट्री में तत्वों को कॉपी करते हैं जो एक BST बनाता है setToBST(s, root1); } // समय जटिलता = O(nlogn), // सहायक स्थान = O(n) सेट के लिए। // नोड बनाने के लिए हेल्पर फ़ंक्शन Node1* newNode(int data){ // डायनामिकली मेमोरी आवंटित करना Node1* temp = new Node1(); temp->data = data; temp->left = temp->right = NULL; return temp; } // इनऑर्डर ट्रैवर्सल करने के लिए फ़ंक्शन void inorder(Node1* root1){ if (!root1) return; inorder(root1->left); cout<< root1->data << " "; inorder(root1->right); } int main(){ Node1* root1 = newNode(6); root1->left = newNode(8); root1->right = newNode(10); root1->right->left = newNode(11); root1->left->left = newNode(2); root1->left->right = newNode(7); root1->right->right = newNode(12); /* निम्नलिखित आकृति में दिए गए ट्री का निर्माण 6 / \ 8 10 /\ / \ 2 7 11 12 */ // हम उपरोक्त बाइनरी ट्री को BST में बदलते हैं binaryTreeToBST(root1); cout<< "Inorder traversal of BST is: " << endl; inorder(root1); return 0; }आउटपुट
Inorder traversal of BST is: 1 5 6 7 9 10 11
समय जटिलता: O(n Log n)
सहायक स्थान: O(n)
