Buscando un algoritmo rápido para encontrar la distancia entre dos nodos en el árbol binario

Question

¿Cómo encuentro la distancia entre dos nodos en un árbol binario? De manera equivalente, ¿qué algoritmos existen para encontrar el ancestro común más reciente (ancestro común más bajo) de dos nodos?

Answer 1

Encontrar el ancestro común es, casi con certeza, la tarea más fácil. Esta es una muy simple: comience desde la raíz del árbol y desciende hasta alcanzar un nodo donde tendrías que descender a diferentes niños para llegar a los dos nodos en cuestión. Ese nodo es el padre común (suponiendo que el árbol contiene ambos nodos, por supuesto).

Answer 2

Haga dos conjuntos que consistan en los antepasados ​​de cada uno: mientras que la unión de los conjuntos está vacía, agregue el próximo ancestro de cada nodo a la lista correspondiente. Una vez que hay un nodo común, ese es el ancestro común.

Answer 3

1. calcular la lista de los ancestros para cada nodo
2. encontrar el prefijo común
3. el último elemento del prefijo común es el ancestro común más bajo
4. quitar el prefijo común de ambos ancestro enumera
5. la distancia es la suma de las longitudes de las listas restantes +1

Answer 4

Como todo el mundo parece saber, si mantiene una nota del Cuando cada nodo es desde la raíz, una vez que haya encontrado el ancestro común más bajo de los dos nodos, podrá calcular la distancia entre ellos en un tiempo constante.

Si realiza un trabajo por única vez lineal en el tamaño del árbol, resulta que puede encontrar el ancestro común más bajo de dos nodos en tiempo constante (sin importar qué tan profundo sea el árbol). Ver http://en.wikipedia.org/wiki/Lowest_common_ancestor

El algoritmo Baruch Schieber y Uzi Vishkin para el ancestro común más bajo es completamente práctico de usar y programar.

Answer 5

Primero, busca la altura del primer elemento. Además, devuelve la ruta para llegar utilizando una lista vinculada. Puede hacerlo en tiempo O (logN). Supongamos que el árbol está equilibrado, donde la altura es logN. deje H1 = altura del primer elemento.

Luego, busque la altura del segundo elemento. Además, devuelve la ruta para llegar utilizando una lista vinculada. Puede hacerlo en tiempo O (logN). Deje H2 = altura del segundo elemento.

Rastrear a través de ambas listas unidas recopiladas hasta que los valores ya no sean iguales (las rutas divergen) El punto antes de que diverjan, llame a la altura de ese nodo H3.

Por lo tanto, el camino más largo es H1 + H2 - 2 * H3 (ya que se necesita H1 para ir a H1 y H2 a ir a H2 Pero, en realidad, se puede rastrear desde H1 hasta el H1-H3. .y luego pasar a H2 desde H3. Entonces es (H1-H3) + (H2-H3) = H1 + H2 -2 * H3.

Detalles de la implementación debería ser sencillo

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

Por lo tanto,

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; 

Tiempo Complejidad: O (logN) + O (logN) + O (logN) = O (logN) Espacio Complejidad: O (logN) (para almacenar ambas listas de distancias enlazadas)

Answer 6

1. Encuentra el antepasado común (LCA) como lo hicimos en Q56. Ver both approaches to find LCA. Prefiero el primer acercamiento ya que almacena la ruta de cada nodo que también podemos usar para encontrar la distancia nodo b/n a LCA
2. Ahora cuente el número de nodos en la ruta 1 y la ruta 2. La totalidad de las destineces/vértices (Ruta 1 Nodos -1) + (Nodos Path2 -1)

Answer 7

aquí está la implementación DP para la distancia BT. No es óptimo, pero es interesante. crea el árbol primero, con una matriz de entrada.

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