CSC212 Lab 10 Solutions 2014

--D. Thiebaut (talk) 12:55, 31 October 2014 (EDT)

---

Source: IntBST.java

/**
 * IntBST.java
 * @author D. Thiebaut
 * All material taken, and adapted from Drozdek's
 * Data Structures and Algorithms in Java.
 * 
 */
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

/**
 * A class implementing a BST node, with an integer key, and a left and right
 * pointer.
 * 
 * @author thiebaut
 *
 */
class IntBSTNode {

	public int key;
	public IntBSTNode left, right;

	IntBSTNode(int el, IntBSTNode l, IntBSTNode r) {
		key = el;
		left = l;
		right = r;
	}

	IntBSTNode(int el) {
		this(el, null, null);
	}
}

/**
 * The tree class. Implements most useful methods.
 * 
 * @author thiebaut
 *
 */
public class IntBST {
	protected IntBSTNode root;
	private int counter;
	private int maxLevel;
	private int noProbes;

	/**
	 * constructor creates an empty tree.
	 */
	IntBST() {
		root = null;
	}

	protected void setRoot(IntBSTNode p) {
		root = p;
	}

	public void clear() {
		root = null;
	}

	/**
	 * Just use for debugging... Recursively visits the tree and display
	 * information about what it finds.
	 */
	protected void debugVisit() {
		debugVisit(root);
	}

	protected void debugVisit(IntBSTNode p) {
		if (p == null)
			return;
		String leftString = "has no left child", rightString = "has no right child";
		if (p.left != null)
			leftString = "has " + p.left.key + " as left child";
		if (p.right != null)
			rightString = "has " + p.right.key + " as right child";
		System.out.println("Node " + p.key + ", " + leftString + ", and "
				+ rightString);
		debugVisit(p.left);
		debugVisit(p.right);
	}

	/**
	 * Iteratively searches for an element in the tree. Returns the node
	 * containing the element if found, or null otherwise.
	 * 
	 * @param el
	 * @return
	 */
	public IntBSTNode search(int el) {
		IntBSTNode p = root;
		noProbes = 0;
		while (p != null) {
			noProbes++;
			if (el == p.key)
				return p;
			if (el < p.key)
				p = p.left;
			else
				p = p.right;
		}
		return null;
	}

	/**
	 * recursively searches for an element in the tree. Returns the node
	 * containing the element, or null if not found.
	 * 
	 * @param el
	 * @return
	 */
	public IntBSTNode recSearch(int el) {
		return recSearch(root, el);
	}

	private IntBSTNode recSearch(IntBSTNode p, int el) {
		if (p == null)
			return null;
		if (el == p.key)
			return p;
		if (el < p.key)
			return recSearch(p.left, el);
		else
			return recSearch(p.right, el);
	}

	/**
	 * counts the number of nodes in the tree
	 * 
	 * @return the number of nodes.
	 */
	public int countNodes() {
		counter = 0;
		countNodes(root);
		return counter;
	}

	public void countNodes(IntBSTNode p) {
		if (p == null)
			return;
		counter++;
		countNodes(p.left);
		countNodes(p.right);
	}

	/**
	 * computes the height of the tree
	 * 
	 * @return
	 */
	public int computeHeight() {
		maxLevel = 0;

		// start recursing on the root
		computeHeight(root, 0);

		// when we come back, the maxHeight will have been set
		return maxLevel + 1;
	}

	private void computeHeight(IntBSTNode p, int level) {

		// if p is a valid node, and if the height is greater than maxLevel,
		// then update maxLevel with current height.
		if (p == null)
			return;

		// deeper than we have been so far?
		if (level > maxLevel)
			maxLevel = level;

		computeHeight(p.left, level + 1);
		computeHeight(p.right, level + 1);
	}

	/**
	 * Traveral methods inOrderVisit preOrderVisit postOrderVisit
	 */
	public void inOrderVisit() {
		inOrderVisit(root);
		System.out.println();
	}

	private void inOrderVisit(IntBSTNode p) {
		if (p == null)
			return;
		inOrderVisit(p.left);
		System.out.print(p.key + " ");
		inOrderVisit(p.right);
	}

	public void preOrderVisit() {
		preOrderVisit(root);
		System.out.println();
	}

	private void preOrderVisit(IntBSTNode p) {
		if (p == null)
			return;
		System.out.print(p.key + " ");
		preOrderVisit(p.left);
		preOrderVisit(p.right);
	}

	public void postOrderVisit() {
		postOrderVisit(root);
		System.out.println();
	}

	private void postOrderVisit(IntBSTNode p) {
		if (p == null)
			return;
		postOrderVisit(p.left);
		postOrderVisit(p.right);
		System.out.print(p.key + " ");
	}

	/**
	 * visits the tree breadth-first. Display the key in all the nodes, in
	 * breadth-first order.
	 */
	public void breadthFirst() {
		IntBSTNode p = root;
		Queue<IntBSTNode> queue = new LinkedList<IntBSTNode>();

		if (p == null)
			return;

		queue.add(p);
		while (!queue.isEmpty()) {
			p = queue.poll();
			// --- do some work with the key. Here we just print it...
			System.out.print(p.key + " ");
			if (p.left != null)
				queue.add(p.left);
			if (p.right != null)
				queue.add(p.right);
		}
	}

	/**
	 * Inserts an element in the tree. We assume that the element is not already
	 * there.
	 * 
	 * @param el
	 */
	public void insert(int el) {
		// is the tree empty? if so, create 1 node
		if (root == null) {
			root = new IntBSTNode(el);
			return;
		}

		// go down to the leaf that will be the parent
		// of the new node
		IntBSTNode p = root, prev = null;
		while (p != null) {
			prev = p;
			if (p.key < el)
				p = p.right;
			else
				p = p.left;
		}

		// add element as new leaf of prev's node
		if (el < prev.key)
			prev.left = new IntBSTNode(el);
		else
			prev.right = new IntBSTNode(el);
	}

	/**
	 * Delete element by merging. Finds the element, then the largest of its
	 * left-subtree, and attaches the right-subtree of the node to delete to
	 * this largest element.
	 * 
	 * @param el
	 *            : the key we want to remove.
	 */
	public void delete(int el) {
		IntBSTNode tmp, node, p = root, prev = null;

		if (root == null) {
			System.out.println("Trying to delete from an empty tree");
			return;
		}

		// find the node containing el
		while (p != null && p.key != el) {
			prev = p;
			if (p.key < el)
				p = p.right;
			else
				p = p.left;
		}

		if (p == null) {
			System.out.println("Key " + el + " not in tree");
			return;
		}

		// we found the element. p is pointing to it. prev is pointing to
		// parent (or is null if el is in root).
		node = p;

		// no right sub-tree?
		if (node.right == null) {
			// yes, then pick the left subtree
			node = node.left;
		} else if (node.left == null) {
			// yes, then pick the right subtree
			node = node.right;
		} else {
			// two existing subtrees.
			// go to left subtree
			tmp = node.left;

			// and find the right-most node that doesn't have a right child.
			while (tmp.right != null)
				tmp = tmp.right;

			// tmp points to right-most node (blue node)

			// attach right subtree of node we're deleting (yellow node)
			// to right most node (blue node)
			tmp.right = node.right;

			node = node.left;
		}

		if (p == root)
			root = node;
		else if (prev.left == p)
			prev.left = node;
		else
			prev.right = node;
	}

	/**
	 * balance the tree by copying all the keys into an array first, then
	 * sorting the array, then doing some binary split operation, going to the
	 * middle of the array to find the root, then to the middle of the two
	 * halves to find the children of the root, etc... and rebuilding the tree
	 * that way.
	 * 
	 * @return
	 */
	private void addNodeToArray(IntBSTNode p, ArrayList allNodes) {
		if (p == null)
			return;
		addNodeToArray(p.left, allNodes);
		allNodes.add(p.key);
		addNodeToArray(p.right, allNodes);
	}

	public void balance() {
		// visit the tree and copy all the nodes into an ArrayList
		// visit in in-order fashion, so as to create a sorted list of keys in
		// the array
		ArrayList allNodes = new ArrayList();
		addNodeToArray(root, allNodes);

		// recursively reconstruct the tree
		clear();
		recursiveBalance(allNodes, 0, allNodes.size() - 1);
	}

	private void recursiveBalance(ArrayList allNodes, int low, int high) {
		if (low <= high) {
			int mid = (low + high) / 2;
			insert((int) allNodes.get(mid));
			recursiveBalance(allNodes, low, mid - 1);
			recursiveBalance(allNodes, mid + 1, high);
		}
	}

	/**
	 * generateDot: generates the dot representation of the tree.
	 */
	public void generateDot() {
		System.out.println("digraph T {\nlabel = \"Mickey Mouse\";");
		generateDot(root);
		System.out.println("}");
	}

	private void generateDotLowKey(IntBSTNode p) {
		if (p == null)
			return;
		if (p.left != null)
			System.out.println(p.key + " -> " + p.left.key + ";");
		if (p.right != null)
			System.out.println(p.key + " -> " + p.right.key + ";");

		generateDot(p.left);
		generateDot(p.right);
	}

	private void generateDot(IntBSTNode p) {
		if (p == null)
			return;
		if (p.left != null)
			System.out.println(p.key + " -> " + p.left.key + ";");
		else {
			String nullNode = "null" + p.key
					+ "left [label=\"\",width=.1,style=invis]";
			System.out.println(nullNode + ";");
			System.out.println(p.key + " -> " + nullNode + " [style=invis];");
		}
		if (p.right != null)
			System.out.println(p.key + " -> " + p.right.key + ";");
		else {
			String nullNode = "null" + p.key
					+ "right [label=\"\",width=.1,style=invis]";
			System.out.println(nullNode + ";");
			System.out.println(p.key + " -> " + nullNode + " [style=invis];");
		}

		generateDot(p.left);
		generateDot(p.right);
	}

	private int getNoProbes() {
		return noProbes;
	}

	/**
	 * M A I N P R O G R A M
	 *
	 */
	static public void main(String[] args) {
		IntBST tree = new IntBST();

		// create a new tree by using insert()
		int[] keys = new int[] { 8, 30, 10, 1, 6, 14, 4, 7, 13 };

		for (int i = 0; i < keys.length; i++)
			tree.insert(keys[i]);

		tree.debugVisit();
		System.out.println( "Number of nodes = " + tree.countNodes() );
		System.out.println( "Height of tree  = " + tree.computeHeight() );

		tree.clear();
		
		int N = 32;
		Random randomGenerator = new Random();
		for ( int i=0;  i < N; i++ ) {
			int el = Math.abs( randomGenerator.nextInt() );
			if ( tree.search(el) == null )
			tree.insert( el );
		}

		// insert a key we know
		tree.insert( 3300000 );

		// pick 10 keys we're going to search for, including 33, which should result in a successful search...
		keys = new int[] { 17905000 , 3111463, 3300000, 60600000, 8989000, 
		                                   869000004, 1769211540, 4000000, 269211540, 56891000 };

		// search for each of the 10 keys and display # of probes...
		for ( int i=0; i < keys.length; i++ ) {
		     IntBSTNode p = tree.search(  keys[i] );
		     
		     // get the number of probes
		     int probes = tree.getNoProbes();

		     System.out.println( "Searching for " + keys[i] + " required " + probes + " probes." );
		}

	}

}

Output

Node 8, has 1 as left child, and has 30 as right child
Node 1, has no left child, and has 6 as right child
Node 6, has 4 as left child, and has 7 as right child
Node 4, has no left child, and has no right child
Node 7, has no left child, and has no right child
Node 30, has 10 as left child, and has no right child
Node 10, has no left child, and has 14 as right child
Node 14, has 13 as left child, and has no right child
Node 13, has no left child, and has no right child
Number of nodes = 9
Height of tree  = 5
Searching for 17905000 required 4 probes.
Searching for 3111463 required 4 probes.
Searching for 3300000 required 4 probes.
Searching for 60600000 required 4 probes.
Searching for 8989000 required 4 probes.
Searching for 869000004 required 11 probes.
Searching for 1769211540 required 5 probes.
Searching for 4000000 required 4 probes.
Searching for 269211540 required 4 probes.
Searching for 56891000 required 4 probes.