c++ - rotaciones - avl algoritmo

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 puedes destruir los árboles de entrada:

1. elimine el elemento situado más a la derecha para el árbol izquierdo, y úselo para construir un nuevo nodo raíz, cuyo hijo izquierdo es el árbol izquierdo 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 más rápido:

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

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

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

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

Answer 2

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

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

Answer 3

Sospecho que solo tendrás que caminar un árbol (con suerte, el más pequeño) e individualmente agregar 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 4

Una solución ultra simple (que funciona sin suposiciones en las relaciones entre los árboles) es esta:

1. Haga un tipo de combinación de ambos árboles en una matriz combinada (iterar simultáneamente ambos árboles).
2. Construya un árbol AVL desde la matriz: tome el elemento medio para que sea la 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.