Constructing UnbalancedTreeMap
In this section, you need to first implement a class OrderedKeyValue to store an ordered
pair of a String key and its Integer value. Then, you should implement the class Unbal-
ancedTreeMap which stores objects of class OrderedKeyValue in the unbalanced binary
search tree.
Class OrderedKeyValue which implements Comparable interface of Java must include
the following members:
1. String key;
2. int value;
3. A constructor for creating a new object with key and value initialized by the input
parameters.
4. int compareTo(OrderedKeyValue other) that implements the interface Comparable
〈OrderedKeyValue〉 by comparing the keys of two OrderedKeyValues based on the
alphabetical order and in a case-insensitive fashion.
Class UnbalancedTreeMap must include the following members:
1. BinaryNode〈OrderedKeyValue〉 root; which is the root of your binary search tree and
BinaryNode〈E〉 is a class with the following instance fields: E element, BinaryNode〈E〉
left, and BinaryNode〈E〉 right. The binary search tree that you’re supposed to construct
uses the instances of BinaryNode〈OrderedKeyValue〉 as its nodes.
2. A constructor to create an empty tree map;public int get(String key): searches through the binary search tree to see whether
any node stores an object of OrderedKeyValue which matches the input key. If such
OrderedKeyValue is found, the method returns its value; otherwise, it returns 0. Ob-
viously, your method should perform O(log n) comparisons for each search operation
as you use a BST.
4. public int put(String key, int value): searches through the tree to see whether any node
stores an object of OrderedKeyValue which matches the input key. If such Ordered-
KeyValue is found, the method sets its value to the one given by the second input
parameter and returns the previous value as the method output; otherwise, it inserts
a new node to the tree to store the given key and value and returns 0. Again, your
method should execute O(log n) instructions for each insert operation as you use a
BST.
5. public String[] keySet(): By visiting the nodes of BST using in-order traversal, you
should store the keys in an array of strings and return the array at the end. The
returned array contains all the keys in alphabetical order.