Please finish everything marked TODO

AVL.java

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 x * / \ / \ * 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() : ""; }

}