non-binary self balancing tree
You can use a binary prefix-trie (critbit-tree). It's not exactly selfbalancing, but it never requires rebalancing and imbalance is limited. For example, with 64bit keys, the maximum depth is strictly 64. This is not exactly the lowest possible height, but maybe that requirement can be relaxed because no rebalancing ever occurs?

You can find an (my) implementation here.