En publicaciones anteriores, hemos discutido cómo calcular el ancestro común más bajo (LCA) para un árbol binario y un árbol de búsqueda binaria ( this , this y this ). Ahora veamos un método que puede calcular LCA para cualquier árbol (no solo para árboles binarios). Utilizamos la programación dinámica con el enfoque de array … Continue reading «LCA para árboles generales o n-arios (enfoque de array dispersa DP)»
Dado un árbol binario, la tarea es encontrar la distancia entre dos claves en un árbol binario, no se dan punteros principales. La distancia entre dos Nodes es el número mínimo de aristas a recorrer para llegar a un Node desde otro. Ya hemos discutido un método que usa el árbol de segmentos para reducir … Continue reading «Consultas para encontrar la distancia entre dos Nodes de un árbol binario – Part 1»
Requisito previo: Introducción y DFS La tarea es encontrar LCA de dos Nodes dados en un árbol (no necesariamente un árbol binario). En publicaciones anteriores, hemos visto cómo calcular LCA utilizando el enfoque Sparse Matrix DP . En esta publicación, veremos una optimización realizada en el método Naive mediante la técnica de descomposición sqrt que … Continue reading «Descomposición Sqrt (o Raíz Cuadrada) | Conjunto 2 (LCA de Tree in O(sqrt(height)) tiempo)»
Dado un árbol de búsqueda binario y dos claves en él. Encuentre la distancia entre dos Nodes con dos claves dadas. Se puede suponer que ambas claves existen en BST. Ejemplos: Input: Root of above tree a = 3, b = 9 Output: 4 Distance between 3 and 9 in above BST is 4. Input: … Continue reading «Distancia más corta entre dos Nodes en BST – Part 1»
Dados los valores de dos valores n1 y n2 en un árbol de búsqueda binaria, encuentre el antepasado común más bajo (LCA). Puede suponer que ambos valores existen en el árbol. Ejemplos: C++ // A recursive CPP program to find // LCA of two nodes n1 and n2. #include <bits/stdc++.h> using namespace std; … Continue reading «Ancestro común más bajo en un árbol de búsqueda binario.»
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 … Continue reading «Encuentre LCA en árbol binario usando RMQ»
Dado un árbol binario que consiste en N Nodes que tienen valores distintos del rango [1, N] , la tarea es encontrar el ancestro común más bajo de las hojas más profundas del árbol binario. Ejemplos: Aporte: Salida: 1 Explicación: Los Nodes de hoja más profundos del árbol son {8, 9, 10}. El ancestro común … Continue reading «Ancestro común más bajo de las hojas más profundas de un árbol binario»
Requisito previo: conceptos básicos de LCA , unión de conjuntos disjuntos por rango y compresión de ruta . Se nos da un árbol (se puede extender a un DAG) y tenemos muchas consultas de forma LCA (u, v), es decir, encontrar LCA de Nodes ‘u’ y ‘v’. Podemos realizar esas consultas en tiempo O(N + … Continue reading «Algoritmo de ancestros comunes más bajos fuera de línea de Tarjan»
La descomposición Heavy Light (HLD) es una de las técnicas más utilizadas en la programación competitiva . Problema de ejemplo: comprendamos la descomposición pesada-ligera (HLD) con la ayuda del siguiente ejemplo. Supongamos que tenemos un árbol desequilibrado (no necesariamente un árbol binario) de n Nodes , y tenemos que realizar operaciones en el árbol para … Continue reading «Descomposición ligera pesada | Serie 1 (Introducción)»
Dado un árbol con N Nodes y N – 1 aristas. Cada borde del árbol está etiquetado con una string de alfabetos ingleses en minúsculas. Se le dan Q consultas. En cada consulta, se le asignan dos Nodes x e y . Para la ruta entre x e y , la tarea es verificar si … Continue reading «Consultas para verificar si la ruta entre dos Nodes en un árbol es un palíndromo»