Dado un árbol binario, la tarea es encontrar el antepasado común más bajo de los dos Nodes dados en el árbol.
Sea G un árbol, entonces el LCA de dos Nodes u y v se define como el Node w en el árbol que es un ancestro de u y v y está más alejado del Node raíz. Si un Node es el ancestro de otro que ese Node particular es el LCA de esos dos Nodes.
Ejemplo:
Aporte:
Salida:
El LCA de 6 y 9 es 1.
El LCA de 5 y 9 es 1.
El LCA de 6 y 8 es 3.
El LCA de 6 y 1 es 1.
Enfoque: el artículo describe un enfoque conocido como elevación binaria para encontrar el antepasado común más bajo de dos Nodes en un árbol. Puede haber muchos enfoques para resolver el problema de LCA. Estamos discutiendo la técnica de elevación binaria, las otras se pueden leer aquí y aquí .
Binary Lifting es un enfoque de programación dinámica en el que precalculamos una array memo[1, n][1, log(n)] donde memo[i][j] contiene el 2^j-ésimo ancestro del Node i. Para calcular los valores de memo[][], se puede usar la siguiente recursión
estado de la nota:
memo[i][j] = i-ésimo ancestro del Node 2^(j) en la ruta
inicialización de notas:
memo[i][j] = memo[i][0] (se da el primer padre (2^0) de cada Node)
memo trans:
nota[i][j] = nota[ nota [i][j – 1]]
significado: A(i,2^j)=A( A(i , 2^(j-1) ) , 2^(j-1) )
Para encontrar el (2^j)-ésimo ancestro de i, busque recursivamente el 2^(j-1)-ésimo ancestro del i-ésimo Node y el 2^(j-1)-ésimo ancestro del Node i. (2^(j) = 2^(j-1) + 2^(j-1))
Asi que:
memo[i][j] = padre[i] si j = 0 y
memo[i][j] = memo[memo[i][j – 1]][j – 1] si j > 0.
Primero verificamos si un Node es un ancestro de otro o no y si un Node es un ancestro de otro, entonces es el LCA de estos dos Nodes; de lo contrario, encontramos un Node que no es el ancestro común de u y v y es más alto ( es decir, un Node x tal que x no es el ancestro común de uyv pero memo[x][0] lo es) en el árbol. Después de encontrar dicho Node (que sea x), imprimimos el primer ancestro de x, es decir, memo[x][0], que será el LCA requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Pre-processing to calculate values of memo[][]
void dfs(int u, int p, int **memo, int *lev, int log, vector<int> *g)
{
// Using recursion formula to calculate
// the values of memo[][]
memo[u][0] = p;
for (int i = 1; i <= log; i++)
memo[u][i] = memo[memo[u][i - 1]][i - 1];
for (int v : g[u])
{
if (v != p)
{
lev[v] = lev[u] + 1;
dfs(v, u, memo, lev, log, g);
}
}
}
// Function to return the LCA of nodes u and v
int lca(int u, int v, int log, int *lev, int **memo)
{
// The node which is present farthest
// from the root node is taken as u
// If v is farther from root node
// then swap the two
if (lev[u] < lev[v])
swap(u, v);
// Finding the ancestor of u
// which is at same level as v
for (int i = log; i >= 0; i--)
if ((lev[u] - pow(2, i)) >= lev[v])
u = memo[u][i];
// If v is the ancestor of u
// then v is the LCA of u and v
if (u == v)
return u;
// Finding the node closest to the root which is
// not the common ancestor of u and v i.e. a node
// x such that x is not the common ancestor of u
// and v but memo[x][0] is
for (int i = log; i >= 0; i--)
{
if (memo[u][i] != memo[v][i])
{
u = memo[u][i];
v = memo[v][i];
}
}
// Returning the first ancestor
// of above found node
return memo[u][0];
}
// Driver Code
int main()
{
// Number of nodes
int n = 9;
// vector to store tree
vector<int> g[n + 1];
int log = (int)ceil(log2(n));
int **memo = new int *[n + 1];
for (int i = 0; i < n + 1; i++)
memo[i] = new int[log + 1];
// Stores the level of each node
int *lev = new int[n + 1];
// Initialising memo values with -1
for (int i = 0; i <= n; i++)
memset(memo[i], -1, sizeof memo[i]);
// Add edges
g[1].push_back(2);
g[2].push_back(1);
g[1].push_back(3);
g[3].push_back(1);
g[1].push_back(4);
g[4].push_back(1);
g[2].push_back(5);
g[5].push_back(2);
g[3].push_back(6);
g[6].push_back(3);
g[3].push_back(7);
g[7].push_back(3);
g[3].push_back(8);
g[8].push_back(3);
g[4].push_back(9);
g[9].push_back(4);
dfs(1, 1, memo, lev, log, g);
cout << "The LCA of 6 and 9 is " << lca(6, 9, log, lev, memo) << endl;
cout << "The LCA of 5 and 9 is " << lca(5, 9, log, lev, memo) << endl;
cout << "The LCA of 6 and 8 is " << lca(6, 8, log, lev, memo) << endl;
cout << "The LCA of 6 and 1 is " << lca(6, 1, log, lev, memo) << endl;
return 0;
}
// This code is contributed by
// sanjeev2552
Java
// Java implementation of the approach
import java.util.*;
public class GFG {
// ArrayList to store tree
static ArrayList<Integer> g[];
static int memo[][], lev[], log;
// Pre-processing to calculate values of memo[][]
static void dfs(int u, int p)
{
// Using recursion formula to calculate
// the values of memo[][]
memo[u][0] = p;
for (int i = 1; i <= log; i++)
memo[u][i] = memo[memo[u][i - 1]][i - 1];
for (int v : g[u]) {
if (v != p) {
// Calculating the level of each node
lev[v] = lev[u] + 1;
dfs(v, u);
}
}
}
// Function to return the LCA of nodes u and v
static int lca(int u, int v)
{
// The node which is present farthest
// from the root node is taken as u
// If v is farther from root node
// then swap the two
if (lev[u] < lev[v]) {
int temp = u;
u = v;
v = temp;
}
// Finding the ancestor of u
// which is at same level as v
for (int i = log; i >= 0; i--) {
if ((lev[u] - (int)Math.pow(2, i)) >= lev[v])
u = memo[u][i];
}
// If v is the ancestor of u
// then v is the LCA of u and v
if (u == v)
return u;
// Finding the node closest to the root which is
// not the common ancestor of u and v i.e. a node
// x such that x is not the common ancestor of u
// and v but memo[x][0] is
for (int i = log; i >= 0; i--) {
if (memo[u][i] != memo[v][i]) {
u = memo[u][i];
v = memo[v][i];
}
}
// Returning the first ancestor
// of above found node
return memo[u][0];
}
// Driver code
public static void main(String args[])
{
// Number of nodes
int n = 9;
g = new ArrayList[n + 1];
// log(n) with base 2
log = (int)Math.ceil(Math.log(n) / Math.log(2));
memo = new int[n + 1][log + 1];
// Stores the level of each node
lev = new int[n + 1];
// Initialising memo values with -1
for (int i = 0; i <= n; i++)
Arrays.fill(memo[i], -1);
for (int i = 0; i <= n; i++)
g[i] = new ArrayList<>();
// Add edges
g[1].add(2);
g[2].add(1);
g[1].add(3);
g[3].add(1);
g[1].add(4);
g[4].add(1);
g[2].add(5);
g[5].add(2);
g[3].add(6);
g[6].add(3);
g[3].add(7);
g[7].add(3);
g[3].add(8);
g[8].add(3);
g[4].add(9);
g[9].add(4);
dfs(1, 1);
System.out.println("The LCA of 6 and 9 is " + lca(6, 9));
System.out.println("The LCA of 5 and 9 is " + lca(5, 9));
System.out.println("The LCA of 6 and 8 is " + lca(6, 8));
System.out.println("The LCA of 6 and 1 is " + lca(6, 1));
}
}
Python3
# Python3 implementation of the above approach
import math
# Pre-processing to calculate values of memo[][]
def dfs(u, p, memo, lev, log, g):
# Using recursion formula to calculate
# the values of memo[][]
memo[u][0] = p
for i in range(1, log + 1):
memo[u][i] = memo[memo[u][i - 1]][i - 1]
for v in g[u]:
if v != p:
lev[v] = lev[u] + 1
dfs(v, u, memo, lev, log, g)
# Function to return the LCA of nodes u and v
def lca(u, v, log, lev, memo):
# The node which is present farthest
# from the root node is taken as u
# If v is farther from root node
# then swap the two
if lev[u] < lev[v]:
swap(u, v)
# Finding the ancestor of u
# which is at same level as v
for i in range(log, -1, -1):
if (lev[u] - pow(2, i)) >= lev[v]:
u = memo[u][i]
# If v is the ancestor of u
# then v is the LCA of u and v
if u == v:
return v
# Finding the node closest to the
# root which is not the common ancestor
# of u and v i.e. a node x such that x
# is not the common ancestor of u
# and v but memo[x][0] is
for i in range(log, -1, -1):
if memo[u][i] != memo[v][i]:
u = memo[u][i]
v = memo[v][i]
# Returning the first ancestor
# of above found node
return memo[u][0]
# Driver code
# Number of nodes
n = 9
log = math.ceil(math.log(n, 2))
g = [[] for i in range(n + 1)]
memo = [[-1 for i in range(log + 1)]
for j in range(n + 1)]
# Stores the level of each node
lev = [0 for i in range(n + 1)]
# Add edges
g[1].append(2)
g[2].append(1)
g[1].append(3)
g[3].append(1)
g[1].append(4)
g[4].append(1)
g[2].append(5)
g[5].append(2)
g[3].append(6)
g[6].append(3)
g[3].append(7)
g[7].append(3)
g[3].append(8)
g[8].append(3)
g[4].append(9)
g[9].append(4)
dfs(1, 1, memo, lev, log, g)
print("The LCA of 6 and 9 is", lca(6, 9, log, lev, memo))
print("The LCA of 5 and 9 is", lca(5, 9, log, lev, memo))
print("The LCA of 6 and 8 is", lca(6, 8, log, lev, memo))
print("The LCA of 6 and 1 is", lca(6, 1, log, lev, memo))
# This code is contributed by Bhaskar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// List to store tree
static List<int> []g;
static int [,]memo;
static int []lev;
static int log;
// Pre-processing to calculate
// values of memo[,]
static void dfs(int u, int p)
{
// Using recursion formula to
// calculate the values of memo[,]
memo[u, 0] = p;
for (int i = 1; i <= log; i++)
memo[u, i] = memo[memo[u, i - 1],
i - 1];
foreach (int v in g[u])
{
if (v != p)
{
// Calculating the level of each node
lev[v] = lev[u] + 1;
dfs(v, u);
}
}
}
// Function to return the LCA of
// nodes u and v
static int lca(int u, int v)
{
// The node which is present farthest
// from the root node is taken as u
// If v is farther from root node
// then swap the two
if (lev[u] < lev[v])
{
int temp = u;
u = v;
v = temp;
}
// Finding the ancestor of u
// which is at same level as v
for (int i = log; i >= 0; i--)
{
if ((lev[u] - (int)Math.Pow(2, i)) >= lev[v])
u = memo[u, i];
}
// If v is the ancestor of u
// then v is the LCA of u and v
if (u == v)
return u;
// Finding the node closest to the root
// which is not the common ancestor of
// u and v i.e. a node x such that
// x is not the common ancestor of u
// and v but memo[x,0] is
for (int i = log; i >= 0; i--)
{
if (memo[u, i] != memo[v, i])
{
u = memo[u, i];
v = memo[v, i];
}
}
// Returning the first ancestor
// of above found node
return memo[u, 0];
}
// Driver code
public static void Main(String []args)
{
// Number of nodes
int n = 9;
g = new List<int>[n + 1];
// log(n) with base 2
log = (int)Math.Ceiling(Math.Log(n) / Math.Log(2));
memo = new int[n + 1, log + 1];
// Stores the level of each node
lev = new int[n + 1];
// Initialising memo values with -1
for (int i = 0; i <= n; i++)
for (int j = 0; j <= log; j++)
memo[i, j] = -1;
for (int i = 0; i <= n; i++)
g[i] = new List<int>();
// Add edges
g[1].Add(2);
g[2].Add(1);
g[1].Add(3);
g[3].Add(1);
g[1].Add(4);
g[4].Add(1);
g[2].Add(5);
g[5].Add(2);
g[3].Add(6);
g[6].Add(3);
g[3].Add(7);
g[7].Add(3);
g[3].Add(8);
g[8].Add(3);
g[4].Add(9);
g[9].Add(4);
dfs(1, 1);
Console.WriteLine("The LCA of 6 and 9 is " +
lca(6, 9));
Console.WriteLine("The LCA of 5 and 9 is " +
lca(5, 9));
Console.WriteLine("The LCA of 6 and 8 is " +
lca(6, 8));
Console.WriteLine("The LCA of 6 and 1 is " +
lca(6, 1));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation of the approach
// ArrayList to store tree
let g;
let memo, lev, log;
// Pre-processing to calculate values of memo[][]
function dfs(u, p)
{
// Using recursion formula to calculate
// the values of memo[][]
memo[u][0] = p;
for (let i = 1; i <= log; i++)
memo[u][i] = memo[memo[u][i - 1]][i - 1];
for (let v = 0; v < g[u].length; v++) {
if (g[u][v] != p) {
// Calculating the level of each node
lev[g[u][v]] = lev[u] + 1;
dfs(g[u][v], u);
}
}
}
// Function to return the LCA of nodes u and v
function lca(u, v)
{
// The node which is present farthest
// from the root node is taken as u
// If v is farther from root node
// then swap the two
if (lev[u] < lev[v]) {
let temp = u;
u = v;
v = temp;
}
// Finding the ancestor of u
// which is at same level as v
for (let i = log; i >= 0; i--) {
if ((lev[u] - Math.pow(2, i)) >= lev[v])
u = memo[u][i];
}
// If v is the ancestor of u
// then v is the LCA of u and v
if (u == v)
return u;
// Finding the node closest to the root which is
// not the common ancestor of u and v i.e. a node
// x such that x is not the common ancestor of u
// and v but memo[x][0] is
for (let i = log; i >= 0; i--) {
if (memo[u][i] != memo[v][i]) {
u = memo[u][i];
v = memo[v][i];
}
}
// Returning the first ancestor
// of above found node
return memo[u][0];
}
// Number of nodes
let n = 9;
g = new Array(n + 1);
// log(n) with base 2
log = Math.ceil(Math.log(n) / Math.log(2));
memo = new Array(n + 1);
// Stores the level of each node
lev = new Array(n + 1);
lev.fill(0);
// Initialising memo values with -1
for (let i = 0; i <= n; i++)
{
memo[i] = new Array(log+1);
for (let j = 0; j < log+1; j++)
{
memo[i][j] = -1;
}
}
for (let i = 0; i <= n; i++)
g[i] = [];
// Add edges
g[1].push(2);
g[2].push(1);
g[1].push(3);
g[3].push(1);
g[1].push(4);
g[4].push(1);
g[2].push(5);
g[5].push(2);
g[3].push(6);
g[6].push(3);
g[3].push(7);
g[7].push(3);
g[3].push(8);
g[8].push(3);
g[4].push(9);
g[9].push(4);
dfs(1, 1);
document.write("The LCA of 6 and 9 is " + lca(6, 9) + "</br>");
document.write("The LCA of 5 and 9 is " + lca(5, 9) + "</br>");
document.write("The LCA of 6 and 8 is " + lca(6, 8) + "</br>");
document.write("The LCA of 6 and 1 is " + lca(6, 1));
</script>
Producción:
The LCA of 6 and 9 is 1 The LCA of 5 and 9 is 1 The LCA of 6 and 8 is 3 The LCA of 6 and 1 is 1
Complejidad del tiempo: el tiempo necesario para el preprocesamiento es O (NlogN) y cada consulta lleva un tiempo O (logN). Entonces, la complejidad de tiempo general de la solución es O (NlogN).
Espacio Auxiliar: O(NlogN)
Publicación traducida automáticamente
Artículo escrito por Amol_Pratap y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA