एक बीएसटी

Question

में स्वैप नोड्स खोजें I मैं एक प्रोग्राम लिखने की कोशिश कर रहा हूं जो बीएसटी में दो नोड्स का पता लगा सकता है और मुद्रित कर सकता है।

एक तीन स्तर के पेड़ में, मैं इस दृष्टिकोण का उपयोग कर समाधान के पास पहुंचा।

If (!AllSubTreeAreValid()) 
{ 
//Nodes swapped on same side of main root node 
} 
else 
{ 
    int max = getMax(root->left); 
    int min = getMin(root->right); 
    if(max > root->data || min < root->data) 
    { 
    //Nodes swapped on different sides of main root node 
    //Print max and min values 

    } 
else 
{ 
//No node swappped 
} 
} 

//Helper functions 
int GetMaxEle(TreeNode* tree) 
{ 
    while(tree->right!=NULL) 
    { 
     tree=tree->right; 
    } 
    return tree->info; 
} 

int GetMinEle(TreeNode* tree) 
{ 
    while(tree->left!=NULL) 
    { 
     tree=tree->left; 
    } 
    return tree->info; 
} 

लेकिन ऊपर दृष्टिकोण में विफल रहा है जब मैं चार स्तर के पेड़ के साथ परीक्षण करने के लिए कोशिश की।

   20 

     15   30 

    10 17  25  33 

9 16 12 18 22 26 31 34 

रूट नोड 15 के दाएं उपट्री में होने के नाते, 12 अभी भी अधिक (उल्लंघन) है।

रूट नोड 15 के बाएं उपट्री में होने के नाते, 16 अभी भी अधिक (उल्लंघन) है।

तो, 16, 12 उपर्युक्त बीएसटी में स्वैच्छिक तत्व हैं। मैं उन्हें प्रोग्राम के माध्यम से कैसे ढूंढूं?

Answer 1

एक तरह से इस समस्या के बारे में सोचने के लिए तथ्य यह है कि पेड़ की एक inorder की पैदल दूरी पर क्रमबद्ध क्रम में सभी तत्त्व का उत्पादन करेगा उपयोग करने के लिए है। यदि आप इस सैर के दौरान सॉर्ट किए गए क्रम से विचलन का पता लगा सकते हैं, तो आप गलत जगह पर मौजूद दो तत्वों को ढूंढने का प्रयास कर सकते हैं।

चलो देखते हैं कि इसे सरल सॉर्ट किए गए सरणी के लिए पहले कैसे करें, फिर पेड़ पर काम करने वाले कुछ बनाने के लिए हमारे एल्गोरिदम का उपयोग करेंगे। सहजता से, अगर हम एक क्रमबद्ध सरणी के साथ शुरू करते हैं और फिर दो (गैर-बराबर!) तत्वों को स्वैप करते हैं, तो हम सरणी में कुछ तत्वों के साथ समाप्त हो जाएंगे। उदाहरण के लिए, दिए गए सरणी

1 2 3 4 5 

अगर हम स्वैप 2 और 4, हम इस सरणी के साथ अंत:

1 4 3 2 5 

हम कैसे पता लगाता है कि 2 और 4 यहाँ बदली कर रहे थे? खैर, चूंकि 4 दो तत्वों में से अधिक है और नीचे की ओर घुमाया गया था, यह इसके चारों ओर के दोनों तत्वों से बड़ा होना चाहिए। इसी तरह, क्योंकि 2 को बदल दिया गया था, यह इसके चारों ओर के दोनों तत्वों से छोटा होना चाहिए। इससे, हम निष्कर्ष निकाल सकते हैं कि 2 और 4 स्वैप किए गए थे।

हालांकि, यह हमेशा सही ढंग से काम नहीं करता है। उदाहरण के लिए, मान लीजिए कि हम स्वैप 1 और 4:

4 2 3 1 5 

यहाँ, दोनों 2 और 1 उनके पड़ोसी तत्वों की तुलना में छोटे हैं, और दोनों 4 और 3 उनकी से बड़े होते हैं।इससे हम बता सकते हैं कि इनमें से दो चार किसी भी तरह से बदल दिए गए थे, लेकिन यह स्पष्ट नहीं है कि हमें किसके साथ आदान-प्रदान करना चाहिए। हालांकि, अगर हम इन मूल्यों में से सबसे बड़ा और सबसे छोटा (क्रमशः 1 और 4) लेते हैं, तो हम उस जोड़ी को बदल देते हैं जो स्वैप किया गया था।

आम तौर पर, तत्वों है कि अनुक्रम में बदली रहे थे खोजने के लिए, आप

• सरणी में सबसे बड़ा स्थानीय अधिकतम लगाना चाहते हैं।
• सरणी में सबसे छोटा स्थानीय न्यूनतम।

ये दो तत्व जगह से बाहर हैं और उन्हें बदला जाना चाहिए।

अब, चलो पेड़ों पर इसे कैसे लागू करें इसके बारे में सोचें। चूंकि पेड़ की एक अंदरूनी पैदल दूरी क्रमशः दो तत्वों के साथ सॉर्ट किए गए अनुक्रम का उत्पादन करेगी, एक विकल्प पेड़ पर चलना होगा, हमारे द्वारा पाए गए तत्वों के क्रम अनुक्रम को रिकॉर्ड करना होगा, फिर उपरोक्त एल्गोरिदम का उपयोग करना होगा। पर हम पाते हैं

9 10 16 15 12 17 18 20 22 25 26 30 31 33 34 

सूचना है कि 16 उसके आसपास के तत्वों से अधिक है हम एक सरणी में इस linearize तो

   20 
     /  \ 
     15    30 
    / \  / \ 
    10 17  25  33 
/| /\ /\ | \ 
9 16 12 18 22 26 31 34 

और कहा कि 12 अपने से भी कम है: उदाहरण के लिए, अपने मूल BST पर विचार करें। यह तुरंत हमें बताता है कि 12 और 16 स्वैप किए गए थे।

इस समस्या को हल करने के लिए एक सरल एल्गोरिथ्म, इसलिए, एक vector या deque की तरह एक दृश्य में यह linearize को पेड़ की एक inorder की पैदल दूरी पर ऐसा करने के लिए किया जाएगा, तो उस अनुक्रम स्कैन करने के लिए सबसे बड़ा स्थानीय अधिकतम और सबसे छोटा लगता है स्थानीय न्यूनतम ओ ओ (एन) स्पेस का उपयोग करके ओ (एन) समय में चलाया जाएगा। एक ट्रिकियर लेकिन अधिक स्पेस-कुशल एल्गोरिदम केवल एक समय में तीन नोड्स का ट्रैक रखना होगा - वर्तमान नोड, इसके पूर्ववर्ती, और इसके उत्तराधिकारी - जो स्मृति उपयोग को ओ (1) में कम कर देता है।

आशा है कि इससे मदद मिलती है!

Answer 2

मैं अपने getMin एट getMax परिकल्पना कि पेड़ एक BST है witht काम करता है, इसलिए

T getMax(tree) { 
    return tree -> right == null 
    ? tree -> value 
    : getMax(tree -> right); 
} 

(या एक पाश के साथ बराबर कोड) लगता है। यदि ऐसा है, तो आपका कोड पेड़ में अधिकतम तीन मानों पर जांच करता है। यहां तक ​​कि अगर मैक्स और getMin वास्तविक अधिकतम/मिनट प्राप्त करने के लिए पूरे पेड़ को पार कर गया है, तो भी आप केवल दो तुलनाओं पर अपने परीक्षण का आधार लेंगे। यदि आप यह देखना चाहते हैं कि आपका पेड़ बीएसटी संपत्ति को संतुष्ट करता है, तो यह स्पष्ट है कि आपको सभी मूल्यों की जांच करनी है। अपने माता-पिता के साथ प्रत्येक नोड की तुलना करने के लिए पर्याप्त है।

void CheckIsBst(Tree *tree) { 
    if (tree -> left != null) { 
    if (tree -> left -> value > tree -> value) { 
     // print violation 
    } 
    CheckIsBst(tree -> left); 
    } 
    // same with -> right, reversing <to> in the test 
} 

संपादित: कि गलत था, टिप्पणी देखें। मेरा मानना ​​है कि यह ठीक है।

void checkIsBst(Tree *Tree, Tree *lowerBound, Tree *upperBound) { 
    if(lowerBound!= null && lowerBound -> value > tree -> Value) { 
    //violation 
    } 
    // same for upper bound, check with < 
    if (tree -> left != null) { 
    if (tree -> left -> value > tree -> value) { 
     // print violation 
    } 
    CheckIsBst(tree -> left, lowerBound, tree); 
    } 
    // same for right, reversing comparison 
    // setting lowerBound to tree instead of upperBound 
} 

अशक्त सीमा के साथ जड़ से कॉलिंग

Answer 3

पेड़ ट्रैवर्सल templatetypedef द्वारा किया गया कार्य करता है यदि आप सुनिश्चित हैं कि केवल एक स्वैप है। अन्यथा मैं एक समाधान अपने प्रारंभिक कोड के आधार पर सुझाव देते हैं:

int GetMax(TreeNode* tree) { 
    int max_right, max_left, ret; 

    ret = tree->data; 
    if (tree->left != NULL) { 
     max_left = GetMax(tree->left); 
     if (max_left > ret) 
      ret = max_left; 
    } 
    if (tree->right != NULL) { 
     max_right = GetMax(tree->right); 
     if (max_right > ret) 
      ret = max_right; 
    } 

    return ret; 
} 

int GetMin(TreeNode* tree) { 
    int min_right, min_left, ret; 

    ret = tree->data; 
    if (tree->left != NULL) { 
     min_left = GetMin(tree->left); 
     if (min_left < ret) 
      ret = min_left; 
    } 
    if (tree->right != NULL) { 
     min_right = GetMin(tree->right); 
     if (min_right < ret) 
      ret = min_right; 
    } 

    return ret; 
} 

void print_violations(TreeNode* tree) { 
    if ((tree->left != NULL) && (tree->right != NULL)) { 
     int max_left = GetMax(tree->left); 
     int min_right = GetMin(tree->right); 
     if (max_left > tree->data && min_right < tree->data) { 
      printf("Need to swap %d with %d\n", max_left, min_right); 
     } 
    } 
    if (tree->left != NULL) 
     print_violations(tree->left); 
    if (tree->right != NULL) 
     print_violations(tree->right); 
} 

यह धीमी है, लेकिन यह सब स्वैप यह पहचान करता प्रिंट करता है। सभी उल्लंघनों को मुद्रित करने के लिए बदला जा सकता है (उदा। यदि (max_left> पेड़-> डेटा) प्रिंट उल्लंघन)। यदि आप ट्री नोड में दो फ़ील्ड जोड़ सकते हैं तो अधिकतम प्रदर्शन के साथ अधिकतम और न्यूनतम प्रीकंप्यूटेड के साथ आप प्रदर्शन को बेहतर बना सकते हैं।