Ruta más corta entre dos Nodes en una array como representación de un árbol binario

Posted on by Rudeus Greyrat

Considere un árbol binario en el que cada Node tiene dos hijos excepto los Nodes hoja. Si un Node se etiqueta como ‘v’, sus hijos de la derecha se etiquetarán como 2v+1 y los hijos de la izquierda como 2v. La raíz está etiquetada como
Dados dos Nodes etiquetados como i y j, la tarea es encontrar la distancia más corta y el camino de i a j. E imprima la ruta del Node i y el Node j desde el Node raíz.

Ejemplos: 

Entrada: i = 1, j = 2        
Salida: 1
Explicación:
La ruta es 1 2

Entrada: i = 4, j = 3
Salida: 3
Explicación:
La ruta es 4 2 1 3

Este problema es principalmente una extensión de Encontrar distancia entre dos claves dadas de un árbol binario . Aquí no sólo encontramos la distancia más corta sino también el camino.
La distancia entre los dos Nodes i y j será igual a dist(i, LCA(i, j)) + dist(j, LCA(i, j)) donde LCA significa el ancestro común más bajo de los Nodes etiquetados como i y j . Si un número x se representa en forma binaria, entonces 2*x se puede representar agregando 0 a la representación binaria de x y 2x+1 se puede representar agregando 1 a la representación binaria de x. Esto se debe a que cuando agregamos 0, todos los términos presentes en la forma binaria de x se desplazan a la izquierda, por lo que se duplica de manera similar cuando agregamos 1, obtenemos 2x+1. Supongamos que la representación binaria de un Node es 1010, esto nos dice la ruta de este Node desde la raíz. El primer término ‘1’ representa la raíz, el segundo término 0 representa el giro a la izquierda, luego el tercer término 1 representa un giro a la derecha desde el Node anterior y, finalmente, 0 representa el giro a la izquierda. 

El Node 10 en forma binaria es 1010 y el 13 en forma binaria es 1101. En segundo lugar, la longitud de la representación binaria de cualquier Node también informa sobre su nivel en un árbol binario. Supongamos que la representación binaria de i tiene una longitud de m y es  i_1 [Tex]i_2 [/Tex]… soy y la representación binaria del Node j tiene una longitud de n  j_1 [Tex]j_2 [/Tex]…… j_n . 
Así conocemos el camino de i y j desde la raíz. Encuentre k tal que para todo p<=k  yo_p =  j_p . Este es el LCA de i y j en forma binaria. Así que dist(i, LCA(i, j)) será m – k y dist(j, LCA(i, j)) = n – k. entonces la respuesta será m + n – 2k. E imprimir la ruta tampoco es un gran problema, simplemente almacene la ruta de i a LCA y la ruta de j a LCA y concatene.

C++

// C++ representation of finding shortest
// distance between node i and j
#include <bits/stdc++.h>
using namespace std;
 
// prints the path between node i and node j
void ShortestPath(int i, int j, int k, int m, int n)
{
    // path1 stores path of node i to lca and
    // path2 stores path of node j to lca
    vector<int> path1, path2;
    int x = m - 1;
 
    // push node i in path1
    path1.push_back(i);
 
    // keep pushing parent of node labelled
    // as i to path1 until lca is reached
    while (x != k) {
        path1.push_back(i / 2);
        i = i / 2;
        x--;
    }
    int y = n - 1;
 
    // push node j to path2
    path2.push_back(j);
 
    // keep pushing parent of node j till
    // lca is reached
    while (y != k)
    {
        path2.push_back(j / 2);
        j = j / 2;
        y--;
    }
 
    // printing path from node i to lca
    for (int l = 0; l < path1.size(); l++)
        cout << path1[l] << " ";
 
    // printing path from lca to node j
    for (int l = path2.size() - 2; l >= 0; l--)
        cout << path2[l] << " ";
    cout << endl;
}
 
// returns the shortest distance between
// nodes labelled as i and j
int ShortestDistance(int i, int j)
{
    // vector to store binary form of i and j
    vector<int> v1, v2;
 
    // finding binary form of i and j
    int p1 = i;
    int p2 = j;
    while (i != 0)
    {
        v1.push_back(i % 2);
        i = i / 2;
    }
    while (j != 0) {
        v2.push_back(j % 2);
        j = j / 2;
    }
 
    // as binary form will be in reverse order
    // reverse the vectors
    reverse(v1.begin(), v1.end());
    reverse(v2.begin(), v2.end());
 
    // finding the k that is lca (i, j)
    int m = v1.size(), n = v2.size(), k = 0;
    if (m < n)
    {
        while (k < m && v1[k] == v2[k])
            k++;
    }
    else {
        while (k < n && v1[k] == v2[k])
            k++;
    }
 
    ShortestPath(p1, p2, k - 1, m, n);
    return m + n - 2 * k;
}
 
// Driver Code
int main()
{
    cout << ShortestDistance(1, 2) << endl;
    cout << ShortestDistance(4, 3) << endl;
    return 0;
}

Java

// Java representation of finding shortest
// distance between node i and j
import java.util.*;
 
class GFG
{
     
// prints the path between node i and node j
static void ShortestPath(int i, int j, int k, int m,
                                    int n)
{
    // path1 stores path of node i to lca and
    // path2 stores path of node j to lca
    Vector<Integer> path1=new Vector<Integer>(),
                    path2=new Vector<Integer>();
    int x = m - 1;
 
    // push node i in path1
    path1.add(i);
 
    // keep pushing parent of node labelled
    // as i to path1 until lca is reached
    while (x != k)
    {
        path1.add(i / 2);
        i = i / 2;
        x--;
    }
    int y = n - 1;
 
    // push node j to path2
    path2.add(j);
 
    // keep pushing parent of node j till
    // lca is reached
    while (y != k)
    {
        path2.add(j / 2);
        j = j / 2;
        y--;
    }
 
    // printing path from node i to lca
    for (int l = 0; l < path1.size(); l++)
        System.out.print( path1.get(l) + " ");
 
    // printing path from lca to node j
    for (int l = path2.size() - 2; l >= 0; l--)
        System.out.print( path2.get(l) + " ");
    System.out.println();
}
 
// returns the shortest distance between
// nodes labelled as i and j
static int ShortestDistance(int i, int j)
{
    // vector to store binary form of i and j
    Vector<Integer> v1=new Vector<Integer>(),
                    v2=new Vector<Integer>();
 
    // finding binary form of i and j
    int p1 = i;
    int p2 = j;
    while (i != 0)
    {
        v1.add(i % 2);
        i = i / 2;
    }
    while (j != 0)
    {
        v2.add(j % 2);
        j = j / 2;
    }
 
    // as binary form will be in reverse order
    // reverse the vectors
    Collections.reverse(v1);
    Collections.reverse(v2);
 
    // finding the k that is lca (i, j)
    int m = v1.size(), n = v2.size(), k = 0;
    if (m < n)
    {
        while (k < m && v1.get(k) == v2.get(k))
            k++;
    }
    else
    {
        while (k < n && v1.get(k) == v2.get(k))
            k++;
    }
 
    ShortestPath(p1, p2, k - 1, m, n);
    return m + n - 2 * k;
}
 
// Driver code
public static void main(String args[])
{
    System.out.println( ShortestDistance(1, 2) );
    System.out.println(ShortestDistance(4, 3) );
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 representation of finding
# shortest distance between node i and j
 
# Prints the path between node i and node j
def ShortestPath(i, j, k, m, n):
 
    # path1 stores path of node i to lca and
    # path2 stores path of node j to lca
    path1, path2 = [], []
    x = m - 1
 
    # push node i in path1
    path1.append(i)
 
    # keep pushing parent of node labelled
    # as i to path1 until lca is reached
    while x != k:
        path1.append(i // 2)
        i = i // 2
        x -= 1
     
    y = n - 1
 
    # push node j to path2
    path2.append(j)
 
    # keep pushing parent of node
    # j till lca is reached
    while y != k:
        path2.append(j / 2)
        j = j // 2
        y -= 1
     
    # printing path from node i to lca
    for l in range(0, len(path1)):
        print(path1[l], end=" ")
 
    # printing path from lca to node j
    for l in range(len(path2) - 2, -1, -1):
        print(path2[l], end=" ")
    print()
 
# Returns the shortest distance
# between nodes labelled as i and j
def ShortestDistance(i, j):
 
    # vector to store binary form of i and j
    v1, v2 = [], []
 
    # finding binary form of i and j
    p1, p2 = i, j
    while i != 0:
        v1.append(i % 2)
        i = i // 2
     
    while j != 0:
        v2.append(j % 2)
        j = j // 2
     
    # as binary form will be in reverse
    # order reverse the vectors
    v1 = v1[::-1]
    v2 = v2[::-1]
 
    # finding the k that is lca (i, j)
    m, n, k = len(v1), len(v2), 0
    if m < n:
        while k < m and v1[k] == v2[k]:
            k += 1
     
    else:
        while k < n and v1[k] == v2[k]:
            k += 1
     
    ShortestPath(p1, p2, k - 1, m, n)
    return m + n - 2 * k
 
# Driver Code
if __name__ == "__main__":
 
    print(ShortestDistance(1, 2))
    print(ShortestDistance(4, 3))
 
# This code is contributed by Rituraj Jain

C#

// C#  representation of finding shortest
// distance between node i and j
using System;
using System.Collections.Generic;   
     
class GFG
{
      
// prints the path between node i and node j
static void ShortestPath(int i, int j, int k, int m,
                                    int n)
{
    // path1 stores path of node i to lca and
    // path2 stores path of node j to lca
    List<int> path1=new List<int>(),
                    path2=new List<int>();
    int x = m - 1;
  
    // push node i in path1
    path1.Add(i);
  
    // keep pushing parent of node labelled
    // as i to path1 until lca is reached
    while (x != k)
    {
        path1.Add(i / 2);
        i = i / 2;
        x--;
    }
    int y = n - 1;
  
    // push node j to path2
    path2.Add(j);
  
    // keep pushing parent of node j till
    // lca is reached
    while (y != k)
    {
        path2.Add(j / 2);
        j = j / 2;
        y--;
    }
  
    // printing path from node i to lca
    for (int l = 0; l < path1.Count; l++)
        Console.Write( path1[l] + " ");
  
    // printing path from lca to node j
    for (int l = path2.Count - 2; l >= 0; l--)
        Console.Write( path2[l] + " ");
    Console.WriteLine();
}
  
// returns the shortest distance between
// nodes labelled as i and j
static int ShortestDistance(int i, int j)
{
    // vector to store binary form of i and j
    List<int> v1=new List<int>(),
                    v2=new List<int>();
  
    // finding binary form of i and j
    int p1 = i;
    int p2 = j;
    while (i != 0)
    {
        v1.Add(i % 2);
        i = i / 2;
    }
    while (j != 0)
    {
        v2.Add(j % 2);
        j = j / 2;
    }
  
    // as binary form will be in reverse order
    // reverse the vectors
    v1.Reverse();
    v2.Reverse();
  
    // finding the k that is lca (i, j)
    int m =v1.Count, n =v2.Count, k = 0;
    if (m < n)
    {
        while (k < m && v1[k] == v2[k])
            k++;
    }
    else
    {
        while (k < n && v1[k] == v2[k])
            k++;
    }
  
    ShortestPath(p1, p2, k - 1, m, n);
    return m + n - 2 * k;
}
  
// Driver code
public static void Main(String []args)
{
    Console.WriteLine( ShortestDistance(1, 2) );
    Console.WriteLine(ShortestDistance(4, 3) );
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript  representation of finding shortest
// distance between node i and j
 
// prints the path between node i and node j
function ShortestPath(i,j,k,m,n)
{
    // path1 stores path of node i to lca and
    // path2 stores path of node j to lca
    let path1=[];
    let path2=[];
    let x = m - 1;
   
    // push node i in path1
    path1.push(i);
   
    // keep pushing parent of node labelled
    // as i to path1 until lca is reached
    while (x != k)
    {
        path1.push(Math.floor(i / 2));
        i = Math.floor(i / 2);
        x--;
    }
    let y = n - 1;
   
    // push node j to path2
    path2.push(j);
   
    // keep pushing parent of node j till
    // lca is reached
    while (y != k)
    {
        path2.push(Math.floor(j / 2));
        j = Math.floor(j / 2);
        y--;
    }
   
    // printing path from node i to lca
    for (let l = 0; l < path1.length; l++)
        document.write( path1[l] + " ");
   
    // printing path from lca to node j
    for (let l = path2.length - 2; l >= 0; l--)
        document.write( path2[l] + " ");
    document.write("<br>");
}
 
// returns the shortest distance between
// nodes labelled as i and j
function ShortestDistance(i,j)
{
    // vector to store binary form of i and j
    let v1=[];
    let v2=[];
   
    // finding binary form of i and j
    let p1 = i;
    let p2 = j;
    while (i != 0)
    {
        v1.push(i % 2);
        i = Math.floor(i / 2);
    }
    while (j != 0)
    {
        v2.push(j % 2);
        j = Math.floor(j / 2);
    }
   
    // as binary form will be in reverse order
    // reverse the vectors
    v1.reverse();
    v2.reverse();
   
    // finding the k that is lca (i, j)
    let m =v1.length, n =v2.length, k = 0;
    if (m < n)
    {
        while (k < m && v1[k] == v2[k])
            k++;
    }
    else
    {
        while (k < n && v1[k] == v2[k])
            k++;
    }
   
    ShortestPath(p1, p2, k - 1, m, n);
    return m + n - 2 * k;
}
 
// Driver code
document.write( ShortestDistance(1, 2) +"<br>");
document.write(ShortestDistance(4, 3) +"<br>");
 
 
// This code is contributed by avanitrachhadiya2155
</script>

Producción: 
 

1 2
1
4 2 1 3
3

Análisis de Complejidad:
Complejidad de Tiempo: O(registro_2 i + registro_2 j) ya que estamos cambiando el valor de i y j a la derecha para cada recorrido

Espacio auxiliar: O(log_2 i + log_2 j) ya que estamos almacenando rutas para cada valor de desplazamiento a la derecha de i y j .

Este artículo es una contribución de Ayush Jha . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *