AbstractMap and AbstractSet

You may find it useful to have your Treap extend AbstractMap. AbstractMap is an abstract class implementing Map which already has implementations of many of the methods you will need - equals, hashCode, toString, containsKey, size, etc. However, some of these implementations require use other parts of your code. For example, AbstractMap's equals method relies on a working equals method for your Map.Entry implementation and a working entry set iterator. You will have to write these anyway, so extending AbstractMap to save yourself some work is a good idea. This is what your class signature would look like:

  public class Treap<K, V> extends AbstractMap<K, V> implements SortedMap<K, V> {

Take a look at the API and source code for AbstractMap:

AbstractMap API

AbstractMap source code

There is an analogous AbstractSet class which you can use for EntrySet.