Re: Segundo parcial 2019
Buenas! Sí, creo que es lo que trata de mencionar más abajo pero no está tan claro.
Una posible implementación del avl es con un puntero al mínimo, con lo cual podrías ver cuál es el mínimo en O(1), pero si lo borrás, tenés que encargarte del puntero izquierdo del padre, al cual no tenés acceso salvo en O(logn).
Y si uno intenta hacerse el inteligente poniendo un puntero al padre, también genera problemas.
Parece estar muy claro en la explicación por qué prioritario es O(1): porque se mantiene un puntero al nodo.
¿La falta de claridad es por qué eliminarPrioritario no es O(1)? Si es eso es porque al eliminar el prioritario hay que buscar el nuevo prioritario. Si bien mantener un puntero al padre puede ser útil para otras aplicaciones no lo es para esta, porque el nuevo prioritario puede estar en el subárbol derecho del que hasta ese momento era el prioritario.