बाइनरी पेड़ में दो नोड्स के बीच दूरी खोजने के लिए तेज़ एल्गोरिदम की तलाश

Question

मुझे बाइनरी पेड़ में दो नोड्स के बीच की दूरी कैसे मिलती है? समान रूप से, दो नोड्स के सबसे हालिया आम पूर्वज (सबसे कम आम पूर्वज) को खोजने के लिए क्या एल्गोरिदम हैं?

Answer 1

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

Answer 2

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

Answer 3

1. प्रत्येक नोड के लिए पूर्वजों की सूची की गणना
2. आम उपसर्ग लगता है
3. आम उपसर्ग से पिछले तत्व सबसे कम आम पूर्वज
4. है हटाने दोनों पूर्वज से आम उपसर्ग को सूचीबद्ध
5. दूरी शेष सूचियों की लंबाई का योग +1

Answer 4

जैसा कि यहां सभी को पता है, अगर आप नोट करते हैं दूरी प्रत्येक नोड रूट से है, फिर एक बार जब आप दो नोड्स के सबसे कम आम पूर्वज पाए जाते हैं तो आप निरंतर समय में एक-दूसरे से दूरी की दूरी तय कर सकते हैं।

यदि आप एक बार पेड़ के आकार में केवल रैखिक काम करते हैं तो यह पता चला है कि आप निरंतर समय में किसी भी दो नोड्स के सबसे कम आम पूर्वज को देख सकते हैं (इससे कोई फर्क नहीं पड़ता कि पेड़ कितना गहरा है)। देखें http://en.wikipedia.org/wiki/Lowest_common_ancestor

सबसे कम आम पूर्वज के लिए बारुख शिची और उजी विशकिन एल्गोरिदम पूरी तरह व्यावहारिक और प्रोग्राम करने के लिए व्यावहारिक है।

Answer 5

पहला, पहले तत्व की ऊंचाई के लिए खोजें। इसके अलावा, एक लिंक की गई सूची का उपयोग करके वहां पहुंचने के लिए पथ वापस करें। आप ओ (लॉगएन) समय में ऐसा कर सकते हैं। मान लें कि पेड़ संतुलित है, जहां ऊंचाई लॉग है। एच 1 = पहले तत्व की ऊंचाई दें।

फिर, दूसरे तत्व की ऊँचाई की खोज करें। इसके अलावा, एक लिंक की गई सूची का उपयोग करके वहां पहुंचने के लिए पथ वापस करें। आप ओ (लॉगएन) समय में ऐसा कर सकते हैं। एच 2 = दूसरे तत्व की ऊंचाई दें।

मूल्यों के बराबर नहीं होने तक दोनों लिंक किए गए सूची के माध्यम से ट्रेस करें (पथ अलग हो जाएं) इससे पहले कि वे अलग हो जाएं, उस नोड एच 3 की ऊंचाई पर कॉल करें।

इस प्रकार, सबसे लंबे समय तक पथ एच 1 + एच 2 है - 2 * H3 (जब से तुम एच 1 पर जाने के लिए एच 1 की जरूरत है, और एच 2 एच 2 पर जाने के लिए लेकिन वास्तव में, आप एच 1 से वापस ऊपर H1-H3 तक ट्रेस कर सकते हैं। और फिर H3 से H2 पर जाएं। तो यह है (एच 1-एच 3) + (एच 2-एच 3) = एच 1 + एच 2 -2 * एच 3।ओ (logn) + O (logn) + O (logn) = ओ (logn) अंतरिक्ष:

क्रियान्वयन विवरण सीधे आगे

search(Tree* Head, Node* Value, LinkedList path, int distance); 

इस प्रकार

,

search(Head, Value1, path1, height1); 
search(Head, Value2, path2, height2); 

i = 0; 
while (path1[i] == path2[i]) 
{ 
    i++; 
} 
height3 = i-1; 
return height1+height2- 2*height3; 

समय जटिलता होना चाहिए जटिलता: ओ (लॉगएन) (दूरी की दोनों लिंक्ड सूची को स्टोर करने के लिए)

Answer 6

1. कम सामान्य पूर्वजों (एलसीए) को खोजें जैसा कि हमने Q56 में किया था। both approaches to find LCA देखें। मैं पहले दृष्टिकोण को पसंद करता हूं क्योंकि यह प्रत्येक नोड के पथ को संग्रहीत करता है जिसे हम एलसीए
2. पर दूरी बी/डब्ल्यू नोड खोजने के लिए उपयोग कर सकते हैं अब पथ 1 और पथ 2 में नोड्स की संख्या गिनें। कुल डिस्टेंस/शिखर (पथ 1 नोड्स -1) + (पथ 2 नोड्स -1)

Answer 7

यहां बीटी दूरी के लिए डीपी कार्यान्वयन है। इष्टतम नहीं, लेकिन दिलचस्प है। यह एक इनपुट सरणी के साथ पेड़ 1 बनाता है।

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Map; 

/** 
* Created by juanmf on 05/02/17. 
*/ 
public class Main2 { 
    /** 
    * {50, 60, 30, 10, 20, 40} will form a Node Structure as follows 
    * 5 
    * ├─L─ 3 
    * │   ├─L─ 1 
    * │   │   └─R─ 2 
    * │   └─R─ 4 
    * └─R─ 6 
    * L: left 
    * R: Right 
    * Path should be: [4, 3, 1, 2] 
    * steps: 3 <- output 
    * 
    * @param args 
    */ 
    public static void main(String[] args) { 
     int i = pathSteps(new int[] {50, 60, 30, 10, 20, 40}, 6, 20, 60); 
     System.out.println(i); 
    } 

    private static int pathSteps(int[] ints, int n, int from, int to) { 
     Node root = null; 
     Map<Node, Node> allNodes = new HashMap<>(); 

     for (int i: ints) { 
      if (root == null) { 
       root = new Node(i); 
       allNodes.put(root, root); 
      } 
      root.addNode(i, allNodes); 
     } 
     Map<Node, List<Node>> cache = new HashMap<>(); 

     Node fromN = new Node(from); 
     Node toN = new Node(to); 

     if (! allNodes.containsKey(fromN) || ! allNodes.containsKey(toN)) { 
      return -1; 
     } 
     fromN = allNodes.get(fromN); 
     toN = allNodes.get(toN); 

     List<Node> path = traverse(fromN, toN, cache); 
     return path.size() - 1; 
    } 

    private static List<Node> traverse(Node fromN, Node toN, Map<Node, List<Node>> cache) { 

     if(cache.containsKey(fromN)) { 
      System.out.println("cache Hit: " + fromN); 

      return cache.get(fromN); 
     } 
     System.out.println("visiting: " + fromN); 
     if (fromN == null || fromN.visited) { 
      return new ArrayList<>(); 
     } 
     if (fromN.equals(toN)) { 
      List<Node> target = new ArrayList<>(); 
      target.add(toN); 
      return target; 
     } 
     fromN.visited = true; 

     List<Node> parentWay = new ArrayList<>(); 
     List<Node> lchildWay = new ArrayList<>(); 
     List<Node> rchildWay = new ArrayList<>(); 

     parentWay.addAll(traverse(fromN.parent, toN, cache)); 
     lchildWay.addAll(traverse(fromN.lchild, toN, cache)); 
     rchildWay.addAll(traverse(fromN.rchild, toN, cache)); 

     List<Node> shortest = getShortestList(getShortestList(parentWay, lchildWay), rchildWay); 

     cache.put(fromN, shortest); 
     if (! shortest.isEmpty()) { 
      shortest.add(fromN); 
     } 
     fromN.visited = false; 
     System.out.println(shortest); 
     return shortest; 
    } 

    private static List<Node> getShortestList(List<Node> l1, List<Node> l2) { 
     List<Node> shortest = null; 
     if (l1 != null & l2 != null) { 
      if (l1.isEmpty()) { 
       shortest = l2; 
      } else if (l2.isEmpty()) { 
       shortest = l1; 
      } else { 
       shortest = l1.size() < l2.size() ? l1 : l2; 
      } 
     } else if (l1 == null) { 
      shortest = l2; 
     } else if (l2 == null) { 
      shortest = l1; 
     } 
     return shortest; 
    } 

    private static class Node { 
     Node parent; 
     Node lchild; 
     Node rchild; 

     final int value; 
     public boolean visited; 

     private Node(int value) { 
      this.value = value; 
     } 

     public void addNode(int i, Map<Node, Node> allNodes) { 
      if (i > value) { 
       if (null == rchild) { 
        rchild = new Node(i); 
        rchild.parent = this; 
        allNodes.put(rchild, rchild); 
       } else { 
        rchild.addNode(i, allNodes); 
       } 
      } 
      if (i < value) { 
       if (null == lchild) { 
        lchild = new Node(i); 
        lchild.parent = this; 
        allNodes.put(lchild, lchild); 
       } else { 
        lchild.addNode(i, allNodes); 
       } 
      } 
     } 

     @Override 
     public boolean equals(Object obj) { 
      return ((Node) obj).value == value; 
     } 

     @Override 
     public int hashCode() { 
      return value; 
     } 

     @Override 
     public String toString() { 
      return String.valueOf(value); 
     } 
    } 
}