बाइनरी पेड़ में सबसे कम आम पूर्वज

Question

बाइनरी खोज पेड़ के लिए सबसे कम आम पूर्वज के कार्यान्वयन के बाद निम्नलिखित है। मेरे पास दो प्रश्न हैं:

1) समय जटिलता ओ (एन) है और अंतरिक्ष जटिलता ओ (एन) खराब मामला है, लेकिन बीएसटी संतुलित होने पर समय और स्थान दोनों के लिए ओ (लॉगन) औसत मामला है। क्या वो सही है? 2) मैं बाइनरी पेड़ के लिए अपना समाधान कैसे बढ़ा सकता हूं न केवल बाइनरी खोज पेड़।

जल्द ही आपसे सुनने की आशा है।

//The function findOrQueue is to enqueue all elements upto target node to a queue 
public void findOrQueue(Node target, Node top, LLQueue q) { 
    int cmp = target.getData().compareTo(top.getData()); 
    if(cmp == 0) { 
     q.enqueue(top); 
     return ; 
    } 
    else if (cmp < 0) { 
     q.enqueue(top); 
     findOrQueue(target, top.getLeftChild(),q); 
    } 
    else { 
     q.enqueue(top); 
     findOrQueue(target, top.getRightChild(),q); 
    } 
} 

public Node LCA(Node n1, Node n2) throws QueueEmptyException { 
    LLQueue q1 = new LLQueue(); 
    LLQueue q2 = new LLQueue(); 
    findOrQueue(n1,getRoot(),q1); 
    findOrQueue(n2,getRoot(),q2); 
    Node t = null; 
    while (!q1.isEmpty() && !q2.isEmpty()) { 
     Node t1 = (Node)q1.dequeue(); 
     Node t2 = (Node)q2.dequeue(); 
     if(t1.getData() != t2.getData()) { 
      return t; 
     } 
     else t = t1; 
    } 
    if(q1.isEmpty() && q2.isEmpty()) 
     return null; 
    else 
     return t; 
    } 

Answer 1

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

निम्नलिखित कच्चे कार्यान्वयन में पैकेज java.util.concurrent * और में ढेर java.util LinkedBlockingQueue का उपयोग करता है * -। हालांकि, किसी भी अन्य साधारण कतार और ढेर भी चाल करना होगा। कोड मानता है कि पेड़ में लक्ष्य नोड मौजूद हैं।

public static void findPath2(Node target,Node top, Stack<Node> path){ 
    LinkedBlockingQueue<Node> q1 = new LinkedBlockingQueue<Node>(), q2 = new LinkedBlockingQueue<Node>(), 
    q3 = new LinkedBlockingQueue<Node>(); 
    Node n = top; 
    Node parrent = null; 
    while(n.getData().compareTo(target.getData())!= 0){ 
     parrent = n; 
     if(n.right != null){ 
      q2.add(n.right); 
      q3.add(parrent); 
     } 
     if(n.left != null){ 
      q2.add(n.left); 
      q3.add(parrent); 
     } 
     n = q2.remove(); 
     q1.add(n); 
    } 

    Stack<Node> s3 = new Stack<Node>(), s2 = new Stack<Node>(); 
    while(!q3.isEmpty()){ 
     s3.push(q3.remove());   
    }  
    for(int i = 1; i <= q2.size(); i++) 
     s3.pop();  
    while(!s3.isEmpty()) 
     s2.push(s3.pop()); 
    while(!q1.isEmpty()) 
     s3.push(q1.remove()); 
    LinkedBlockingQueue<Node> temp = new LinkedBlockingQueue<Node>(); 
    while(!s2.isEmpty()) 
     temp.add(s2.pop()); 
    while(!temp.isEmpty()) 
     s2.push(temp.remove()); 
    path.push(s3.pop()); 
    path.push(s2.pop()); 
    while(!s3.isEmpty()){ 
     n = s3.peek();   
     while(n.getData().compareTo(path.peek().getData()) != 0 && !s3.isEmpty()){ 
      s3.pop(); 
      s2.pop(); 
      if(!s3.isEmpty()) 
       n = s3.peek(); 
     } 
     if(!s3.isEmpty()){ 
      s3.pop(); 
      path.push(s2.pop()); 
     } 
    }  
}