Van Emde Boas tree - all operations in O(log log n) time

The title is not a typo. Time is exponentially better than a self-balancing binary search tree. Assuming your problem can fit within the key constraints, and that your tree is sufficiently dense to make it practical. ;)