Binary Search Tree - Java Implementation

You can use a TreeMap data structure. TreeMap is implemented as a red black tree, which is a self-balancing binary search tree.

According to Collections Framework Overview you have two balanced tree implementations: