Task: Implementation of the AVLTree class. The partial implementation of the class is given below:

public class AVLTreeMap extends AbstractMap { private int n; private TreeNode root; private TreeNode NIL = new TreeNode(); private MapEntryComparator comp = new MapEntryComparator(); public AVLTreeMap() { /* your implementation */ } public int size() {return n;} public boolean isEmpty() {return n == 0;} public Object get(Object key) { /* your implementation */ } public Object put(Object key, Object value) { /* your implementation */ } private r_get(TreeNode p, String k) { /* your implementation */ } private void insertAVL(TreeNode p, TreeNode node) { /* your implementation */ } private TreeNode rotateLL(TreeNode p) { /* your implementation */ } private TreeNode rotateLR(TreeNode p) { /* your implementation */ } private TreeNode rotateRR(TreeNode p) { /* your implementation */ } private TreeNode rotateRL(TreeNode p) { /* your implementation */ } public Object remove(Object key) { return null; // remove is not required for this assignment } } 

Requirements:

Complete the AVLTreeMap class. You have to complete all the necessary methods declared in the template. You may add your own private method if necessary. The remove method is not rquired. Your implementation has to follow the skeleton codes below.

Test: write a test program that inserts 100 data items and then print them out (in-order).

Please submit the following source codes: AVLTreeMap.java, MapEntryComparator.java, TreeNode.java, AbstractMap.java, MapEntry.java and Test.java.

public class TreeNode extends MapEntry { private TreeNode parent; private TreeNode left; private TreeNode right; private int height; private int bfactor;

public TreeNode() { parent = null; left = null; right = null; height = -1; bfactor = 0; }

public TreeNode (String key, String value) { super (key, value); parent = null; left = null; right = null; height = 0; bfactor = 0; }

In MapEntry class ... add a method void setValue (String value)

// a bunch of getXXX and setXXX for parent, left, right .... getParent(), getLeft(), getRight(), getH(), getBF() setParent(), setLeft(), setRight(), setH(), setBF() }

public class MapEntry Comparator implements Comparator { public int compare (Object a, Object b) { String aa = ((TreeNode)a).getKey(); String bb = ((TreeNode)b).getKey();

if (a == null && b == null) return 0; else if (a == nll) return -1; else if (b == null) return 01; else { int size = Math.min(aa.length(), bb.length()); for (int i = 0; i

else if (aa.charAt(i)>bb.charAt(i)) return 1; // a>b }

if (size == aa.length() && size == bb.length()) return 0; else if (size == aa.length()) return 1; }

public class AVLTreeMap extends AbstractMap { private int n; private TreeNode root; private TreeNode NIL = new TreeNode(); // dummy node private MapEntryComparator comp = new MapEntryComparator();

public AVLTreeMap() { super(); n=0; root = null; }

size(), isEmpty() public object get(Object key) { (<--Compare (key, root.key); if (c == 0) return root.value; else if (c<0) return get(root.left, key); return r_get(root.right, key); }

private String r.get(TreeNde p, String k) { if (p == NIL) return null; c <--- k.compareTo(p.getkey()); if (c == 0) return p.value; else if (c<0) return r.get(p.left, k); return r.get(p.right, k); }

private TreeNode rotate LL (TreeNode p) { pp <--- p.parent; left <--- p.left; y <--- left.right;

y <--- p.parent; if (pp is null) root <--- left;

else if (p is the left child of pp) pp.left <--- left;

else pp.right <--- left; }

left.right <--- p; p.left <--- y; p.parent <--- left;

recalculate p.height and p.bfactor

}