सबसे बड़ा तत्व एक BST

Question

एक द्विआधारी खोज वृक्ष और एक पूर्णांक कश्मीर को देखते हुए में कश्मीर की तुलना में छोटे ढूंढने के लिए, मैं सबसे बड़ा तत्व लालकृष्ण

से कम

नीचे ट्री में प्राप्त करना चाहते हैं,

for K = 13, result = 12 
for K = 10, result = 8 
for K = 1 (or) 2, result = -1 

     10 

    5  12 

2 8 11 14 

मैंने नीचे तर्क की कोशिश की। लेकिन क्या ऐसा करने का कोई बेहतर तरीका है?

int findNum(node* node, int K) 
{ 
     if(node == NULL) 
     { 
       return -1; 
     } 
     else if(K <= node->data) 
     { 
       return findNum(node->left,K); 
     } 
     else if(K > node->data) 
     { 
       int t = findNum(node->right,K); 
       return t > node->data ? t : node->data; 
     } 

     return -1; 
} 

Answer 1

हे (लॉग एन) है, जो कम से कम है कि। हालांकि, आप दक्षता में सुधार कर सकते हैं (जो कि इन साक्षात्कारकर्ताओं की मुख्य बात है) और पूंछ के पुनरावृत्ति को समाप्त करके स्टैक ओवरफ्लो (तादा!) की संभावना को खत्म कर सकते हैं, इसे एक लूप में बदल सकते हैं। इसके अलावा, यदि पेड़ में ऋणात्मक संख्याएं हैं तो आपका कोड काम नहीं करता है ... यदि आपका मतलब गैर-नकारात्मक पूर्णांक है, तो आपको ऐसा कहना चाहिए, लेकिन यदि साक्षात्कारकर्ता ने अभी "पूर्णांक" कहा है तो आपको थोड़ा अलग कोड और एक अलग आवश्यकता है एपीआई। (आप एक ही फ़ंक्शन हस्ताक्षर रख सकते हैं लेकिन विफलता पर -1 के बदले में के बदले।)

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

// Return the greatest int < K in tree, or K if none. 
int findNum (Node* tree, int K) 
{ 
    int val = K; 

    while(tree) 
     if(tree->data >= K) 
      tree = tree->left; 
     else{ 
      val = tree->data; 
      tree = tree->right; 
     } 

    return val; 
} 

Answer 2

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

सामान्य जीवन में सामान्य रूप से, इन समस्याओं में से अधिकांश को अपने कोड में हल करने की आवश्यकता नहीं है। एसटीएल आपके लिए कई सामान्य कार्य कर सकता है। यह जानना उपयोगी है कि उन्हें कैसे हल किया जाए, इसलिए परीक्षण।

Answer 3

मैं मानक पुस्तकालय सुविधाओं का उपयोग करने में विश्वास करता हूं। इस प्रकार, मेरा समाधान std::set का उपयोग करता है। :-)

int largest_num_smaller_than(std::set<int> const& set, int num) 
{ 
    std::set<int>::const_iterator lb(set.lower_bound(num)); 
    return lb == set.begin() ? -1 : *--lb; 
} 

Answer 4

:

यहाँ एक कार्यान्वयन है। इसलिए, कोड (अद्यतन किया गया) किया जाएगा

int findNum (Node *node, int K) 
{ 
    Node* last_right_move = NULL; 

    while (node) 
    { 
     if (K<=node->data) 
      node = node->left; 
     else 
     { 
      last_right_move = node; 
      node = node->right; 
     } 
    } 

    if (last_right_move) 
     return last_right_move->data; 
    else 
     return NOT_FOUND; // defined previously. (-1 may conflict with negative number) 
} 

Answer 5

क्या पहले उत्तर कहा, और यहाँ के पीछे कारण है कि यह हे (लॉग एन) की तुलना में बेहतर नहीं मिल सकता है तर्क है। आप के से कम से कम सबसे बड़ी संख्या की तलाश में हैं। यह बीएसटी-सर्च/प्राप्त करने के लिए काफी करीब है।

हालांकि अपने मूल एल्गोरिथ्म काफी अच्छा लग रहा है, मुझे लगता है कि यह तेजी से होगा:

int findNum (node root, int K) { 
     if(root == null) return -1; 

     if(K > root.val) { 
      if(root.right != null) return findNum(root.right, K);    
      else return root.val; 
     } 

     return findNum(root.left, K); //look in left subtree 

    }