import java.util.ArrayList;

import java.util.Collection;

import java.util.List;

public class AVL> implements Tree{

private int height;

private int size;

private BinaryNode root;

private int RRotations; // this will be used to see if the amount of rotations was correct

private int LRotations; // this will be used to see if the amount of rotations was correct

public AVL(){

this.root = null;

this.height = 0;

this.size = 0;

this.RRotations = 0;

this.LRotations = 0;

}

public AVL(BinaryNode root){

this.root = root;

this.height = root.height();

this.size = root.size();

this.RRotations = 0;

this.LRotations = 0;

}

// Access fields

public int getRRotations(){

return this.RRotations;

}

public int getLRotations(){

return this.LRotations;

}

public BinaryNode root() {

return this.root;

}

public int height() {

return this.height;

}

public int size() {

return this.size;

}

public boolean isBalanced() {

return root.isBalanced();

}

// TODO: updateHeight - same as BST

public void updateHeight() {

}

// Traversals that return lists

// TODO: Preorder traversal

public List preOrderList() {

return new ArrayList();

}

// TODO: Inorder traversal

public List inOrderList() {

return new ArrayList();

}

// TODO: Postorder traversal

public List postOrderList() {

return new ArrayList();

}

/*

TODO: rotateRight

* x y

* / \ / \

* y C ===> A x

* / \ / \

* A B B C

* You should never rotateRight if the left subtree is empty.

* Make sure you increment the RRotations.

*/

public void rotateRight(BinaryNode node){

}

/*

TODO: rotateLeft

* x y

* / \ / \

* y C

* / \ / \

* A B B C

* You should never rotateLeft if the right subtree is empty.

* Make sure you increment the LRotations.

* Symmetrical to above.

*/

public void rotateLeft(BinaryNode node){

}

/*

TODO: possibleRotateRight

* If the current node is unbalanced with the right tree height being smaller

* than the left subtree height, rotate right. Otherwise, don't do anything.

*/

public void possibleRotateRight(BinaryNode node){

}

/*

TODO: possibleRotateLeft

* If the current node is unbalanced with the left tree height being smaller

* than the right subtree height, rotate left. Otherwise, don't do anything.

*/

public void possibleRotateLeft(BinaryNode node){

}

/*

TODO: mkBalanced

* Given a node, balance it if the heights are unbalanced.

* Hint: rotations!!!

*/

public void mkBalanced(BinaryNode node){

}

// Helpers for BST/AVL methods

// TODO: extractRightMost - identical to BST

public BinaryNode extractRightMost(BinaryNode curNode) {

return null;

}

// AVL & BST Search & insert same

// TODO: search - identical to BST

public BinaryNode search(E elem) {

return null;

}

/*

TODO: insert - slightly different from BST but similar logic

* Hint: mkBalanced will be your best friend here.

*/

public void insert(E elem) {

}

/*

TODO: delete - slightly different from BST but similar logic

* Hint: mkBalanced will be your best friend here.

*/

public BinaryNode delete(E elem) {

return null;

}

// Stuff to help you debug if you want

// Can ignore or use to see if it works.

static > Tree mkAVL (Collection elems) {

Tree result = new AVL();

for (E e : elems) result.insert(e);

return result;

}

public TreePrinter.PrintableNode getLeft() {

return this.root.hasLeft() ? this.root.left() : null;

}

public TreePrinter.PrintableNode getRight() {

return this.root.hasRight() ? this.root.right() : null;

}

public String getText() {

return (this.root != null) ? this.root.getText() : "";

}

}

public class BinaryNode> implements TreePrinter.PrintableNode{

private E data;

private BinaryNode left;

private BinaryNode right;

private int height;

private int size;

private BinaryNode parent;

public BinaryNode(E data){

this.data = data;

this.left = null;

this.right = null;

this.parent = null;

this.height = 1;

this.size = 1;

}

// TODO: Set up the BinaryNode

public BinaryNode(E data, BinaryNode left, BinaryNode right, BinaryNode parent){

}

// Access fields

E data() { return this.data; };

BinaryNode left() {

return this.left;

}

BinaryNode right() {

return this.right;

}

BinaryNode parent() { return this.parent; }

// Setter fields

void setLeft(BinaryNode left) {

this.left = left;

if(left != null) left.setParent(this);

}

void setRight(BinaryNode right) {

this.right = right;

if(right != null) right.setParent(this);

}

void setParent(BinaryNode parent) {

this.parent = parent;

}

void setData(E data) { this.data = data; }

void setHeight(int h){

this.height = h;

}

// Basic properties

int height() {

return this.height;

}

int size() { return this.size; }

boolean isBalanced() {

int leftHeight = (hasLeft()) ? left.height() : 0;

int rightHeight = (hasRight()) ? right().height() : 0;

return Math.abs(leftHeight - rightHeight)

}

boolean hasLeft(){

return left == null ? false : true;

}

boolean hasRight(){

return right == null ? false :true;

}

boolean hasParent(){

return parent == null ? false :true;

}

public boolean equals(BinaryNode other){

if(other == null) return false;

return other.data.equals(this.data);

}

// Can use these to help debug

public TreePrinter.PrintableNode getLeft() {

return left == null ? null : left;

}

public TreePrinter.PrintableNode getRight() {

return right == null ? null : right;

}

public String getText() {

return String.valueOf(data);

}

public String toString(){

String ret = "";

return "root " + this.data + " Left: " +(hasLeft() ? left.data : null) + " Right: " +(hasRight() ? right.data : null) +

" parent: " + (hasParent() ? parent.data : null) ;

}

}

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