एक बीएसटी में दो नोड्स यादृच्छिक रूप से स्वैप किए जाते हैं, हमें उन दो नोड्स को ढूंढने की आवश्यकता होती है और उन्हें

Question

एक बाइनरी सर्च पेड़ दिया जाता है, जिसमें कोई भी दो नोड्स बदल जाते हैं। इसलिए हमें उन दो नोड्स को ढूंढने और उन्हें वापस स्वैप करने की आवश्यकता है (हमें नोड्स को स्वैप करने की आवश्यकता है, डेटा नहीं)

मैंने एक अतिरिक्त सरणी बनाकर ऐसा करने की कोशिश की जिसमें पेड़ के अंदरूनी ट्रैवर्सल है और यह भी बचाता है प्रत्येक नोड के लिए सूचक। फिर हम सरणी को पार करते हैं और दो नोड्स को क्रमबद्ध क्रम में नहीं पाते हैं, अब इन दो नोड्स को पेड़ में खोजा जाता है और फिर

तो मेरा प्रश्न यह है कि ओ (1) में इस समस्या को हल करने का तरीका है। अंतरिक्ष?

Answer 1

In order traversal बीएसटी पर आपको आदेश दिया गया तत्वों पर एक ट्रैवर्सल देता है।
आप इन-ऑर्डर ट्रैवर्सल का उपयोग कर सकते हैं, दो जगहों के तत्वों को ढूंढ सकते हैं (उन्हें दो पॉइंटर्स में स्टोर करें) और उन्हें वापस स्वैप करें।

यह विधि वास्तव में इसे बनाने के बिना फ्लाई पर वर्णित सरणी बना रही है।

ध्यान दें कि हालांकि, अंतरिक्ष खपत O(1) नहीं है, यह O(h) है जहां h स्टैक ट्रेस के कारण पेड़ की ऊंचाई है। यदि पेड़ संतुलित है, तो यह O(logn)

Answer 2

बीएसटी के आधार पर यह ओ (1) में किया जा सकता है।

उदाहरण के लिए, यदि पेड़ के नोड्स के पास अपने माता-पिता के पास एक सूचक है, तो आप Tree_traversal के विकिपीडिया पृष्ठ के nonRecrusiveInOrderTraversal अनुभाग में वर्णित कार्यान्वयन का उपयोग कर सकते हैं।

एक और संभावना के रूप में, यदि बीएसटी को 1-आयामी सरणी के रूप में संग्रहीत किया जाता है, तो नोड्स के बीच पॉइंटर्स के बजाय, आप केवल सरणी पर चल सकते हैं (और प्रत्येक नोड के माता-पिता और बच्चों को निर्धारित करने के लिए गणित करते हैं)।

ट्रैवर्सल/पैदल चलते समय, यह देखने के लिए जांचें कि वर्तमान तत्व सही जगह पर है या नहीं।

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

Answer 3

हम उन 2 यादृच्छिक रूप से स्वैप किए गए नोड्स को स्वैप करने और इसे सही करने के लिए नीचे दिए गए isBST() विधि को संशोधित कर सकते हैं।

/* Returns true if the given tree is a binary search tree 
(efficient version). */ 
int isBST(struct node* node) 
{ 
    struct node *x = NULL; 
    return(isBSTUtil(node, INT_MIN, INT_MAX,&x)); 
} 

/* Returns true if the given tree is a BST and its 
    values are >= min and <= max. */ 
int isBSTUtil(struct node* node, int min, int max, struct node **x) 
{ 

    /* an empty tree is BST */ 
    if (node==NULL) 
    return 1; 

    /* false if this node violates the min/max constraint */ 
    if (node->data < min || node->data > max) { 
    if (*x == NULL) { 
     *x = node;//same the first incident where BST property is not followed. 
    } 
    else { 
     //here we second node, so swap it with *x. 
     int tmp = node->data; 
     node->data = (*x)->data; 
     (*x)->data = tmp; 

    } 
    //return 0; 
    return 1;//have to return 1; as we are not checking here if tree is BST, as we know it is not BST, and we are correcting it. 
    } 
    /* otherwise check the subtrees recursively, 
    tightening the min or max constraint */ 
    return 
    isBSTUtil(node->left, min, node->data-1, x) && // Allow only distinct values 
    isBSTUtil(node->right, node->data+1, max, x); // Allow only distinct values 
}