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 ) {
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();
}
}
