El artículo describe un enfoque para resolver el problema de encontrar el LCA de dos Nodes en un árbol reduciéndolo a un problema de RMQ.
El ancestro común más bajo (LCA) de dos Nodes u y v en un árbol con raíz T se define como el Node ubicado más lejos de la raíz que tiene u y v como descendientes.
Por ejemplo, en el siguiente diagrama, el LCA del Node 4 y el Node 9 es el Node 2.
Puede haber muchos enfoques para resolver el problema de LCA. Los enfoques difieren en sus complejidades de tiempo y espacio. Aquí hay un enlace a un par de ellos (estos no implican una reducción a RMQ).
La consulta de rango mínimo (RMQ) se usa en arrays para encontrar la posición de un elemento con el valor mínimo entre dos índices especificados. Se han discutido diferentes enfoques para resolver RMQ aquí y aquí . En este artículo, se analiza el enfoque basado en el árbol de segmentos. Con un árbol de segmentos, el tiempo de preprocesamiento es O(n) y el tiempo para la consulta mínima de rango es O(Logn). El espacio adicional requerido es O(n) para almacenar el árbol de segmentos.
Reducción de LCA a RMQ:
La idea es recorrer el árbol a partir de la raíz mediante un recorrido de Euler (recorrido sin levantar un lápiz), que es un recorrido de tipo DFS con características de recorrido de preorden.
Observación :
El LCA de los Nodes 4 y 9 es el Node 2, que resulta ser el Node más cercano a la raíz entre todos los encontrados entre las visitas 4 y 9 durante un DFS de T. Esta observación es la clave de la reducción. Reformulemos: nuestro Node es el Node en el nivel más pequeño y el único Node en ese nivel entre todos los Nodes que ocurren entre ocurrencias consecutivas (cualquiera) de u y v en el recorrido de Euler de T.
Requerimos tres arrays para la implementación:
- Nodes visitados en orden de recorrido de Euler por T
- El nivel de cada Node visitado en el recorrido de Euler de T
- Índice de la primera aparición de un Node en el recorrido de Euler por T (dado que cualquier aparición sería buena, sigamos la primera)
Algoritmo:
- Realice un recorrido de Euler en el árbol y complete las arrays de euler, nivel y primera aparición.
- Usando la primera array de aparición, obtenga los índices correspondientes a los dos Nodes que serán las esquinas del rango en la array de nivel que se alimenta al algoritmo RMQ para el valor mínimo.
- Una vez que el algoritmo devuelve el índice del nivel mínimo en el rango, lo usamos para determinar el LCA usando la array de recorrido de Euler.
A continuación se muestra la implementación del algoritmo anterior.
C++
/* C++ Program to find LCA of u and v by reducing the problem to RMQ */
#include<bits/stdc++.h>
#define V 9 // number of nodes in input tree
int euler[2*V - 1]; // For Euler tour sequence
int level[2*V - 1]; // Level of nodes in tour sequence
int firstOccurrence[V+1]; // First occurrences of nodes in tour
int ind; // Variable to fill-in euler and level arrays
// A Binary Tree node
struct Node
{
int key;
struct Node *left, *right;
};
// Utility function creates a new binary tree node with given key
Node * newNode(int k)
{
Node *temp = new Node;
temp->key = k;
temp->left = temp->right = NULL;
return temp;
}
// log base 2 of x
int Log2(int x)
{
int ans = 0 ;
while (x>>=1) ans++;
return ans ;
}
/* A recursive function to get the minimum value in a given range
of array indexes. The following are parameters for this function.
st --> Pointer to segment tree
index --> Index of current node in the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending indexes of the segment represented
by current node, i.e., st[index]
qs & qe --> Starting and ending indexes of query range */
int RMQUtil(int index, int ss, int se, int qs, int qe, int *st)
{
// If segment of this node is a part of given range, then return
// the min of the segment
if (qs <= ss && qe >= se)
return st[index];
// If segment of this node is outside the given range
else if (se < qs || ss > qe)
return -1;
// If a part of this segment overlaps with the given range
int mid = (ss + se)/2;
int q1 = RMQUtil(2*index+1, ss, mid, qs, qe, st);
int q2 = RMQUtil(2*index+2, mid+1, se, qs, qe, st);
if (q1==-1) return q2;
else if (q2==-1) return q1;
return (level[q1] < level[q2]) ? q1 : q2;
}
// Return minimum of elements in range from index qs (query start) to
// qe (query end). It mainly uses RMQUtil()
int RMQ(int *st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n-1 || qs > qe)
{
printf("Invalid Input");
return -1;
}
return RMQUtil(0, 0, n-1, qs, qe, st);
}
// A recursive function that constructs Segment Tree for array[ss..se].
// si is index of current node in segment tree st
void constructSTUtil(int si, int ss, int se, int arr[], int *st)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se)st[si] = ss;
else
{
// If there are more than one elements, then recur for left and
// right subtrees and store the minimum of two values in this node
int mid = (ss + se)/2;
constructSTUtil(si*2+1, ss, mid, arr, st);
constructSTUtil(si*2+2, mid+1, se, arr, st);
if (arr[st[2*si+1]] < arr[st[2*si+2]])
st[si] = st[2*si+1];
else
st[si] = st[2*si+2];
}
}
/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
int *constructST(int arr[], int n)
{
// Allocate memory for segment tree
// Height of segment tree
int x = Log2(n)+1;
// Maximum size of segment tree
int max_size = 2*(1<<x) - 1; // 2*pow(2,x) -1
int *st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(0, 0, n-1, arr, st);
// Return the constructed segment tree
return st;
}
// Recursive version of the Euler tour of T
void eulerTour(Node *root, int l)
{
/* if the passed node exists */
if (root)
{
euler[ind] = root->key; // insert in euler array
level[ind] = l; // insert l in level array
ind++; // increment index
/* if unvisited, mark first occurrence */
if (firstOccurrence[root->key] == -1)
firstOccurrence[root->key] = ind-1;
/* tour left subtree if exists, and remark euler
and level arrays for parent on return */
if (root->left)
{
eulerTour(root->left, l+1);
euler[ind]=root->key;
level[ind] = l;
ind++;
}
/* tour right subtree if exists, and remark euler
and level arrays for parent on return */
if (root->right)
{
eulerTour(root->right, l+1);
euler[ind]=root->key;
level[ind] = l;
ind++;
}
}
}
// Returns LCA of nodes n1, n2 (assuming they are
// present in the tree)
int findLCA(Node *root, int u, int v)
{
/* Mark all nodes unvisited. Note that the size of
firstOccurrence is 1 as node values which vary from
1 to 9 are used as indexes */
memset(firstOccurrence, -1, sizeof(int)*(V+1));
/* To start filling euler and level arrays from index 0 */
ind = 0;
/* Start Euler tour with root node on level 0 */
eulerTour(root, 0);
/* construct segment tree on level array */
int *st = constructST(level, 2*V-1);
/* If v before u in Euler tour. For RMQ to work, first
parameter 'u' must be smaller than second 'v' */
if (firstOccurrence[u]>firstOccurrence[v])
std::swap(u, v);
// Starting and ending indexes of query range
int qs = firstOccurrence[u];
int qe = firstOccurrence[v];
// query for index of LCA in tour
int index = RMQ(st, 2*V-1, qs, qe);
/* return LCA node */
return euler[index];
}
// Driver program to test above functions
int main()
{
// Let us create the Binary Tree as shown in the diagram.
Node * root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->left->right->left = newNode(8);
root->left->right->right = newNode(9);
int u = 4, v = 9;
printf("The LCA of node %d and node %d is node %d.\n",
u, v, findLCA(root, u, v));
return 0;
}
Java
// Java program to find LCA of u and v by reducing problem to RMQ
import java.util.*;
// A binary tree node
class Node
{
Node left, right;
int data;
Node(int item)
{
data = item;
left = right = null;
}
}
class St_class
{
int st;
int stt[] = new int[10000];
}
class BinaryTree
{
Node root;
int v = 9; // v is the highest value of node in our tree
int euler[] = new int[2 * v - 1]; // for euler tour sequence
int level[] = new int[2 * v - 1]; // level of nodes in tour sequence
int f_occur[] = new int[2 * v - 1]; // to store 1st occurrence of nodes
int fill; // variable to fill euler and level arrays
St_class sc = new St_class();
// log base 2 of x
int Log2(int x)
{
int ans = 0;
int y = x >>= 1;
while (y-- != 0)
ans++;
return ans;
}
int swap(int a, int b)
{
return a;
}
/* A recursive function to get the minimum value in a given range
of array indexes. The following are parameters for this function.
st --> Pointer to segment tree
index --> Index of current node in the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending indexes of the segment represented
by current node, i.e., st[index]
qs & qe --> Starting and ending indexes of query range */
int RMQUtil(int index, int ss, int se, int qs, int qe, St_class st)
{
// If segment of this node is a part of given range, then return
// the min of the segment
if (qs <= ss && qe >= se)
return st.stt[index];
// If segment of this node is outside the given range
else if (se < qs || ss > qe)
return -1;
// If a part of this segment overlaps with the given range
int mid = (ss + se) / 2;
int q1 = RMQUtil(2 * index + 1, ss, mid, qs, qe, st);
int q2 = RMQUtil(2 * index + 2, mid + 1, se, qs, qe, st);
if (q1 == -1)
return q2;
else if (q2 == -1)
return q1;
return (level[q1] < level[q2]) ? q1 : q2;
}
// Return minimum of elements in range from index qs (query start) to
// qe (query end). It mainly uses RMQUtil()
int RMQ(St_class st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe)
{
System.out.println("Invalid input");
return -1;
}
return RMQUtil(0, 0, n - 1, qs, qe, st);
}
// A recursive function that constructs Segment Tree for array[ss..se].
// si is index of current node in segment tree st
void constructSTUtil(int si, int ss, int se, int arr[], St_class st)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se)
st.stt[si] = ss;
else
{
// If there are more than one elements, then recur for left and
// right subtrees and store the minimum of two values in this node
int mid = (ss + se) / 2;
constructSTUtil(si * 2 + 1, ss, mid, arr, st);
constructSTUtil(si * 2 + 2, mid + 1, se, arr, st);
if (arr[st.stt[2 * si + 1]] < arr[st.stt[2 * si + 2]])
st.stt[si] = st.stt[2 * si + 1];
else
st.stt[si] = st.stt[2 * si + 2];
}
}
/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
int constructST(int arr[], int n)
{
// Allocate memory for segment tree
// Height of segment tree
int x = Log2(n) + 1;
// Maximum size of segment tree
int max_size = 2 * (1 << x) - 1; // 2*pow(2,x) -1
sc.stt = new int[max_size];
// Fill the allocated memory st
constructSTUtil(0, 0, n - 1, arr, sc);
// Return the constructed segment tree
return sc.st;
}
// Recursive version of the Euler tour of T
void eulerTour(Node node, int l)
{
/* if the passed node exists */
if (node != null)
{
euler[fill] = node.data; // insert in euler array
level[fill] = l; // insert l in level array
fill++; // increment index
/* if unvisited, mark first occurrence */
if (f_occur[node.data] == -1)
f_occur[node.data] = fill - 1;
/* tour left subtree if exists, and remark euler
and level arrays for parent on return */
if (node.left != null)
{
eulerTour(node.left, l + 1);
euler[fill] = node.data;
level[fill] = l;
fill++;
}
/* tour right subtree if exists, and remark euler
and level arrays for parent on return */
if (node.right != null)
{
eulerTour(node.right, l + 1);
euler[fill] = node.data;
level[fill] = l;
fill++;
}
}
}
// returns LCA of node n1 and n2 assuming they are present in tree
int findLCA(Node node, int u, int v)
{
/* Mark all nodes unvisited. Note that the size of
firstOccurrence is 1 as node values which vary from
1 to 9 are used as indexes */
Arrays.fill(f_occur, -1);
/* To start filling euler and level arrays from index 0 */
fill = 0;
/* Start Euler tour with root node on level 0 */
eulerTour(root, 0);
/* construct segment tree on level array */
sc.st = constructST(level, 2 * v - 1);
/* If v before u in Euler tour. For RMQ to work, first
parameter 'u' must be smaller than second 'v' */
if (f_occur[u] > f_occur[v])
u = swap(u, u = v);
// Starting and ending indexes of query range
int qs = f_occur[u];
int qe = f_occur[v];
// query for index of LCA in tour
int index = RMQ(sc, 2 * v - 1, qs, qe);
/* return LCA node */
return euler[index];
}
// Driver program to test above functions
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
// Let us create the Binary Tree as shown in the diagram.
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.left.right.left = new Node(8);
tree.root.left.right.right = new Node(9);
int u = 4, v = 9;
System.out.println("The LCA of node " + u + " and " + v + " is "
+ tree.findLCA(tree.root, u, v));
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Python3 program to find LCA of u and v by
# reducing the problem to RMQ
from math import log2, floor
from typing import List
class Node:
def __init__(self, val: int):
self.val, self.left, self.right = val, None, None
class BinaryTree:
def __init__(self, root: Node):
self.root = root
self.val_max = self._get_max_val()
self.euler = [0] * (2 * self.val_max - 1)
self.level = [0] * (2 * self.val_max - 1)
self.f_occur = [-1] * (self.val_max + 1)
self.fill = 0
self.segment_tree = []
def _get_max_val(self):
stack = [self.root]
max_val = -1
while stack:
x = stack.pop()
if x.val > max_val:
max_val = x.val
if x.left:
stack.append(x.left)
if x.right:
stack.append(x.right)
return max_val
''' A recursive function to get the minimum value in a given range
of array indexes. The following are parameters for this function.
st --> Pointer to segment tree
index --> Index of current node in the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending indexes of the segment represented
by current node, i.e., st[index]
qs & qe --> Starting and ending indexes of query range '''
def rmq_util(self, index, ss, se, qs, qe) -> int:
# If segment of this node is part of given range
# then return the min of the segment
if qs <= ss and qe >= se:
return self.segment_tree[index]
# If segment of this node is outside
# the given range
elif se < qs or ss > qe:
return -1
# If part of this segment overlaps with
# given range
mid = (ss + se) // 2
q1 = self.rmq_util(2 * index + 1,
ss, mid, qs, qe)
q2 = self.rmq_util(2 * index + 2, mid + 1,
se, qs, qe)
if q1 == -1:
return q2
if q2 == -1:
return q1
return (q1 if self.level[q1] <
self.level[q2] else q2)
# Return minimum of elements in range from
# index qs (query start) to qe (query end).
# It mainly uses rmq_util()
def rmq(self, n: int, qs: int, qe: int) -> int:
if qs < 0 or qe > n - 1 or qs > qe:
print('invalid input')
return -1
return self.rmq_util(0, 0, n - 1, qs, qe)
# A recursive function that constructs Segment
# Tree for array[ss..se]. si is index of
# current node in segment tree st
def construct_segment_tree_util(self, si, ss,
se, arr):
# If there is one element in array,
# store it in current node of segment tree
# and return
if ss == se:
self.segment_tree[si] = ss
else:
# If there are more than one elements,
# then recur for left and right subtrees and
# store the min of two values in this node
mid = (ss + se) // 2
index_left, index_right = si * 2 + 1, si * 2 + 2
self.construct_segment_tree_util(
index_left, ss, mid, arr)
self.construct_segment_tree_util(
index_right, mid+1, se, arr)
if (arr[self.segment_tree[index_left]] <
arr[self.segment_tree[index_right]]):
self.segment_tree[si] = self.segment_tree[index_left]
else:
self.segment_tree[si] = self.segment_tree[index_right]
# Function to construct segment tree from given
# array. This function allocates memory for segment
# tree and calls construct_segment_tree_util()
# to fill the allocated memory
def construct_segment_tree(self, arr: List, n: int):
# Height of segment tree
x = floor(log2(n) + 1)
# Maximum size of segment tree
max_size = 2 * (1 << x) - 1 # 2*pow(2,x) -1
self.segment_tree = [0] * max_size
# Fill the allocated memory st
self.construct_segment_tree_util(
0, 0, n - 1, arr)
# Recursive version of the Euler tour of T
def euler_tour(self, node: Node, lev: int):
# If the passed node exists
if node is not None:
self.euler[self.fill] = node.val
self.level[self.fill] = lev
self.fill += 1
# If unvisited, mark first occurrence
if self.f_occur[node.val] == -1:
self.f_occur[node.val] = self.fill - 1
# Tour left subtree if exists and remark
# euler and level arrays for parent on
# return
if node.left is not None:
self.euler_tour(node.left, lev + 1)
self.euler[self.fill] = node.val
self.level[self.fill] = lev
self.fill += 1
# Tour right subtree if exists and
# remark euler and level arrays for
# parent on return
if node.right is not None:
self.euler_tour(node.right, lev + 1)
self.euler[self.fill] = node.val
self.level[self.fill] = lev
self.fill += 1
# Returns LCA of nodes n1, n2 (assuming they are
# present in the tree)
def find_lca(self, u: int, v: int):
# Start euler tour with root node on level 0
self.euler_tour(self.root, 0)
# Construct segment tree on level array
self.construct_segment_tree(self.level,
2 * self.val_max - 1)
# For rmq to work, u must be smaller than v
if self.f_occur[u] > self.f_occur[v]:
u, v = v, u
# Start and end of query range
qs = self.f_occur[u]
qe = self.f_occur[v]
# Query for index of lca in tour
index = self.rmq(2 * self.val_max - 1, qs, qe)
# Return lca node
return self.euler[index]
# Driver code
if __name__ == "__main__":
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.right.left = Node(8)
root.left.right.right = Node(9)
tree = BinaryTree(root)
u, v = 4, 9
print('The lca of node {} and {} is node {}'.format(
u, v, tree.find_lca(u, v)))
# This code is contributed by Rajat Srivastava
C#
// C# program to find LCA of u and
// v by reducing problem to RMQ
using System;
// A binary tree node
class Node
{
public Node left, right;
public int data;
public Node(int item)
{
data = item;
left = right = null;
}
}
class St_class
{
public int st;
public int []stt = new int[10000];
}
public class BinaryTree
{
Node root;
static int v = 9; // v is the highest value of node in our tree
int []euler = new int[2 * v - 1]; // for euler tour sequence
int []level = new int[2 * v - 1]; // level of nodes in tour sequence
int []f_occur = new int[2 * v - 1]; // to store 1st occurrence of nodes
int fill; // variable to fill euler and level arrays
St_class sc = new St_class();
// log base 2 of x
int Log2(int x)
{
int ans = 0;
int y = x >>= 1;
while (y-- != 0)
ans++;
return ans;
}
int swap(int a, int b)
{
return a;
}
/* A recursive function to get
the minimum value in a given range
of array indexes. The following
are parameters for this function.
st --> Pointer to segment tree
index --> Index of current node
in the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending
indexes of the segment represented
by current node, i.e., st[index]
qs & qe --> Starting and ending
indexes of query range */
int RMQUtil(int index, int ss, int se,
int qs, int qe, St_class st)
{
// If segment of this node is a part
// of given range, then return
// the min of the segment
if (qs <= ss && qe >= se)
return st.stt[index];
// If segment of this node is
// outside the given range
else if (se < qs || ss > qe)
return -1;
// If a part of this segment
// overlaps with the given range
int mid = (ss + se) / 2;
int q1 = RMQUtil(2 * index + 1,
ss, mid, qs, qe, st);
int q2 = RMQUtil(2 * index + 2,
mid + 1, se, qs, qe, st);
if (q1 == -1)
return q2;
else if (q2 == -1)
return q1;
return (level[q1] < level[q2]) ? q1 : q2;
}
// Return minimum of elements in
// range from index qs (query start) to
// qe (query end). It mainly uses RMQUtil()
int RMQ(St_class st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe)
{
Console.WriteLine("Invalid input");
return -1;
}
return RMQUtil(0, 0, n - 1, qs, qe, st);
}
// A recursive function that constructs
// Segment Tree for array[ss..se].
// si is index of current node in segment tree st
void constructSTUtil(int si, int ss, int se,
int []arr, St_class st)
{
// If there is one element in array,
// store it in current node of
// segment tree and return
if (ss == se)
st.stt[si] = ss;
else
{
// If there are more than one elements,
// then recur for left and right subtrees
// and store the minimum of two values in this node
int mid = (ss + se) / 2;
constructSTUtil(si * 2 + 1, ss, mid, arr, st);
constructSTUtil(si * 2 + 2, mid + 1, se, arr, st);
if (arr[st.stt[2 * si + 1]] < arr[st.stt[2 * si + 2]])
st.stt[si] = st.stt[2 * si + 1];
else
st.stt[si] = st.stt[2 * si + 2];
}
}
/* Function to construct segment tree
from given array. This function
allocates memory for segment tree
and calls constructSTUtil() to
fill the allocated memory */
int constructST(int []arr, int n)
{
// Allocate memory for segment tree
// Height of segment tree
int x = Log2(n) + 1;
// Maximum size of segment tree
int max_size = 2 * (1 << x) - 1; // 2*pow(2,x) -1
sc.stt = new int[max_size];
// Fill the allocated memory st
constructSTUtil(0, 0, n - 1, arr, sc);
// Return the constructed segment tree
return sc.st;
}
// Recursive version of the Euler tour of T
void eulerTour(Node node, int l)
{
/* if the passed node exists */
if (node != null)
{
euler[fill] = node.data; // insert in euler array
level[fill] = l; // insert l in level array
fill++; // increment index
/* if unvisited, mark first occurrence */
if (f_occur[node.data] == -1)
f_occur[node.data] = fill - 1;
/* tour left subtree if exists,
and remark euler and level
arrays for parent on return */
if (node.left != null)
{
eulerTour(node.left, l + 1);
euler[fill] = node.data;
level[fill] = l;
fill++;
}
/* tour right subtree if exists, and remark euler
and level arrays for parent on return */
if (node.right != null)
{
eulerTour(node.right, l + 1);
euler[fill] = node.data;
level[fill] = l;
fill++;
}
}
}
// returns LCA of node n1 and n2
// assuming they are present in tree
int findLCA(Node node, int u, int v)
{
/* Mark all nodes unvisited. Note
that the size of firstOccurrence
is 1 as node values which
vary from 1 to 9 are used as indexes */
//Arrays.fill(f_occur, -1);
for(int i = 0; i < f_occur.Length; i++)
f_occur[i] = -1;
/* To start filling euler and
level arrays from index 0 */
fill = 0;
/* Start Euler tour with
root node on level 0 */
eulerTour(root, 0);
/* construct segment tree on level array */
sc.st = constructST(level, 2 * v - 1);
/* If v before u in Euler tour.
For RMQ to work, first parameter
'u' must be smaller than
second 'v' */
if (f_occur[u] > f_occur[v])
u = swap(u, u = v);
// Starting and ending indexes of query range
int qs = f_occur[u];
int qe = f_occur[v];
// query for index of LCA in tour
int index = RMQ(sc, 2 * v - 1, qs, qe);
/* return LCA node */
return euler[index];
}
// Driver program to test above functions
public static void Main(String []args)
{
BinaryTree tree = new BinaryTree();
// Let us create the Binary Tree
// as shown in the diagram.
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.left.right.left = new Node(8);
tree.root.left.right.right = new Node(9);
int u = 4, v = 9;
Console.WriteLine("The LCA of node " + u + " and " + v + " is "
+ tree.findLCA(tree.root, u, v));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find LCA of u and v
// by reducing problem to RMQ
// A binary tree node
class Node
{
constructor(item)
{
this.data=item;
this.left = this.right = null;
}
}
class St_class
{
st;
stt=new Array(10000);
}
let root;
// v is the highest value of node in our tree
let v = 9;
// for euler tour sequence
let euler = new Array(2 * v - 1);
// level of nodes in tour sequence
let level = new Array(2 * v - 1);
// to store 1st occurrence of nodes
let f_occur = new Array(2 * v - 1);
let fill; // variable to fill euler and level arrays
let sc = new St_class();
// log base 2 of x
function Log2(x)
{
let ans = 0;
let y = x >>= 1;
while (y-- != 0)
ans++;
return ans;
}
function swap(a,b)
{
return a;
}
/* A recursive function to get the
minimum value in a given range
of array indexes. The following
are parameters for this function.
st --> Pointer to segment tree
index --> Index of current node in
the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending indexes
of the segment represented
by current node, i.e., st[index]
qs & qe --> Starting and ending indexes of query range */
function RMQUtil(index,ss,se,qs,qe,st)
{
// If segment of this node is a part
// of given range, then return
// the min of the segment
if (qs <= ss && qe >= se)
return st.stt[index];
// If segment of this node is
// outside the given range
else if (se < qs || ss > qe)
return -1;
// If a part of this segment overlaps
// with the given range
let mid = Math.floor((ss + se) / 2);
let q1 = RMQUtil(2 * index + 1, ss, mid, qs, qe, st);
let q2 = RMQUtil(2 * index + 2, mid + 1, se, qs, qe, st);
if (q1 == -1)
return q2;
else if (q2 == -1)
return q1;
return (level[q1] < level[q2]) ? q1 : q2;
}
// Return minimum of elements in range
// from index qs (query start) to
// qe (query end). It mainly uses RMQUtil()
function RMQ(st,n,qs,qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe)
{
document.write("Invalid input");
return -1;
}
return RMQUtil(0, 0, n - 1, qs, qe, st);
}
// A recursive function that constructs
// Segment Tree for array[ss..se].
// si is index of current node in segment tree st
function constructSTUtil(si,ss,se,arr,st)
{
// If there is one element in array,
// store it in current node of
// segment tree and return
if (ss == se)
st.stt[si] = ss;
else
{
// If there are more than one elements,
// then recur for left and
// right subtrees and store the minimum
// of two values in this node
let mid = Math.floor((ss + se) / 2);
constructSTUtil(si * 2 + 1, ss, mid, arr, st);
constructSTUtil(si * 2 + 2, mid + 1, se, arr, st);
if (arr[st.stt[2 * si + 1]] < arr[st.stt[2 * si + 2]])
st.stt[si] = st.stt[2 * si + 1];
else
st.stt[si] = st.stt[2 * si + 2];
}
}
/* Function to construct segment tree
from given array. This function
allocates memory for segment tree and
calls constructSTUtil() to
fill the allocated memory */
function constructST(arr,n)
{
// Allocate memory for segment tree
// Height of segment tree
let x = Log2(n) + 1;
// Maximum size of segment tree
let max_size = 2 * (1 << x) - 1; // 2*pow(2,x) -1
sc.stt = new Array(max_size);
// Fill the allocated memory st
constructSTUtil(0, 0, n - 1, arr, sc);
// Return the constructed segment tree
return sc.st;
}
// Recursive version of the Euler tour of T
function eulerTour(node,l)
{
/* if the passed node exists */
if (node != null)
{
euler[fill] = node.data; // insert in euler array
level[fill] = l; // insert l in level array
fill++; // increment index
/* if unvisited, mark first occurrence */
if (f_occur[node.data] == -1)
f_occur[node.data] = fill - 1;
/* tour left subtree if exists, and remark euler
and level arrays for parent on return */
if (node.left != null)
{
eulerTour(node.left, l + 1);
euler[fill] = node.data;
level[fill] = l;
fill++;
}
/* tour right subtree if exists, and remark euler
and level arrays for parent on return */
if (node.right != null)
{
eulerTour(node.right, l + 1);
euler[fill] = node.data;
level[fill] = l;
fill++;
}
}
}
// returns LCA of node n1 and n2
// assuming they are present in tree
function findLCA(node,u,v)
{
/* Mark all nodes unvisited. Note that the size of
firstOccurrence is 1 as node values which vary from
1 to 9 are used as indexes */
for(let i=0;i<f_occur.length;i++)
{
f_occur[i]=-1;
}
/* To start filling euler and
level arrays from index 0 */
fill = 0;
/* Start Euler tour with root node on level 0 */
eulerTour(root, 0);
/* construct segment tree on level array */
sc.st = constructST(level, 2 * v - 1);
/* If v before u in Euler tour. For RMQ to work, first
parameter 'u' must be smaller than second 'v' */
if (f_occur[u] > f_occur[v])
u = swap(u, u = v);
// Starting and ending indexes of query range
let qs = f_occur[u];
let qe = f_occur[v];
// query for index of LCA in tour
let index = RMQ(sc, 2 * v - 1, qs, qe);
/* return LCA node */
return euler[index];
}
// Driver program to test above functions
// Let us create the Binary Tree as shown in the diagram.
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.right.left = new Node(8);
root.left.right.right = new Node(9);
u = 4, v = 9;
document.write("The LCA of node " + u +
" and node " + v + " is node "
+ findLCA(root, u, v));
// This code is contributed by rag2127
</script>
Producción
The LCA of node 4 and node 9 is node 2.
Nota:
- Suponemos que los Nodes consultados están presentes en el árbol.
- También asumimos que si hay V Nodes en el árbol, entonces las claves (o datos) de estos Nodes están en el rango de 1 a V.
Complejidad del tiempo:
- Tour de Euler: El número de Nodes es V. Para un árbol, E = V-1. Euler tour (DFS) tomará O(V+E) que es O(2*V) que se puede escribir como O(V).
- Construcción del árbol de segmentos: O(n) donde n = V + E = 2*V – 1.
- Intervalo Consulta mínima: O(log(n))
En general, este método requiere un tiempo O(n) para el preprocesamiento, pero requiere un tiempo O(log n) para la consulta. Por lo tanto, puede ser útil cuando tenemos un solo árbol en el que queremos realizar una gran cantidad de consultas LCA (Tenga en cuenta que LCA es útil para encontrar la ruta más corta entre dos Nodes de un árbol binario)
Espacio Auxiliar:
- Array de recorrido de Euler: O(n) donde n = 2*V – 1
- Array de niveles de Node: O(n)
- Array de primeras ocurrencias: O(V)
- Árbol de segmentos: O(n)
Total: O(n)
Otra observación es que los elementos adyacentes en la array de nivel difieren en 1. Esto se puede usar para convertir un problema RMQ en un problema LCA.
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