CSC212 IntBST.java: A Non-Generic BST Implementation

--D. Thiebaut (talk) 19:59, 28 October 2014 (EDT)

---

/**
 * 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;

/**
 * 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;
	
	/**
	 * 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;
		while ( p != null ) {
			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 );
	}

	
	/**
	 * 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 );
		}
	}

	
	/**
	 *                M A I N   P R O G R A M 
	 *
	*/  
	static public void main( String[] args ) {
		IntBST2 tree = new IntBST2();
		
        // create a new tree by using insert()
        int[] keys = new int[] { 8, 3, 10, 1, 6, 14, 4, 7, 13 };
 
        for ( int i=0; i< keys.length; i++ ) 
        	tree.insert( keys[i] );	
        
        tree.debugVisit();
	}
}