Please change the BST.java as followed: In the case in which the deleted node has two children, write the code in two ways.

a) always replace the deleted node with the largest node on the left.

b) count how many deletions have been done, and for even deletions replace the deleted node with the largest node on the left, for odd deletions, replace the deleted node with the smallest node on the right.

Now do an experiment in which you add 100 random Doubles to the tree, then repeatedly delete and add values many times. (Keep an array of the numbers currently in the tree and randomly choose an element of the array to delete.)

As you do each random deletion and insertion, note the depth of the tree, and create a graph (using Excel?) that shows how the tree's depth changes.

Do this experiment for each of the deletion strategies a) and b). How do the graphs differ?

To generate the random numbers needed,

import java.util.Random; then in your code,

Random ran = new Random(); ran.nextDouble(); gives a double between 0.0 and 1.0 ran.nextInt(n) gives a random integer between 0 and n-1 inclusive

BST.java:

public class BST> { private Node root;

public BST() { this.root = null; }

public void insert(T datum) throws BSTException { this.root = insert(this.root, datum); }

private Node insert(Node r, T datum) throws BSTException { if( r == null) { return new Node(datum); } else { int sign = r.getData().compareTo(datum); if(sign == 0) { throw new BSTException("Duplicate Entry " + datum); } else if(sign > 0) { r.setLeft(insert(r.getLeft(), datum)); } else { r.setRight(insert(r.getRight(), datum)); } return r; } }

public T lookup(T target) { Node where = root; T retval = null;

while (where != null && retval == null) { int sign = where.getData().compareTo(target); if (sign == 0) retval = where.getData(); else if(sign > 0) where = where.getLeft(); else where = where.getRight(); } return retval; } public void delete(T target) { root = delete(root, target); return; }

private Node delete(Node root, T target) { //Tree is empty if (root == null) return root; // if not empty tree, search recursively for target int sign = target.compareTo(root.getData()); if (sign < 0) //go left root.setLeft(delete(root.getLeft(), target)); else if (sign > 0) //go right root.setRight(delete(root.getRight(), target)); else // sign == 0 so we found it { //case 1 and 2: 0 or 1 child if (root.getLeft() == null) return root.getRight(); else if (root.getRight() == null) return root.getLeft();

//if we get here, there are 2 children. //replace our data with minimum data //in right subtree root.setData(minOnRight(root.getRight())); //or with maximum data in left subtree //root.setData(maxOnLeft(root.getLeft()); //finally, delete the node whose data we //copied root.setRight(delete(root.getRight(), root.getData())); } return root; } private T minOnRight(Node r) { while(r.getLeft() != null) r = r.getLeft(); return r.getData(); }

public int getDepth() { return getDepth(root); }

public int getDepth(Node r) { int retval = -1; if (r == null) return retval; else { retval = Math.max(getDepth(r.getLeft()), getDepth(r.getRight()) ) + 1; } return retval; }

public String toString() { String retval = ""; return toString(root, retval); }

public String toString(Node r, String retval) { if (r == null) { return retval + "null" + " "; } else { retval += r.getData() + " "; retval = toString(r.getLeft(), retval); retval = toString(r.getRight(), retval); } return retval; }

public static void main(String args[]) throws BSTException { BST sbst = new BST(); sbst.insert("horse"); sbst.insert("cow"); sbst.insert("manticore"); sbst.insert("jaguar"); sbst.insert("zebra"); sbst.insert("aardvark"); sbst.insert("duck"); System.out.println(sbst); System.out.println(); sbst.delete("horse"); System.out.println(sbst); } }

Node.java:

public class Node> { private T data; private Node left; private Node right; private int depth;

public Node(T data, Node left, Node right) { this.data = data; this.left = left; this.right = right; }

public Node(T data) { this(data, null, null); }

public T getData() { return this.data; }

public Node getLeft() { return this.left; }

public Node getRight() { return this.right; } public void setData(T val) { this.data = val; } public void setLeft(Node left) { this.left = left; }

public void setRight(Node r) { this.right = r; }

public void setDepth(int d) { this.depth = d; }

public int getDepth() { return this.depth; } }

BSTException.java:

public class BSTException extends Exception { public BSTException() { super("BST Exception"); }

public BSTException(String s) { super(s); } }