Tìm thuật toán nhanh để tìm khoảng cách giữa hai nút trong cây nhị phân

Question

Làm cách nào để tìm khoảng cách giữa hai nút trong cây nhị phân? Tương tự, thuật toán nào có để tìm tổ tiên chung gần đây nhất (tổ tiên chung thấp nhất) của hai nút?

Answer 1

Tìm tổ tiên chung gần như chắc chắn là nhiệm vụ dễ dàng hơn. Đây là một điều khá đơn giản: bắt đầu từ gốc cây, và hạ xuống cây cho đến khi bạn đạt đến một nút mà bạn sẽ phải xuống đến các trẻ khác nhau để đến hai nút được đề cập. Nút đó là cha mẹ chung (giả sử cây có chứa cả hai nút, tất nhiên).

Answer 2

Tạo hai bộ gồm tổ tiên của mỗi bộ: trong khi sự kết hợp các bộ trống, thêm tổ tiên tiếp theo của mỗi nút vào danh sách thích hợp. Khi có một nút chung, đó là tổ tiên chung.

Answer 3

1. tính trong danh sách của tổ tiên cho mỗi nút
2. tìm tiền tố chung
3. yếu tố cuối cùng từ tiền tố chung là tổ tiên chung thấp nhất
4. loại bỏ các tiền tố chung của cả tổ tiên liệt kê
5. khoảng cách là tổng độ dài của các danh sách còn lại +1

Answer 4

Như mọi người ở đây dường như biết, nếu bạn lưu ý khoảng cách mỗi nút là từ gốc, sau đó một khi bạn đã tìm thấy tổ tiên chung thấp nhất của hai nút, bạn có thể làm việc ra khoảng cách họ đến từ nhau trong thời gian không đổi.

Nếu bạn làm một lần chỉ làm việc tuyến tính với kích thước của cây thì bạn có thể tìm thấy tổ tiên chung thấp nhất của bất kỳ hai nút nào trong thời gian không đổi (dù cây có sâu bao nhiêu). Xem http://en.wikipedia.org/wiki/Lowest_common_ancestor

Thuật toán Baruch Schieber và Uzi Vishkin cho tổ tiên chung thấp nhất là hoàn toàn thiết thực để sử dụng và lập trình.

Answer 5

Đầu tiên, tìm kiếm chiều cao của phần tử đầu tiên. Ngoài ra, hãy quay lại đường dẫn đến đó bằng danh sách được liên kết. Bạn có thể thực hiện việc này trong thời gian O (logN). Giả sử cây được cân bằng, nơi chiều cao là logN. để H1 = chiều cao của phần tử đầu tiên.

Sau đó, tìm kiếm chiều cao cho phần tử thứ hai. Ngoài ra, hãy quay lại đường dẫn đến đó bằng danh sách được liên kết. Bạn có thể thực hiện việc này trong thời gian O (logN). Hãy H2 = chiều cao của phần tử thứ hai.

Dấu vết thông qua cả hai danh sách liên kết được thu thập cho đến khi các giá trị không còn bằng nhau (đường dẫn phân tách) Điểm trước khi chúng phân kỳ, hãy gọi chiều cao của nút đó H3.

Do đó, con đường dài nhất là H1 + H2 - 2 * H3 (vì bạn cần H1 để đi đến H1 và H2 để đi tới H2. Nhưng thực sự, bạn có thể theo dõi từ H1 lên đến H1-H3 và sau đó di chuyển đến H2 từ H3 Vì vậy, nó (H1-H3) + (H2-H3) = H1 + H2 -2 * H3.

chi tiết thi hành nên thẳng về phía trước

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

Như vậy,

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; 

Thời gian phức tạp: O (logN) + O (logN) + O (logN) = O (logN) Space Độ phức tạp: O (logN) (để lưu trữ cả hai danh sách liên kết khoảng cách)

Answer 6

1. Tìm tổ tiên chung ít nhất (LCA) như chúng tôi đã làm trong Q56. Xem both approaches to find LCA. Tôi thích cách tiếp cận đầu tiên vì nó lưu trữ đường dẫn của mỗi nút mà chúng ta có thể sử dụng để tìm nút b/w khoảng cách đến LCA
2. Bây giờ đếm số lượng nút trong đường dẫn 1 và đường dẫn 2. Tổng khoảng cách/đỉnh sẽ là (Đường dẫn 1 Nút -1) + (Path2 Nút -1)

Answer 7

đây là triển khai DP cho khoảng cách BT. Không tối ưu, nhưng thú vị. nó tạo ra cây thứ nhất, với một mảng đầu vào.

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); 
     } 
    } 
}