(20 points) Write an instance method isMinHeap(loc) for ArrayTree that takes in a location and determines if the tree rooted at that location is a valid MinHeap. (25 points) Write an instance method...

(20 points) Write an instance method isMinHeap(loc) for ArrayTree that takes in a location and determines if the tree rooted at that location is a valid MinHeap. (25 points) Write an instance method isRedBlackTree() for RedBlackNode that determines if the tree rooted at this node satisfies all the properties of a Red-Black tree. The first property is already taken care of since RedBlackNoes have the red variable set in the constructor. You will need to check the other 3 properties and return true if they are all satisfied and false if any of them are broken. A red-black tree should also be a valid binary search tree, but don’t worry about verifying that yet. (20 points) Write an instance method isBST() for TreeNode that determines if the tree rooted at this node is a binary search tree. Assume that all the keys are unique so you don’t have to worry about cases like these Where it depends which side you put equal values on.


package hw3_skeleton; import java.util.Arrays; class ArrayTree, V> { TreeElement[] tree; // Sets up an initial array for the tree with 1 slot for the root @SuppressWarnings("unchecked") public ArrayTree() { tree = (TreeElement[]) new TreeElement[1]; } public TreeElement getLeft(int loc) { return locToElement(getLeftLoc(loc)); } public TreeElement getRight(int loc) { return locToElement(getRightLoc(loc)); } public TreeElement getParent(int loc) { return locToElement(getParentLoc(loc)); } public int getLeftLoc(int loc) { return 2 * loc + 1; } public int getRightLoc(int loc) { return 2 * loc + 2; } public int getParentLoc(int loc) { return (loc - 1) / 2; } // returns the element stored at a location public TreeElement locToElement(int loc) { if (loc >= tree.length || loc < 0)="" return="" null;="" else="" return="" tree[loc];="" }="" only="" method="" that="" actually="" adds="" things="" to="" the="" array="" public="" void="" setloc(int="" loc,=""> e) { if (loc < 0)="" throw="" new="" indexoutofboundsexception("tree="" locations="" must="" be="" 0="" or="" more");="" if="" we're="" adding="" something="" beyond="" the="" length="" of="" the="" tree="" array,="" then="" we="" must="" grow="" the="" array="" if="" (loc="">= tree.length) resize(); tree[loc] = e; e.setTreeLocation(loc); } // takes a location in the tree and a new Element // makes that element the left child of the node at loc public void setLeft(int loc, TreeElement e) { setLoc(getLeftLoc(loc), e); } // takes a location in the tree and a new Element // makes that element the right child of the node at loc public void setRight(int loc, TreeElement e) { setLoc(getRightLoc(loc), e); } @SuppressWarnings("unchecked") private void resize() { // double the size of the array // adds just enough spaces for one more full level of a complete tree int new_length = tree.length * 2 + 1; // create new array TreeElement[] temp_tree = (TreeElement[]) new TreeElement[new_length]; // copy contents of old array to new array for (int i = 0; i < tree.length;="" i++)="" {="" temp_tree[i]="tree[i];" }="" set="" replace="" old="" array="" with="" the="" new="" one="" tree="temp_tree;" }="" @override="" public="" string="" tostring()="" {="" returns="" string="" representation="" of="" tree="" array="" which="" holds="" nodes="" in="" complete="" order="" i.e.="" left="" to="" right,="" top="" to="" bottom="" return="" "arraytree="" "="" +="" arrays.tostring(tree);="" }="" public=""> getUncle(int loc) { // TODO if(locToElement(getParentLoc(getParentLoc(loc))) == null) return null; if(getRightLoc(getParentLoc(getParentLoc(loc)))!=getParentLoc(getParentLoc(loc)) ) return locToElement(getRightLoc(getParentLoc(getParentLoc(loc)))); if(getLeftLoc(getParentLoc(getParentLoc(loc)))!=getParentLoc(getParentLoc(loc)) ) return locToElement(getLeftLoc(getParentLoc(getParentLoc(loc)))); return null; } public boolean isMinHeap(int loc) { // TODO return false; } } package hw3_skeleton; public class Main { public static void main(String[] args) throws Exception { // setup a tree for testing RedBlackNode root = new RedBlackNode(5, "A"); root.setBlack(); root.setLeft(new RedBlackNode(3, "B", "black")); root.setRight(new RedBlackNode(6, "C", "black")); root.getLeft().setRight(new RedBlackNode(4, "D")); System.out.println(root.printSubTree()); // TreeNode [red=false, key=5, value=A] // |--left| TreeNode [red=false, key=3, value=B] // | |--right| TreeNode [red=true, key=4, value=D] // |--right| TreeNode [red=false, key=6, value=C] System.out.println(root.getLeft().getRight().getUncle()); //TreeNode [red=false, key=6, value=C] System.out.println(root.getLeft().getRight().nextInOrder()); //TreeNode [red=false, key=5, value=A] System.out.println(root.isRedBlackTree()); //true System.out.println(root.isBST()); //true // setup a tree for testing ArrayTree tree = new ArrayTree(); tree.setLoc(0, new TreeElement(3, "A")); tree.setLeft(0, new TreeElement(5, "B")); tree.setRight(0, new TreeElement(7, "C")); tree.setRight(tree.getLeftLoc(0), new TreeElement(6, "D")); System.out.println(tree); //ArrayTree [TreeElement [key=3, treeLocation=0, value=A], TreeElement [key=5, treeLocation=1, value=B], TreeElement [key=7, treeLocation=2, value=C], null, TreeElement [key=6, treeLocation=4, value=D], null, null] System.out.println(tree.getUncle(4)); //TreeElement [key=7, treeLocation=2, value=C] System.out.println(tree.isMinHeap(0)); //true } } package hw3_skeleton; import java.security.InvalidParameterException; import java.util.ArrayList; public class RedBlackNode, V> extends TreeNode { // red node if this is true, black if false private boolean red; private int totalblacks; // default to red public RedBlackNode(K key, V value) { super(key, value); red = true; } // can take a string to set color // this makes things a little easier when testing public RedBlackNode(K key, V value, String color) { super(key, value); if (color.equalsIgnoreCase("black")) setBlack(); else if (color.equalsIgnoreCase("red")) setRed(); else throw new InvalidParameterException("color must be red or black"); } public boolean isRed() { return red; } public boolean isBlack() { return !red; } public void setRed() { this.red = true; } public void setBlack() { this.red = false; } public RedBlackNode getLeft() { return (RedBlackNode) left; } public RedBlackNode getRight() { return (RedBlackNode) right; } public RedBlackNode getParent() { return (RedBlackNode) parent; } @Override public String toString() { return "TreeNode [red=" + red + ", " + "key=" + getKey() + ", value=" + getValue() + "]"; } public Boolean isRedBlackTree() { totalblacks = -1; if (this.isRed()) return false; int currentblacks = 0; return this.isRBThelp(currentblacks); } private Boolean isRBThelp(int cb) { if (this.isBlack()) { cb++; if (this.getLeft() != null) if (!this.getLeft().isRBThelp(cb)) { System.out.println("78" + ' ' + cb +' ' + totalblacks); return false; } if (this.getRight() != null) if (!this.getRight().isRBThelp(cb)) { System.out.println("84" + ' ' + cb +' ' + totalblacks); return false; } if (this.getLeft() == null && this.getRight() == null) { if (totalblacks == -1){ totalblacks = cb; System.out.println("totalblacks set to " +totalblacks); } else { if (cb != totalblacks) { System.out.println("92" + ' ' + cb +' ' + totalblacks); return false; } else return true; } } } if (this.isRed()) { if (this.getLeft() != null) { if (this.getLeft().isBlack()) { if (!this.getLeft().isRBThelp(cb)) { System.out.println(104); return false; } } else { System.out.println(108); return false; } if (this.getRight() != null) { if (this.getRight().isBlack()) { if (!this.getRight().isRBThelp(cb)) { System.out.println(115); return false; } } else { System.out.println(119); return false; } } if (this.getLeft() == null && this.getRight() == null) { if (totalblacks == -1){ totalblacks = cb; System.out.println("totalblacks set to " +totalblacks); } else { if (cb != totalblacks) { System.out.println(129); return false; } else return true; } } } } return true; } }