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() { this.height = root.height(); } // Traversals that return lists // TODO: Preorder traversal public List preOrderList() { List list = new ArrayList<>(); preOrderTraversal(root, list); return list; } private void preOrderTraversal(BinaryNode node, List list) { if (node == null) { return; } list.add(node.data()); preOrderTraversal(node.left(), list); preOrderTraversal(node.right(), list); } // TODO: Inorder traversal public List inOrderList() { List list = new ArrayList<>(); inOrderTraversal(root, list); return list; } private void inOrderTraversal(BinaryNode node, List list) { if (node == null) { return; } inOrderTraversal(node.left(), list); list.add(node.data()); inOrderTraversal(node.right(), list); } // TODO: Postorder traversal public List postOrderList() { List list = new ArrayList<>(); postOrderTraversal(root, list); return list; } private void postOrderTraversal(BinaryNode node, List list) { if (node == null) { return; } postOrderTraversal(node.left(), list); postOrderTraversal(node.right(), list); list.add(node.data()); } /* 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){ if (node == null || node.left() == null) { return; } BinaryNode left = node.left(); node.setLeft(left.right()); left.setRight(node); //node.updateSize(); //left.updateSize(); if (root == node) { root = left; } RRotations++; } /* 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){ if (node == null || node.right() == null) { return; } BinaryNode right = node.right(); node.setRight(right.left()); right.setLeft(node); //node.updateSize(); //right.updateSize(); if (root == node) { root = right; } LRotations++; } /* 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){ if (node == null) { return; } int balanceFactor = node.balanceFactor(); if (balanceFactor > 1 && node.left().balanceFactor() < 0) { rotateLeft(node.left()); } if (balanceFactor > 1) { rotateRight(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){ if (node == null) { return; } int balanceFactor = node.balanceFactor(); if (balanceFactor < -1 && node.right().balanceFactor() > 0) { rotateRight(node.right()); } if (balanceFactor < -1) { rotateLeft(node); } } /* TODO: mkBalanced * Given a node, balance it if the heights are unbalanced. * Hint: rotations!!! */ public void mkBalanced(BinaryNode node){ if (node == null) { return; } node.updateHeight(); node.updateSize(); possibleRotateRight(node); possibleRotateLeft(node); int balanceFactor = node.getBalanceFactor(); if (balanceFactor == 2) { if (node.getRight().getBalanceFactor() < 0) { rotateRight(node.getRight()); } rotateLeft(node); } else if (balanceFactor == -2) { if (node.getLeft().getBalanceFactor() > 0) { rotateLeft(node.getLeft()); } rotateRight(node); } mkBalanced(node.getLeft()); mkBalanced(node.getRight()); } // Helpers for BST/AVL methods // TODO: extractRightMost - identical to BST public BinaryNode extractRightMost(BinaryNode curNode) { if (curNode.hasRight() == false) { if (curNode.hasLeft()) { curNode.left.parent = curNode.parent; } if (curNode.hasParent() == true) { if (curNode.parent.right == curNode) { curNode.parent.right = curNode.left; } else { curNode.parent.left = curNode.left; } curNode.left = null; curNode.right = null; curNode.updateSize(); curNode.updateHeight(); mkBalanced(curNode.parent); } curNode.parent = null; return curNode; } else { BinaryNode node = extractRightMost(curNode.right); curNode.updateHeight(); curNode.updateSize(); mkBalanced(curNode); return node; } } // AVL & BST Search & insert same // TODO: search - identical to BST public BinaryNode search(E elem) { BinaryNode node = root; while (node != null) { int cmp = elem.compareTo(node.data); if (cmp == 0) { return node; } else if (cmp < 0) { node = node.left; } else { node = node.right; } } return null; } /* TODO: insert - slightly different from BST but similar logic * Hint: mkBalanced will be your best friend here. */ public void insert(E elem) { BinaryNode node = new BinaryNode<>(elem); if (root == null) { root = node; return; } BinaryNode parent = root; while (true) { int cmp = elem.compareTo(parent.data); if (cmp == 0) { return; } else if (cmp < 0) { if (parent.left == null) { parent.left = node; node.parent = parent; parent.updateSize(); parent.updateHeight(); mkBalanced(parent); return; } else { parent = parent.left; } } else { if (parent.right == null) { parent.right = node; node.parent = parent; parent.updateSize(); parent.updateHeight(); mkBalanced(parent); return; } else { parent = parent.right; } } } } /* TODO: delete - slightly different from BST but similar logic * Hint: mkBalanced will be your best friend here. */ public BinaryNode delete(E elem) { if (this.root == null) { return null; } BinaryNode target = search(elem); if (target == null) { return null; } this.root = deleteHelper(this.root, elem); return target; } private BinaryNode deleteHelper(BinaryNode node, E elem) { if (node == null) { return null; } if (elem.compareTo(node.data()) < 0) { node.setLeft(deleteHelper(node.left(), elem)); } else if (elem.compareTo(node.data()) > 0) { node.setRight(deleteHelper(node.right(), elem)); } else { if (node.isLeaf()) { return null; } else if (node.hasLeft() && !node.hasRight()) { return node.left(); } else if (node.hasRight() && !node.hasLeft()) { return node.right(); } else { BinaryNode replacement = extractRightMost(node.left()); node.setData(replacement.data()); node.setLeft(deleteHelper(node.left(), replacement.data())); } } mkBalanced(node); return node; } // 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() : ""; } } 

---different class---

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){ this.data = data; setLeft(left); setRight(right); setParent(parent); this.height = 1; this.size = 1; } // 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) < 2; } 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) ; } } 

---please fix red underline error---

i can't find what is problem