import java.util.List;

interface Tree> extends TreePrinter.PrintableNode {

// Access fields

BinaryNode root();

// Basic properties

int height();

boolean isBalanced();

void updateHeight();

int size();

// Traversals that return lists

List preOrderList();

List inOrderList();

List postOrderList();

// Helpers for BST/AVL methods

BinaryNode extractRightMost(BinaryNode curNode);

// AVL & BST Search & insert same

BinaryNode search(E elem);

void insert(E elem);

BinaryNode delete (E elem);

}

// From https://stackoverflow.com/questions/4965335/how-to-print-binary-tree-diagram

import java.util.ArrayList;

import java.util.List;

/**

* Binary tree printer

*

* @author MightyPork

*/

public class TreePrinter

{

/** Node that can be printed */

public interface PrintableNode

{

/** Get left child */

PrintableNode getLeft();

/** Get right child */

PrintableNode getRight();

/** Get text to be printed */

String getText();

}

/**

* Print a tree

*

* @param root

* tree root node

*/

public static void print(PrintableNode root)

{

List> lines = new ArrayList>();

List level = new ArrayList();

List next = new ArrayList();

level.add(root);

int nn = 1;

int widest = 0;

while (nn != 0) {

List line = new ArrayList();

nn = 0;

for (PrintableNode n : level) {

if (n == null) {

line.add(null);

next.add(null);

next.add(null);

} else {

String aa = n.getText();

line.add(aa);

if (aa.length() > widest) widest = aa.length();

next.add(n.getLeft());

next.add(n.getRight());

if (n.getLeft() != null) nn++;

if (n.getRight() != null) nn++;

}

}

if (widest % 2 == 1) widest++;

lines.add(line);

List tmp = level;

level = next;

next = tmp;

next.clear();

}

int perpiece = lines.get(lines.size() - 1).size() * (widest + 4);

for (int i = 0; i

List line = lines.get(i);

int hpw = (int) Math.floor(perpiece / 2f) - 1;

if (i > 0) {

for (int j = 0; j

// split node

char c = ' ';

if (j % 2 == 1) {

if (line.get(j - 1) != null) {

c = (line.get(j) != null) ? '' : '';

} else {

if (j

}

}

System.out.print(c);

// lines and spaces

if (line.get(j) == null) {

for (int k = 0; k

System.out.print(" ");

}

} else {

for (int k = 0; k

System.out.print(j % 2 == 0 ? " " : "");

}

System.out.print(j % 2 == 0 ? "" : "");

for (int k = 0; k

System.out.print(j % 2 == 0 ? "" : " ");

}

}

}

System.out.println();

}

// print line of numbers

for (int j = 0; j

String f = line.get(j);

if (f == null) f = "";

int gap1 = (int) Math.ceil(perpiece / 2f - f.length() / 2f);

int gap2 = (int) Math.floor(perpiece / 2f - f.length() / 2f);

// a number

for (int k = 0; k

System.out.print(" ");

}

System.out.print(f);

for (int k = 0; k

System.out.print(" ");

}

}

System.out.println();

perpiece /= 2;

}

}

}

This assignment will focus on the implementation of BST and AVL trees. You will have to tweak some of the logic from the lab for BST. You will also have to maintain parent pointers, size (number of nodes in tree), and the height (different form size) of the tree. These trees will then be used for the search engine. You will be surprised to see how much faster the search engine is! AVL will look very similar to BST but it's a self-balancing tree. Your tasks are to implement all the methods marked with TODO and write test cases checking for accuracy (all methods marked)/efficiency (of the ones we specifically ask). Include edge cases. Be sure to implement these tests using JUnit. Further Clarifications on what some things are supposed to do: - updateHeight - update the height of the tree depending on its right and left subtrees - [traversal]List - return an ArrayList of the nodes it visits in that traversal - mkBalanced - given some Node, return the balanced version of that node. - search - if the node is found, return it, if not return null - delete - if the node is found, delete and then return the deleted. if not found, return null. - main method in SearchEngine: ignore mode 1/2 for ArrayList \& sortedArrayList just focus on BST/AVL Please feel free to use BufferedReader or some other Java import to read any files necessary. Some useful hints: - If your tree is not building fast at all, make sure that your heights are being properly updated. Remember you have the height of the tree and the height of the node. Additionally, it should be constant updating on heights. - Make sure your rotations are actually rotating when needed and not unnecessarily. - TreePrinter.print() will be your best friend in visualizing the structure of the tree. It is not perfect but it will help