Red Black Tree

Self balancing binary search tree.

Searches, Inserts, and Deletes in O(log n) where n is the number of items in the tree.

Its leaf nodes don't contain data (are null).

In Java, TreeMap implements this. TreeMap guarantees the keys of the map will be in ascending order sorted according to the comparator provided in the constructor upon creation of the map.