Luego de tanto batallar hemos dado con el arreglo de esta obstáculo que muchos los usuarios de este sitio web presentan. Si tienes alguna información que aportar puedes aportar tu conocimiento.
Solución:
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 recurrir más. Por supuesto, estoy asumiendo un operador de cortocircuito && aquí.
También señalaré que esto está pasando por alto algunos problemas con el manejo correcto de árboles estructuralmente diferentes y con la finalización de la recursividad. Básicamente, tiene que haber algunos null comprueba t1.left etc. Si un árbol tiene un null .izquierda pero el otro no, ha encontrado una diferencia estructural. si ambos tienen null .left, no hay diferencia, pero ha llegado a una hoja; no recurra más. Solo si ambos valores de .left no sonnull ¿Recurres para verificar el subárbol? Lo mismo se aplica, por supuesto, para .right.
Podría incluir controles 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 la repetición donde no es necesaria: si t1.left y t2.left son el mismo nodo físico, ya sabe que todos esos subárboles 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)
EDITAR En respuesta a un comentario…
El tiempo de ejecución para una comparación de árbol completo usando esto se indica de manera más simple como O (n), donde n es algo así como 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 (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 como máximo 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.
Podría 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 O grande 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 esté tratando de construir una estructura de datos/algoritmo más grande con esto como componente, y como resultado sabe que alguna propiedad siempre se aplicará a esos árboles que pueden permitirle un límite más estrecho para el algoritmo más grande.
Una forma de formar un límite más estrecho es considerar los conjuntos de caminos a los nodos en ambos árboles. Cada paso es una L (subárbol izquierdo) o una R (subárbol derecho). Entonces, 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 “caminos (T)” (matemáticamente, no es parte del programa) para representar el conjunto de caminos válidos en un árbol: un camino 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 izquierdo/derecho para ambos árboles. Entonces, la recursividad visita los caminos en la intersección de estos conjuntos, y el límite más estrecho que podemos especificar usando esto es la cardinalidad de esa intersección (todavía 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 como máximo a tres veces el costo máximo del trabajo no recursivo en la función tree_compare.
Esto normalmente es una cantidad innecesaria de detalles, pero claramente la intersección de los conjuntos de caminos es como mucho tan grande como el número de nodos en el árbol original más pequeño. Y ya sea que n en O(n) se refiera al número de nodos en un árbol original oa la suma de los nodos en ambos, esto claramente no es menor 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.
Desbordamiento de pila de módulo, 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 pieza de datos estructurados, verifique si cada una de sus subpartes es igual a cada una de las otras subpartes).
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.
Sección de Reseñas y Valoraciones
Si crees que te ha resultado de ayuda este artículo, te agradeceríamos que lo compartas con más entusiastas de la programación y nos ayudes a extender nuestra información.