Concatenar/fusionar/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 de concatenarlos en un solo árbol AVL? He buscado en todas partes pero no he encontrado nada útil.

Answer 1

Asumiendo 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 el factor de equilibrio de ese nodo: O (log n). En la violación (temporal) del invariante, el factor de equilibrio puede estar fuera del rango {-1, 0, 1}
3. gire para volver a poner el factor de equilibrio en el 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 sobre las rotaciones en el siguiente algoritmo. También es bastante probable que sea más rápido:

1. Determine la altura de ambos árboles: O (log n).
   Suponiendo que el árbol derecho es más alto (el otro caso es simétrico):
2. elimina el elemento más a la derecha del árbol left (girando y ajustando su altura calculada si es necesario). Deje n ser ese elemento. O (log n)
3. En el árbol de la derecha, navegue hacia la izquierda hasta llegar a un nodo cuyo subárbol sea como máximo 1 1 más alto que left. Deje r ser ese nodo. O (log n)

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

5. incrementa el saldo de sus padres en consecuencia. O (1)

6. y vuelva a equilibrar como lo haría después de insertar. O (log n)

Answer 2

Sospecho que solo tendrá que caminar un árbol (con suerte, el más pequeño) y agregar individualmente cada uno de sus elementos al otro árbol. Las operaciones de inserción/eliminación de AVL no están diseñadas para manejar la adición de un subárbol completo a la vez.

Answer 3

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

1. hacer una especie de combinación de los dos árboles en un array resultante (concurrentemente iterar ambos árboles).
2. Construya un árbol AVL de la matriz: tome el elemento medio como raíz y aplique recursivamente a las mitades izquierda y derecha.

Ambos pasos son O (n). El principal problema es que toma O (n) espacio extra.

Answer 4

La mejor solución que leí para este problema se puede encontrar en here. Está muy cerca de respuesta meriton 's si corrige este problema:

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