Concatenando / Fusión / unir dos árboles AVL

Question

Supongamos que tengo dos árboles AVL y que cada elemento del primer árbol es más pequeño que cualquier elemento del segundo árbol. ¿Cuál es la forma más eficiente para concatenar en un solo árbol AVL? He buscado por todas partes pero no he encontrado nada útil.

Answer 1

Si se asume que puede destruir los árboles de entrada:

1. retirar el elemento más a la derecha para el árbol de la izquierda, y lo utilizan para construir un nuevo nodo raíz, cuyo hijo izquierdo es el árbol de la izquierda, y cuyo hijo derecho es el árbol derecho: O (log n)
2. determinar y establecer factor de equilibrio de ese nodo: O (log n). En violación (temporal) de la invariante, el factor de equilibrio puede estar fuera del rango {-1, 0, 1}
3. gire para obtener el factor de equilibrio de nuevo en rango: O (log n) rotaciones: O (log n)

Por lo tanto, toda la operación se puede realizar en O (log n).

Editar: Pensándolo bien, es más fácil razonar acerca de las rotaciones en el siguiente algoritmo. También es muy probable que más rápido:

1. Determinar la altura de ambos árboles:. O (log n)
   Suponiendo que el árbol de la derecha es más alto (el otro caso es simétrica):
2. retirar el elemento más a la derecha del árbol left (giratorio y el ajuste de su altura computada si es necesario). Deje n sea ese elemento. O (log n)
3. En el árbol de la derecha, navegar hacia la izquierda hasta llegar a un nodo cuyo subárbol es a lo sumo un 1 más alto que left. Deje r sea ese nodo. O (log n)

4. reemplazar ese nodo con un nuevo nodo con el valor n, y subárboles left y r. O (1)
   Por construcción, el nuevo nodo es AVL-equilibrado, y su subárbol 1 más alto que r.

5. incremento de balance de su matriz en consecuencia. O (1)

6. y reequilibrar como lo haría después de la inserción. O (log n)

Answer 2

Una solución de ultra sencillo (que funciona sin ninguna hipótesis en las relaciones entre los árboles) es la siguiente:

1. Haga una especie de combinación de los dos árboles en un array resultante (concurrentemente iterar ambos árboles).
2. Construir un árbol AVL de la matriz - tomar el elemento medio a ser la raíz, y aplicar de forma recursiva a la izquierda y la mitad derecha
.

Ambos pasos son O (n). El principal problema con él es que se necesita O (n) el espacio extra.

Answer 3

La mejor solución que he leído a este problema se puede encontrar aquí . Está muy cerca de respuesta Meriton 's si corrige este problema:

En el tercer paso del algoritmo Se desplaza a la izquierda hasta llegar a la sub nodo cuyo árbol tiene la misma altura que el árbol de la izquierda . Esto no siempre es posible, (ver imagen contraejemplo). La forma correcta de hacer este paso es de dos hallazgo de un subárbol con h altura o h+1 donde h es la altura del árbol de la izquierda

Answer 4

Sospecho que vas a tener que caminar un árbol (esperemos que el más pequeño) e individualmente añadir cada uno de los elementos que hay al otro árbol. El inserto AVL / eliminar operaciones no están diseñados para manejar la adición de un subárbol completo a la vez.