Concatenar/Fusionar / Unir dos árboles AVL

Suponiendo que puede destruir los árboles de entrada:

1. elimine el elemento más a la derecha del árbol izquierdo, y utilícelo 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. determine y establezca 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 obtener el factor de equilibrio de nuevo 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 muy probable que sea más rápido:

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

4. Reemplace 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-balanceado, y su subárbol 1 más alto que r.

5. Incremente el saldo de su padre en consecuencia. O(1)

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