किसी दिए गए बाइनरी ट्री के मामले में, इसे बाइनरी सर्च ट्री में इस तरह से बदलें कि बाइनरी ट्री की मूल संरचना बरकरार रहे।
सरणी आधारित समाधान के बजाय इस समाधान द्वारा 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) में बदलने के लिए निम्नलिखित प्रोग्राम को यहाँ समझाया गया है।
उदाहरण
/* CPP program for converting a Binary tree to BST implementing sets as containers. */
#include <bits/stdc++.h>
using namespace std;
struct Node1 {
int data;
struct Node1 *left, *right;
};
// function for storing the nodes in set while performing inorder traversal.
void storeinorderInSet(Node1* root1, set<int>& s){
if (!root1)
return;
// Left subtree is visited first
storeinorderInSet(root1->left, s);
Order of O(logn) for sets is taken by insertion
s.insert(root1->data);
// We visit the right subtree
storeinorderInSet(root1->right, s);
} // Time complexity = O(nlogn)
// function for copying elements of set one by one to the tree while performing inorder traversal
void setToBST(set<int>& s, Node1* root1){
// base condition
if (!root1) return;
// We first move to the left subtree and update elements
setToBST(s, root1->left);
// iterator initially pointing to the starting of set
auto it = s.begin();
// We copy the element at sarting of set(sorted) to the tree.
root1->data = *it;
// now we erase the starting element from set.
s.erase(it);
// now we move to right subtree and update elements
setToBST(s, root1->right);
}
// T(n) = O(nlogn) time
// We convert Binary tree to BST.
void binaryTreeToBST(Node1* root1){
set<int> s;
// We populate the set with the tree's inorder traversal data
storeinorderInSet(root1, s);
// At present sets are by default sorted as they are used
implementing self-balancing BST
// We copy elements from set to the tree while inorder traversal
which makes a BST
setToBST(s, root1);
}
// Time complexity = O(nlogn),
// Auxiliary Space = O(n) for set.
// helper function for creating a node
Node1* newNode(int data){
// dynamically allocating memory
Node1* temp = new Node1();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// function for doing inorder traversal
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);
/* Building tree given in the following figure
6
/ \
8 10
/\ / \
2 7 11 12 */
// We convert the above Binary tree to 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)
सहायक स्थान को इस प्रकार दर्शाया गया है:(n)
