Using the templates below, create an AVL Tree Map in java (fill in the places where it says // fix this). In other words, create an AVL Tree which implements the Map interface. The Map interface as well as a template AVLTreeMap.java class is given below.

public class AVLTreeMap implements Map {

class Node { String key; String value; int height; Node parent; // delete this variable for extra credit Node left; Node right; public Node(String key, String value) { this.key = key; this.value = value; this.height = 1; this.parent = null; this.left = null; this.right = null; } public int balance() { // FIXME return -1; } }

private int size; private Node root;

public AVLTreeMap() { // FIXME }

public int size() { // FIXME return -1; }

public void put(String key, String value) { // FIXME }

public String get(String key) { // FIXME return null; }

public void print() { this.print(this.root, "", 0); }

private void print(Node node, String prefix, int depth) { if (node == null) { return; } for (int i = 0; i < depth; i++) { System.out.print(" "); } if (!prefix.equals("")) { System.out.print(prefix); System.out.print(":"); } System.out.print(node.key); System.out.print(" ("); System.out.print("H:"); System.out.print(node.height); System.out.print(", B:"); System.out.print(node.balance()); System.out.println(")"); this.print(node.left, "L", depth + 1); this.print(node.right, "R", depth + 1); }

public static void main(String[] args) { AVLTreeMap map = new AVLTreeMap(); String[] keys = {"7", "9", "6", "0", "4", "2", "1"}; String[] values = {"seven", "nine", "six", "zero", "four", "two", "one"}; for (int i = 0; i < keys.length; i++) { map.put(keys[i], values[i]); map.print(); System.out.println(); } for (int i = 0; i < keys.length; i++) { System.out.print(keys[i]); System.out.print(" "); System.out.println(map.get(keys[i])); } } }