Since MIN / MAX are O(1) operations there is a trivial optimization where you can add elements that are greater or smaller of any other element in O(1), and in

Since MIN / MAX are O(1) operations there is a trivial optimization where you can add elements that are greater or smaller of any other element in O(1), and in many applications this is happens with a great probability. Of course you can do this for AVL trees as well, but in order to do so there is to take additional information in the structure.