In this case study, we design a second implementation of the IMap<K,V> data type defined in the previous lesson. That second implementation will use binary search trees instead of linear search.

To reduce duplication of code, we define an abstract base class from which all of our implementations of IMap<K,V> can inherit.

To reduce duplication of code in our implementation of binary search trees, we define a second abstract base class from which the classes for empty and non-empty trees can inherit.

This case study will also provide many opportunities to discuss Java-specific syntax, semantics, and APIs.