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 cuanto a estructura y contenido?

Answer 1

es una cuestión de menor importancia, pero me gustaría adaptar la solución antes 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 m es probable que los ismatches sean comunes, y es mejor detectar (y dejar de comparar) temprano, antes de volver a recurrir. Por supuesto, estoy asumiendo un operador de cortocircuito & & aquí.

También señalaré que esto es pasar por alto algunos problemas con el manejo correcto de árboles estructuralmente diferentes, y con terminar la recursión. Básicamente, debe haber algunas comprobaciones nulas para t1.left, etc. Si un árbol tiene un nulo nulo, pero el otro no, ha encontrado una diferencia estructural. Si ambos tienen nulo .left, no hay diferencia, pero has alcanzado una hoja, no recurres más. Solo si ambos valores .left son no nulos, recurse para verificar el subárbol. Lo mismo aplica, por supuesto, para .right.

Puede incluir cheques de, 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 comprobación sería otra forma de evitar la recurrencia cuando 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.

aplicación de CA 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 completa del árbol usando así se indique lo más simplemente como O (n) donde n es un poco del 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 (como máximo) 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 una cantidad constante de trabajo (no hay bucles), el trabajo que incluye todas las llamadas recursivas solo puede ser tanto como el tamaño del árbol más pequeño multiplicado por esa constante.

Puede analizar más a fondo para obtener un límite más complejo pero más pequeño usando la idea de la intersección de los árboles, pero la gran O solo da un límite superior, no necesariamente el límite superior más bajo posible. Probablemente no valga la pena hacer ese análisis a menos que intente construir una estructura más grande de algoritmo/datos con esto como un componente, y como resultado, usted sabe que alguna propiedad siempre se aplicará a esos árboles que pueden permitirle un límite más estricto para el algoritmo más grande.

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

Así podríamos tener ...

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

Las mismas especificaciones de ruta aplican tanto a los árboles. Y cada recursión siempre sigue el mismo enlace izquierda/derecha para ambos árboles. Entonces la recursión visita los caminos en la sección de estos conjuntos, y el límite más estricto que podemos especificar al usar esto es la cardinalidad de esa intersección (aún con la constante enlazada al trabajo por llamada recursiva).

Para las estructuras de árbol encima, hacemos recurrencias de las siguientes rutas ...

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

Así que nuestro trabajo en este caso está limitada a un máximo de tres veces el coste máximo de trabajo no recursivo en el función tree_compare.

Normalmente, esta es una cantidad innecesaria de detalles, pero es evidente que la intersección de los conjuntos de rutas es como máximo igual a la cantidad de nodos en el árbol original más pequeño. Y si el 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 estricto, pero sigue siendo un límite superior válido, incluso si somos un poco vagos de qué tamaño estamos hablando.

Answer 2

Un término más general para lo que probablemente esté intentando lograr es graph isomorphism. Hay algunos algoritmos para hacer esto en esa página.

Answer 3

Modulo 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 se generaliza a un predicado de igualdad para todos los tipos de datos algebraicos con estructura de árbol - para cualquier pedazo de datos estructurados, comprobar si cada uno de sus sub-partes son iguales a cada uno de los sub-partes de la otra.)

Answer 4

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

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

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

• ordenada la igualdad:

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

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

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

Answer 5

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

Answer 6

Puesto que es un hecho comprobado que - es posible recrear un árbol binario, siempre y cuando tenemos el siguiente:

1. La secuencia de nodos que se encuentran en una Transversal Dentro de la Orden.
2. La secuencia de nodos que se encuentran en un pre-pedido o Post-orden transversal

Si dos árboles binarios tienen el mismo en orden y [pre-pedido o post-fin] secuencia, entonces debe ser igual tanto estructuralmente como 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 la complejidad del tiempo sería O (n)