Complejidad del tiempo: algoritmo para encontrar el ancestro común más bajo de todas las hojas más profundas

Question

Esta es la declaración de problemas que encontré hoy.

Dado un árbol binario, encuentra el ancestro común más bajo de todas las hojas más profundas.

Se me ocurrió un algoritmo correcto, pero me gustaría confirmar el tiempo de ejecución de este enfoque.

El algoritmo es el siguiente:

1. atravesar el árbol y encontrar el nivel más profundo del árbol, dmax .
2. atravesar el árbol y encontrar todas las hojas en profundidad dmax .
3. dado que lca (a, b, c) = lca (lca (a, b), c) , atravesar todos los nodos encontrados en el Paso 2 y calcular LCA.

La subrutina para lca (a, b) es simple. A partir de a , vaya hasta la raíz y almacene cada nodo visitado en un hashset. Luego, comenzando a b , sube hasta que encuentre un nodo que esté contenido en el hashset.

Sé que los dos primeros pasos del algoritmo son O (n) , donde n corresponde a la cantidad de nodos en el árbol. Sin embargo, no estoy seguro del último paso.

lca (a, b) subrutina tiene una complejidad lineal. Pero, ¿cuántos nodos, en el peor escenario, se puede encontrar en el paso 2?.

Intuitivamente, argumentaría que tiene que ser mucho menos que n nodos.

Answer 1

Como explicó @rick Decker, puede tener $ n / 2 $ hojas a la profundidad máxima en el caso. En este caso, el paso 3 es $ o (n \ log n) $ . esta publicación Muestra el peor de los casos. Considere un árbol $ t $ consiste en una cadena de $ n / 2 $ nodos donde restante $ n / 2 $ los nodos se adjuntan como un árbol equilibrado en la parte inferior de la cadena. Esto proporciona todas las profundidades de la hoja $ n / 2 + \ log_2 (n)=theta (n) $ con $ n / 4 $ hojas en profundidad $ \ theTa (n) $ Tenemos $ \ theTa (n ^ 2) $ tiempo de ejecución para el paso 3 en este caso. Esto es asintóticamente el peor de los casos, ya que tenemos $ n $ nodos en la profundidad máxima $ n $ .

Hay una mejor manera de hacer esto. Deje definir una función $ f $

$ f (v)=comienzan {casos} v & \ texto {if} \ quad \ texttt {altura} (v.left)=texttt {altura} (v.right) \\ f (v.left) & \ texto {if} \ quad \ texttt {altura} (v.left)> \ texttt {altura} (v.right) \\ f (v.right) & \ texto {if} \ quad \ texttt {altura} (v.left) <\ texttt {altura} (v.right) \ End {casos} $

Si las alturas de los niños de un nodo $ v $ son los mismos, entonces claramente $ v $ es el LCA de los nodos más profundos del subárbol enraizado en $ v $ . Si el subárate izquierdo es más alto, entonces queremos el LCA de los nodos más profundos del subárbol enraizado en $ v.left $ , ya que son más profundos que los nodos más profundos de El subárbol enraizado en $ v.right $ . La misma lógica sigue para $ v.right $ cuando es más alto.

Los valores para $ \ texttt {altura} $ y $ f (v) $ puede ser calculado en un recorrido posterior a $ t $ en tiempo lineal.

Llamar $ f (root) $ debe devolver el LCA de los nodos más profundos del árbol.

Answer 2

Bueno, no sé lo que pretende "mucho menos que", pero está claro que podría tener alrededor de $ n / 2 $ hojas a máxima profundidad: Tome un árbol binario completo, por ejemplo, con el nivel más bajo lleno.

Answer 3

Escribiría una función que para cada árbol calcula el ancestro común más bajo de todos los nodos más profundos, y la altura del árbol.Esto es bastante simple:

Si la raíz R no tiene rama izquierda o derecha, entonces la altura es 1 y el ancestro común es R. Si la raíz R tiene una rama izquierda o derecha, luego calcula la altura y el ancestro común más bajo de esa rama, yLa altura con la raíz R es una más alta, pero el ancestro común más bajo es el mismo.

Si hay una rama derecha izquierda y , luego calcule la altura y el ancestro común más bajo de ambas ramas.Si las alturas son diferentes, devolvemos (altura + 1) más el ancestro más bajo de esa rama.Si las alturas son las mismas, devolvemos (altura + 1) y r como el ancestro común más bajo.

Eso debería tomar pasos CN con una pequeña constante C si el número de nodos es N. y, como debemos visitar cada nodo N (al menos para saber que no tiene sucursales), esto no se puede mejorar.