The TreeMap documentation states that it is a red-black tree based implementation of the SortedMap interface. What are red-black trees?
John Zukowski A red-black tree is a binary search tree where every node has two children or is a leaf. It ensures O(log N) search times, at a cost of a more complicated insertion (and deletion) process. In a red-black tree, every node is colored either red or black, with a black root node, though a black root node isn't a requirement. In addition, if a node is red, its children must be black and every path from root to leaf (or null child node) must contain the same number of black nodes. These rather obscure rules ensure the tree is balanced.