Buenas, no se si alguien va a ver este mensaje. Pero me quedo una duda de como borrar en un AVl manteniendo ambas, las propiedad de orden y la propiedad de estructura. En su momento hicimos en clase la inserción, y quedo pendiente el borrado (también quedo pendiente el buscar pero como esta operación no modifica al árbol creo que es como una búsqueda en un ABB normal)
La cuestión es que no me quedaba claro en que parte chequear y posiblemente corregir los desbalances del árbol, al final opte por hacerlo luego de cada llamado recursivo a la función, incluso después de llamarla para hacer la eliminación del nodo mínimo del subárbol derecho (si es que cae en ese caso).
El código en si es bastante largo, pero lo dejo por si alguien lo ve y le encuentra algo o sabe como hacerlo mas escueto.
Saludos.