Supongamos que tengo dos árboles AVL y que sé sus tamaños respectivos. Sin embargo, no sé si hay nodos repetidos o cualquier otra información. ¿Cuál sería la forma más eficiente de fusionarlos en un nuevo árbol AVL? Los árboles originales pueden ser destruidos.Fusionando 2 árboles AVL DIFERENTES
T1 y T2 a listas ordenadas L1 y L2L1 y L2 en una lista ordenada LL en un árbol T nuevo.IIRC todas estas operaciones son O (N), por lo que la fusión completa también será O (N).
Si su representación de los árboles AVL permite iterar sobre ellos de manera eficiente (por ejemplo, usando contraindicaciones, continuaciones, evaluación diferida, etc.) también podrá hacerlo sin las listas intermedias.
Actualización: como su lenguaje de programación parece ser C/C++, podría abusar temporalmente de las estructuras de sus nodos AVL para ser nodos en una lista vinculada y luego reutilizarlos nuevamente para el árbol de salida.
Actualización 2: @hwlau: esta es O (N), He comprobado que el uso de mi propia aplicación AVL en Prolog disponible de avl.pl y este programa de prueba de avl_test.pl que comprueba el número de operaciones cuando la fusión de árboles AVL de tamaño 1, 2, 4, 8, 16, ...
Esta es la salida:
timing avl_merge, size: 128
% 1,790 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
timing avl_merge, size: 256
% 3,591 inferences, 0.010 CPU in 0.002 seconds (430% CPU, 359100 Lips)
timing avl_merge, size: 512
% 7,176 inferences, 0.030 CPU in 0.028 seconds (107% CPU, 239200 Lips)
...
timing avl_merge, size: 32000
% 451,839 inferences, 0.490 CPU in 0.499 seconds (98% CPU, 922120 Lips)
timing avl_merge, size: 64000
% 903,682 inferences, 0.900 CPU in 0.964 seconds (93% CPU, 1004091 Lips)
timing avl_merge, size: 128000
% 1,807,363 inferences, 2.420 CPU in 2.559 seconds (95% CPU, 746844 Lips)
es obvio que el número de inferencias/operaciones es proporcional al tamaño de los árboles fusionadas y por lo que la complejidad del algoritmo O (N).
No es el más eficiente, pero definitivamente es el más fácil de implementar. Puede simplemente agregar todos los nodos desde el segundo árbol al primero. No necesita eliminar los nodos del segundo árbol. Simplemente destruyes el segundo árbol y tienes el primer árbol como resultado. La complejidad de tiempo es O(N*log(N)).
Estrictamente, la complejidad de este método es O (M * log (N + M)). Este método puede ser apropiado cuando uno de los árboles es mucho más pequeño que el otro. – salva
posible duplicar http://stackoverflow.com/questions/2037212/concatenating-merging-joining-two-avl-trees –
Eso no es exactamente un duplicado. Las condiciones en su enlace son más restringidas: "cada elemento del primer árbol es más pequeño que cualquier elemento del segundo árbol" –
@bronzebeard: Las preguntas son diferentes. El señalado por usted tiene una condición que simplifica enormemente el problema y sus soluciones no son aplicables aquí. – salva