Hola.
En un AVL las operaciones referidas son O(lo n) peor caso. En un ABB lo son en el caso promedio (peor caso O(n)).
En listas no ordenadas la inserción es O(1) pero las selectoras son O(n). Si la lista está ordenada las selectoras son O(1) pero la inserción es O(n).
En cualquier caso se puede llevar un puntero al de orden prioritario pero esto no permite borrar en O(1).
Saludos Carlos