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<Integer> 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<Integer> allNodes = new ArrayList<Integer>();
                addNodeToArray( root, allNodes );
                                
                // recursively reconstruct the tree
                clear();
                recursiveBalance( allNodes, 0, allNodes.size()-1 );
        }
        
        private void recursiveBalance( ArrayList<Integer> allNodes, int low, int high ) {
                if ( low <= high ) {
                        int mid = ( low + high ) / 2;
                        insert( 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 ) {
                IntBST tree = new IntBST();
                
        // 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();
        }
}