Tengo dos árboles binarios y quiero unirlos. Mi primera pregunta es si podemos fusionar dos árboles binarios y, en caso afirmativo, qué tan eficientemente puedo realizar las operaciones de fusión y cuáles son las diversas formas en que puedo realizar las operaciones de fusión. ..?Cómo puedo fusionar dos árboles binarios
Sin considerar la eficiencia esta respuesta puede funcionar Algorithm of combining two binary trees?. Si está ordenado o equilibrado, debate sobre eficiencia en How to merge two BST's efficiently? y Concatenating/Merging/Joining two AVL trees
1) Aplanar los árboles en listas ordenadas.
2) Combinar las listas de lo que tienes en 1)
3) construir el árbol de lo que tienes en 2)
wahts la complejidad? –
Puede aplanar los árboles en listas en el tiempo O (n) usando una caminata estándar en orden. La fusión de dos listas ordenadas también se puede hacer en el tiempo O (n). Una vez que haya combinado las listas, puede construir el BST en el tiempo O (n) construyendo recursivamente árboles de las mitades izquierda y derecha, y luego pegándolos. La complejidad general es, por lo tanto, O (n). – templatetypedef
@templatetypedef: Gracias por la respuesta. Sí, la complejidad es O (n). – hari
Crea un nuevo nodo y apunta una cola a la cabeza de uno de los árboles y señala la otra cola a la cabeza del otro árbol. Quizás necesite aclarar su pregunta para ser más específico. ¿Qué relaciones estás tratando de preservar?
Un árbol también es un gráfico, de modo que muestre los pares de vértices de borde (u, v) para cada árbol, y luego unir estos conjuntos de bordes y generar el gráfico resultante.
El problema surge con la forma de mapear vértices en un árbol a vértices en el otro (por ejemplo, tenemos un par de aristas (5,9) en el árbol 1 y un par de aristas (5,6) en el arbol 2, estos 5s corresponden al mismo vértice?).
Comando con una numeración de vértices (tal vez que asigna números a cada vértice en un árbol binario incompleto, como si fuera un árbol binario completo, es decir asigna los vértices en cualquier árbol binario parcial a las ranuras de un Árbol binario completo hipotético del cual ese árbol es un subárbol), que de alguna manera proporciona una equivalencia deseable es algo que funciona.
La fusión de árboles binarios es trivial, simplemente vincule la raíz de uno como hijo de uno de los nodos de hoja del otro. ¿Tenía alguna otra estructura que desea conservar, como ordenarla o equilibrarla? – JGWeissman
, comencemos con un árbol desordenado no ordenado simple. Dijiste que es trivial, ¿puedes mostrarme cómo se hace? –