Please please help I'm desperate

You must write a Java class HBST that implements a hashed binary search tree, as described in the previous section. Its keys must be instances of the generic class Key, and its values must be instances of the generic class Value, so HBST looks like this. To simplify grading, your code must use the same names as are shown here.

class HBST { ? }

Your class HBST must have two inner classes. One inner class, called ValueNode, must implement the nodes of the association lists that handle collisions. Each ValueNode must have a Key slot called key, a Value slot called value, and a ValueNode slot called next. The other inner class, called TreeNode, must implement the nodes of the binary search tree. It must have an int slot called key, a ValueNode slot called value, and two TreeNode slots called left and right. Dont try to use the same class for both kinds of nodes: that wont work. Your class HBST must also have the following methods. Each method is worth a specific number of points. You may also write extra private helper methods, but they are worth zero points.

public HBST()

(5 points.) Constructor. Initialize a new empty HBST. Your HBST must have a head node (see below).

public Value get(Key key)

(15 points.) If no value is associated with key, then throw an IllegalArgumentException. Otherwise return the value that is associated with key. Note that key may be null, and the returned value may benull.

private int hash(Key key)

(5 points.) Return the hash value of key (see below). You may use any high quality hash function, such as the Java method hashCode, as part of this method. Note that key may be null.

public int height()

(5 points.) Return the height of the HBST. You will need it to show that your HBST works.

public void put(Key key, Value value)

(20 points.) Associate key with value. Note that key may be null, value may be null, or both may be null. You must use the head node (made by the constructor) to avoid the special case that occurs when the HBST is empty.

As stated above, your constructor must make a head node, which must be used by put to avoid a special case when adding a new key-value pair to an empty HBST. The easiest way to do this is to have the key slot of the head node be some integer that cannot be returned by the method hash. This may affect how you write HBSTs constructor, and how you write its hash method.

3. Example.

The following driver class makes an instance of HBST and gives it some predefined Java names as keys, in strictly increasing alphabetical order. If an ordinary BST was used, then this would result in a degenerate tree, but that must not happen here!

class HBSTifier { private final static String[] keys = { "abstract", "assert", "boolean", "break", "byte", "case", "catch", "char", "class", "const", "continue", "default", "do", "double", "else", "extends", "false", "final", "finally", "float", "for", "goto", "if", "implements", "import", "instanceof", "int", "interface", "long", "native", "new", "null", "package", "private", "protected", "public", "return", "short", "static", "super", "switch", "synchronized", "this", "throw", "throws", "transient", "true", "try", "var", "void", "volatile", "while" }; public static void main(String [] args) { HBST hbst = new HBST(); for (int index = 0; index < keys.length; index += 1) { hbst.put(keys[index], index); } System.out.println(hbst.height()); for (int index = 0; index < keys.length; index += 1) { System.out.format("%02d %s", hbst.get(keys[index]), keys[index]); System.out.println(); } } }