एक बाइनरी पेड़ में नोड के पहले आम पूर्वजों को कैसे ढूंढें?

Question

के बाद पहले आम पूर्वज को खोजने के लिए मेरे एल्गोरिथ्म है। लेकिन मुझे नहीं पता कि समय की जटिलता की गणना कैसे करें, क्या कोई मदद कर सकता है?

public Tree commonAncestor(Tree root, Tree p, Tree q) { 
    if (covers(root.left, p) && covers(root.left, q)) 
     return commonAncestor(root.left, p, q); 
    if (covers(root.right, p) && covers(root.right, q)) 
     return commonAncestor(root.right, p, q); 
    return root; 
} 
private boolean covers(Tree root, Tree p) { /* is p a child of root? */ 
    if (root == null) return false; 
    if (root == p) return true; 
    return covers(root.left, p) || covers(root.right, p); 
} 

Answer 1

ठीक है, तो चलिए इस एल्गोरिदम के लिए सबसे खराब स्थिति की पहचान करके शुरू करते हैं। covers खोजें पेड़ बाएं से दाएं, तो आप बुरी से बुरी हालत व्यवहार पाने से यदि नोड आप खोज रहे हैं सबसे दायीं ओर का पत्ता है, या यह सबट्री में बिल्कुल भी नहीं है। इस बिंदु पर आप उपट्री में सभी नोड्स का दौरा करेंगे, इसलिए coversओ (एन) है, जहां एन पेड़ में नोड्स की संख्या है।

इसी तरह, commonAncestor सबसे खराब मामले व्यवहार प्रदर्शित करता है जब p और q के पहले आम पूर्वज पेड़ में दाईं ओर गहरे नीचे हैं। इस मामले में, यह पहले दो बार covers पर कॉल करेगा, दोनों मामलों में सबसे खराब समय व्यवहार प्राप्त करेगा। यह तो अपने आप को फिर से सही सबट्री, जो एक संतुलित पेड़ के मामले में आकार n/2 की है को कॉल करेंगे।

मान लिया जाये कि पेड़ संतुलित है, हम आवर्तन संबंध T(n) = T(n/2) + O(n) द्वारा रन टाइम वर्णन कर सकते हैं। मास्टर प्रमेय का उपयोग करके, हमें संतुलित पेड़ के लिए उत्तर T(n) = O(n) मिलता है।

अब, अगर पेड़ नहीं संतुलित है, हम सबसे खराब स्थिति में केवल सबट्री का आकार 1 द्वारा प्रत्येक पुनरावर्ती कॉल के लिए कम हो सकता है, पुनरावृत्ति T(n) = T(n-1) + O(n) उपज। इस पुनरावृत्ति का समाधान T(n) = O(n^2) है।

आप हालांकि इससे बेहतर कर सकते हैं।

उदाहरण के लिए, बजाय बस निर्धारण जो सबट्री p या qcover साथ शामिल की, के p और q करने के लिए पूरे मार्ग का निर्धारण करते हैं। यह लेता है O(n) सिर्फ cover की तरह, हम बस में अधिक जानकारी रख रहे हैं। अब, उन पथों को समानांतर में पार करें और जहां वे अलग हो जाएं बंद करें। यह हमेशा O(n) है।

यदि आपके पास प्रत्येक नोड से उनके माता-पिता के पॉइंटर्स हैं तो आप "पेड़-अप" पथ उत्पन्न करके इस पर भी सुधार कर सकते हैं, जिससे आप एक संतुलित पेड़ के लिए O(log n) दे सकते हैं।

नोट यह एक अंतरिक्ष समय दुविधा यह है कि, के रूप में अपने कोड O(1) अंतरिक्ष लेता है, इस एल्गोरिथ्म एक संतुलित पेड़ के लिए O(log n) जगह है, और सामान्य रूप में O(n) अंतरिक्ष ले जाता है।

Answer 2

hammar’s answer दर्शाता है, आपका एल्गोरिदम काफी अक्षम है क्योंकि कई ऑपरेशन दोहराए जाते हैं।

मैं एक अलग दृष्टिकोण करता हूं: प्रत्येक संभावित रूट नोड के परीक्षण के बजाय यदि दो दिए गए नोड एक ही उप-पेड़ में नहीं होते हैं (इस प्रकार यह पहला आम पूर्वज बनाते हैं) तो मैं रूट से पथ निर्धारित करता हूं दो दिए गए नोड्स और नोड्स की तुलना करें। जड़ से नीचे के रास्ते पर अंतिम आम नोड तब भी पहला आम पूर्वज है।

यहाँ जावा में एक (untested) कार्यान्वयन है:

private List<Tree> pathToNode(Tree root, Tree node) { 
    List<Tree> path = new LinkedList<Tree>(), tmp; 

    // root is wanted node 
    if (root == node) return path; 

    // check if left child of root is wanted node 
    if (root.left == node) { 
     path.add(node); 
     path.add(root.left); 
     return path; 
    } 
    // check if right child of root is wanted node 
    if (root.right == node) { 
     path.add(node); 
     path.add(root.right); 
     return path; 
    } 

    // find path to node in left sub-tree 
    tmp = pathToNode(root.left, node); 
    if (tmp != null && tmp.size() > 1) { 
     // path to node found; add result of recursion to current path 
     path = tmp; 
     path.add(0, node); 
     return path; 
    } 
    // find path to node in right sub-tree 
    tmp = pathToNode(root.right, node); 
    if (tmp != null && tmp.size() > 1) { 
     // path to node found; add result of recursion to current path 
     path = tmp; 
     path.add(0, node); 
     return path; 
    } 
    return null; 
} 

public Tree commonAncestor(Tree root, Tree p, Tree q) { 
    List<Tree> pathToP = pathToNode(root, p), 
       pathToQ = pathToNode(root, q); 
    // check whether both paths exist 
    if (pathToP == null || pathToQ == null) return null; 
    // walk both paths in parallel until the nodes differ 
    while (iterP.hasNext() && iterQ.hasNext() && iterP.next() == iterQ.next()); 
    // return the previous matching node 
    return iterP.previous(); 
} 

दोनों pathToNode और commonAncestor हे (एन) में हैं।