Ricerca di un algoritmo veloce per trovare la distanza tra due nodi nell'albero binario

Question

Come si trova la distanza tra due nodi in un albero binario? Equivalentemente, quali algoritmi ci sono per trovare il più recente antenato comune (antenato più basso comune) di due nodi?

Answer 1

Trovare l'antenato comune è quasi certamente il compito più facile. Questo è piuttosto semplice: iniziare dalla radice dell'albero e discendere l'albero fino a raggiungere un nodo in cui dovresti scendere a diversi bambini per arrivare ai due nodi in questione. Quel nodo è il genitore comune (assumendo che l'albero contenga entrambi i nodi, ovviamente).

Answer 2

Creare due set costituiti dagli antenati di ciascuno: mentre l'unione dei set è vuota, aggiungere il prossimo antenato di ciascun nodo all'elenco appropriato. Una volta che c'è un nodo comune, questo è l'antenato comune.

Answer 3

1. calcolare l'elenco degli antenati per ogni nodo
2. trovare il prefisso comune
3. l'ultimo elemento dal prefisso comune è il più basso antenato comune
4. rimuovere il prefisso comune sia antenato elenca
5. la distanza è la somma delle lunghezze delle liste rimanenti +1

Answer 4

Come tutti qui sembra sapere, se si tiene una nota del la distanza di ogni nodo è dalla radice, quindi una volta trovato l'antenato comune più basso dei due nodi è possibile calcolare la distanza tra di loro in un tempo costante.

Se si lavora una volta sola in modo lineare nella dimensione dell'albero, si scopre che è possibile trovare il più basso antenato comune di due nodi in tempo costante (indipendentemente dalla profondità dell'albero). Vedi http://en.wikipedia.org/wiki/Lowest_common_ancestor

L'algoritmo di Baruch Schieber e Uzi Vishkin per il più basso antenato comune è interamente pratico da utilizzare e programmare.

Answer 5

Primo, cercare l'altezza del primo elemento. Inoltre, restituire il percorso per arrivarci utilizzando un elenco collegato. È possibile farlo in tempo O (logN). Supponiamo che l'albero sia bilanciato, dove l'altezza è logN. let H1 = altezza del primo elemento.

Quindi, cercare l'altezza del secondo elemento. Inoltre, restituire il percorso per arrivarci utilizzando un elenco collegato. È possibile farlo in tempo O (logN). Lasciate H2 = altezza del secondo elemento.

Tracciare entrambe le liste collegate raccolte fino a quando i valori non sono più uguali (percorsi divergenti) Il punto prima che divergano, chiama l'altezza di quel nodo H3.

Così, il percorso più lungo è H1 + H2 - 2 * H3 (in quanto è necessario H1 di andare a H1 e H2 di andare a H2 Ma in realtà, è possibile risalire da H1 fino ad H1-H3. e quindi passare a H2 da H3. Quindi è (H1-H3) + (H2-H3) = H1 + H2 -2 * H3.

dettagli attuazione dovrebbe essere semplice

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

Così,

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; 

Tempo Complessità: O (log N) + O (log N) + O (log N) = O (log N) Spazio Complessità: O (logN) (per memorizzare entrambe le liste collegate di distanze)

Answer 6

1. Trova Least common Ancestor (LCA) come abbiamo fatto in Q56. Vedi both approaches to find LCA. Preferirei il primo approccio in quanto memorizza il percorso di ogni nodo, che possiamo usare per trovare il nodo b/n di distanza in LCA
2. Contare ora il numero di nodi nel percorso 1 e nel percorso 2. I punti di distacco/vertici totali saranno (Percorso 1 nodi -1) + (Nodi Path2 -1)

Answer 7

ecco l'implementazione DP per BT distance. Non ottimale, ma interessante. crea l'albero 1, con una matrice di input.

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