algorithm - propiedades - construir arbol binario a partir de su recorrido

Determine si dos árboles binarios son iguales

Question

¿Cuál sería el algoritmo eficiente para encontrar si dos árboles binarios dados son iguales en estructura y contenido?

Answer 1

Como es un hecho comprobado, es posible recrear un árbol binario siempre que tengamos lo siguiente:

1. La secuencia de nodos que se encuentran en un recorrido en orden.
2. La secuencia de nodos que se encuentran en un recorrido previo al pedido o posterior al pedido

Si dos árboles binarios tienen la misma secuencia en orden y [pre-orden O post-orden], entonces deberían ser iguales estructuralmente y en términos de valores.

Cada recorrido es una operación O (n). Los recorridos se realizan 4 veces en total y se comparan los resultados del mismo tipo de recorrido. O (n) * 4 + 2 => O (n) Por lo tanto, el orden total de complejidad del tiempo sería O (n)

Answer 2

Es un problema menor, pero adaptaría la solución anterior de la siguiente manera ...

eq(t1, t2) =
  t1.data=t2.data && eq(t1.left, t2.left) && eq(t1.right, t2.right)

La razón es que es probable que los desajustes sean comunes, y es mejor detectar (y dejar de comparar) temprano, antes de seguir recurriendo. Por supuesto, estoy asumiendo un operador de cortocircuito && aquí.

También señalaré que esto es pasar por alto algunos problemas relacionados con el manejo correcto de árboles estructuralmente diferentes y con la finalización de la recursión. Básicamente, es necesario que haya algunos controles nulos para t1.left, etc. Si un árbol tiene un .left nulo pero el otro no, ha encontrado una diferencia estructural. Si ambos tienen un nulo .left, no hay diferencia, pero usted ha alcanzado una hoja, no se preocupe más. Solo si ambos valores .left no son nulos, usted solicita asistencia para verificar el subárbol. Lo mismo se aplica, por supuesto, para .right.

Podría incluir verificaciones para, por ejemplo, (t1.left == t2.left), pero esto solo tiene sentido si los subárboles se pueden compartir físicamente (los mismos nodos de estructura de datos) para los dos árboles. Esta verificación sería otra forma de evitar recursiones donde no sea necesario: si t1.left y t2.left son el mismo nodo físico, ya sabe que esos subárboles completos son idénticos.

La implementación de AC podría ser ...

bool tree_compare (const node* t1, const node* t2)
{
  // Same node check - also handles both NULL case
  if (t1 == t2)  return true;

  // Gone past leaf on one side check
  if ((t1 == NULL) || (t2 == NULL))  return false;

  // Do data checks and recursion of tree
  return ((t1->data == t2->data) && tree_compare (t1->left,  t2->left )
                                 && tree_compare (t1->right, t2->right));
}

EDITAR En respuesta a un comentario ...

El tiempo de ejecución para una comparación de árbol completo utilizando esto se indica de forma más simple como O (n) donde n es un poco el tamaño de un árbol. Si está dispuesto a aceptar un límite más complejo, puede obtener uno más pequeño como O (mínimo (n1, n2)) donde n1 y n2 son los tamaños de los árboles.

La explicación es básicamente que la llamada recursiva solo se realiza (a lo sumo) una vez para cada nodo en el árbol izquierdo, y solo se realiza (como máximo) una vez para cada nodo en el árbol derecho. Como la función en sí misma (excluyendo las recursiones) solo especifica a lo sumo una cantidad constante de trabajo (no hay bucles), el trabajo que incluye todas las llamadas recursivas solo puede ser tan grande como el tamaño del árbol más pequeño que la constante.

Podría analizar más a fondo para obtener un límite más complejo pero más pequeño utilizando la idea de la intersección de los árboles, pero la O grande solo proporciona un límite superior, no necesariamente el límite superior más bajo posible. Probablemente no valga la pena realizar ese análisis, a menos que esté intentando construir un algoritmo / estructura de datos más grande con esto como un componente, y como resultado sabe que alguna propiedad siempre se aplicará a esos árboles, lo que puede permitirle un límite más estricto para el algoritmo más grande.

Una forma de formar un límite más tenso es considerar los conjuntos de rutas a los nodos en ambos árboles. Cada paso es una L (subárbol izquierdo) o una R (subárbol derecho). Así que la raíz se especifica con una ruta vacía. El hijo derecho del hijo izquierdo de la raíz es "LR". Defina una función "rutas (T)" (matemáticamente, que no forma parte del programa) para representar el conjunto de rutas válidas en un árbol, una ruta para cada nodo.

Así que podríamos tener ...

paths(t1) = { "", "L", "LR", "R", "RL" }
paths(t2) = { "", "L", "LL", "R", "RR" }

Las mismas especificaciones de ruta se aplican a ambos árboles. Y cada recursión siempre sigue el mismo enlace de izquierda / derecha para ambos árboles. Por lo tanto, la recursión visita las rutas en la sección de estos conjuntos, y el límite más estrecho que podemos especificar es la cardinalidad de esa intersección (aún con el límite constante en el trabajo por llamada recursiva).

Para las estructuras de árbol de arriba, hacemos recursiones para los siguientes caminos ...

paths(t1) intersection paths(t2) = { "", "L", "R" }

Por lo tanto, nuestro trabajo en este caso está limitado a un máximo de tres veces el costo máximo del trabajo no recursivo en la función tree_compare.

Esto suele ser una cantidad innecesaria de detalles, pero claramente la intersección de los conjuntos de rutas es a lo sumo tan grande como la cantidad de nodos en el árbol original más pequeño. Y si la n en O (n) se refiere al número de nodos en un árbol original o a la suma de los nodos en ambos, esto claramente no es más pequeño que el mínimo o nuestra intersección. Por lo tanto, O (n) no es un límite tan estrecho, pero sigue siendo un límite superior válido, incluso si somos un poco vagos de qué tamaño estamos hablando.

Answer 3

Lo escribiría de la siguiente manera. El siguiente código funcionará en el idioma más funcional, e incluso en python si sus tipos de datos son hashable (por ejemplo, no diccionarios o listas):

• igualdad topológica (igual en estructura, es decir, Tree(1,Tree(2,3))==Tree(Tree(2,3),1) ):

  tree1==tree2 significa set(tree1.children)==set(tree2.children)

• igualdad ordenada

  tree1==tree2 significa tree1.children==tree2.children

(Tree.children es una lista ordenada de niños)

No es necesario manejar los casos base (hojas), porque la igualdad ya se ha definido para ellos.

Answer 4

Módulo de desbordamiento de pila, algo así como

eq(t1, t2) =
    eq(t1.left, t2.left) && t1.data=t2.data && eq(t1.right, t2.right)

(Esto generaliza a un predicado de igualdad para todos los tipos de datos algebraicos con estructura de árbol; para cualquier parte de datos estructurados, verifique si cada una de sus subpartes es igual a cada una de las subpartes del otro).

Answer 5

También podemos hacer cualquiera de los dos recorridos (pre-orden, post-orden o en orden) y luego comparar los resultados de ambos árboles. Si son iguales, podemos estar seguros de su equivalencia.

Answer 6

Un término más general para lo que probablemente está tratando de lograr es el gráfico isomorfismo . Hay algunos algoritmos para hacer esto en esa página.