public class MyAVLTreeMap extends TreeMap { /** Constructs an empty map using the natural ordering of keys.

Fantastic news! We've Found the answer you've been seeking!

Question:

In this project you will populate a Binary Search Tree_(BST), specifically an AVL tree and print out its contents. For exampl The main class (ProgProject4.java) defines the inputs, creates the AVL and calls the print method (which you will write), in Input of JABCDEFISNDsNRunning the programThe zipped java project file, which contains all your source code in your Eclip

public class MyAVLTreeMap extends TreeMap {

/** Constructs an empty map using the natural ordering of keys. */
public MyAVLTreeMap() { super(); }

/**
* Constructs an empty map using the given comparator to order keys.
* @param comp comparator defining the order of keys in the map
*/
public MyAVLTreeMap(Comparator comp) { super(comp); }

/** Returns the height of the given tree position. */
protected int height(Position> p) {
return tree.getAux(p);
}

/** Recomputes the height of the given position based on its children's heights. */
protected void recomputeHeight(Position> p) {
tree.setAux(p, 1 + Math.max(height(left(p)), height(right(p))));
}

/** Returns whether a position has balance factor between -1 and 1 inclusive. */
protected boolean isBalanced(Position> p) {
return Math.abs(height(left(p)) - height(right(p))) <= 1;
}

/** Returns a child of p with height no smaller than that of the other child. */
protected Position> tallerChild(Position> p) {
if (height(left(p)) > height(right(p))) return left(p); // clear winner
if (height(left(p)) < height(right(p))) return right(p); // clear winner
// equal height children; break tie while matching parent's orientation
if (isRoot(p)) return left(p); // choice is irrelevant
if (p == left(parent(p))) return left(p); // return aligned child
else return right(p);
}

/**
* Utility used to rebalance after an insert or removal operation. This traverses the
* path upward from p, performing a trinode restructuring when imbalance is found,
* continuing until balance is restored.
*/
protected void rebalance(Position> p) {
int oldHeight, newHeight;
do {
oldHeight = height(p); // not yet recalculated if internal
if (!isBalanced(p)) { // imbalance detected
// perform trinode restructuring, setting p to resulting root,
// and recompute new local heights after the restructuring
p = restructure(tallerChild(tallerChild(p)));
recomputeHeight(left(p));
recomputeHeight(right(p));
}
recomputeHeight(p);
newHeight = height(p);
p = parent(p);
} while (oldHeight != newHeight && p != null);
}

/** Overrides the TreeMap rebalancing hook that is called after an insertion. */
@Override
protected void rebalanceInsert(Position> p) {
rebalance(p);
}

/** Overrides the TreeMap rebalancing hook that is called after a deletion. */
@Override
protected void rebalanceDelete(Position> p) {
if (!isRoot(p))
rebalance(parent(p));
}

/** Ensure that current tree structure is valid AVL (for debug use only). */
private boolean sanityCheck() {
for (Position> p : tree.positions()) {
if (isInternal(p)) {
if (p.getElement() == null)
System.out.println("VIOLATION: Internal node has null entry");
else if (height(p) != 1 + Math.max(height(left(p)), height(right(p)))) {
System.out.println("VIOLATION: AVL unbalanced node with key " + p.getElement().getKey());
dump();
return false;
}
}
}
return true;
}

public void printTree() {
// Put your code to print AVL tree here
System.out.println("Print of tree");
}

}
public class ProgProject4 {
public static void main(String[] args) {
String[] inputs = {
"CBDAE",
"DACBEFMLGHJK",
"JABCDEFISN"
};
for (int k=0; kMyAVLTreeMap mytree = new MyAVLTreeMap();
// this code populates your tree
for (int i =0 ; i< inputs[k].length(); i++) {
mytree.put(inputs[k].substring(i,i+1), 1);
}
System.out.println("Input of " + inputs[k]);
// this line of code call the printTree method you are to write
mytree.printTree();
System.out.println();

}

}
}