2 Replies - 2401 Views - Last Post: 01 November 2011 - 04:22 PM

#1 blackcompe   User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • Posts: 2,547
  • Joined: 05-May 05

Unbalanced Binary Search Tree

Posted 10 August 2011 - 04:14 PM

Description: To run, change into the directory where BST.java is located and type:

javac BST.java
java BSTBST.java represents an unbalanced node-based binary tree.
/**
 * BST represents an unbalanced node-based binary tree. All operations are O(log(n)).
 * Removing interior nodes can linearize the tree structure so that tree operations become O(n). 
 * To ensure O(log(n)) searches, use AVL or Red-Black Trees.
 * Inserting, removing, and searching rely on Comparable.CompareTo. Note that the tree will not store two nodes
 * with the same value. The original will be kept. 
 * @author Ryan Beckett
 * 
 */
public class BST<T extends Comparable<? super T>> {

	private Node<T>	treeRoot;

	/**
	 * Insert a value into the tree.
	 */
	public void insert(T val) {
		if(val == null)return;
		if(treeRoot == null) { //create tree root
			treeRoot = new Node<T>(val);
		}else { //insert into tree
			insert(treeRoot, val);
		}
	}
	
	/**
	 * insert(treeRoot, val)
	 */
	private void insert(Node<T> root, T val) {
		if(val.compareTo(root.val) < 0) { 
			//insert as left child
			if(root.left == null) { 
				root.left = new Node<T>(val);
			}//traverse left subtree
			else { 
				insert(root.left, val);
			}
		}else if(val.compareTo(root.val) > 0) { 
			//insert as right child
			if(root.right == null) { 
				root.right = new Node<T>(val);
			}//traverse right subtree
			else { 
				insert(root.right, val);
			}
		}
	}
	
	/**
	 * Insert a node into the tree.
	 */
	private void insert(Node<T> nd) {
		if(nd == null)return;
		//create tree root
		if(treeRoot == null) { 
			treeRoot = nd;
		}//insert into tree
		else { 
			insert(treeRoot, nd);
		}
	}
	
	/**
	 * insert(treeRoot, nd)
	 */
	private void insert(Node<T> root, Node<T> nd) {
		if(nd.val.compareTo(root.val) < 0) { 
			//insert as left child
			if(root.left == null) { 
				root.left = nd;
			}//traverse left subtree
			else { 
				insert(root.left, nd);
			}
		}else if(nd.val.compareTo(root.val) > 0) { 
			//insert as right child
			if(root.right == null) { 
				root.right = nd;
			}//traverse right subtree
			else { 
				insert(root.right, nd);
			}
		}
	}
	
	/**
	 * Search for a value in the tree.
	 */
	public T search(T val) {
		if(val == null)return null;
		return search(treeRoot, val);
	}
	
	/**
	 * search(treeRoot, val)
	 */
	private T search( Node<T> root, T val ) {
		if(root == null)return null;
		//traverse left subtree
		if(val.compareTo(root.val) < 0) {
			return search(root.left, val);
		}//traverse right subtree
		else if(val.compareTo(root.val) > 0) {
			return search(root.right, val);
		}//found target
		else 
			return root.val;
	}
	
	/**
	 * Remove a value from the tree.
	 */
	public T remove(T val) {
		if(val == null)return null;
		return remove(treeRoot, treeRoot, val);	
	}
	
	/**
	 * remove(treeRoot, treeRoot, val)
	 */
	private T remove(Node<T> root, Node<T> parent, T val) {
		//end of tree; target not found
		if(root == null)return null; 
		//traverse left subtree
		if(val.compareTo(root.val) < 0) { 
			return remove(root.left, root, val);
		}//traverse right subtree
		else if(val.compareTo(root.val) > 0) { 
			return remove(root.right, root, val);
		}//found node; link root's parent to one of root's children
		else {
			adjust(root, parent);
			return root.val;
		}
	}
	
	/**
	 * Remove node by letting one of its children take its place. 
	 */
	private void adjust(Node<T> root, Node<T> parent) {
		//We're removing a leaf
		if(root.left == null && root.right == null) {
			//We're removing the root of tree, just clear the tree.
			if(root == treeRoot) {
				treeRoot = null;
			}//it's its parent's left child
			else if(root.val.compareTo(parent.val) < 0) { 
				parent.left = null;
			}//it's its parent's right child
			else {
				parent.right = null;
			}
		}
		//We're removing an interior node with two children
		else if(root.right != null && root.left !=  null) { 
			//We're removing the root of the tree
			if(root == treeRoot) { 
				//temporarily hold the root's right child's left subtree
				Node<T> removable = root.right.left;
				//make the tree's left subtree the root's right child's left subtree
				root.right.left = root.left;
				//the root's right child becomes the root
				treeRoot = root.right;
				//add right child's left subtree back into the tree;
				insert(removable); 
			}else{
				//temporarily hold the node's right child's left subtree
				Node<T> removable = root.right.left;
				//make the node's left subtree the node's right child's left subtree
				root.right.left = root.left; 
				//the node's right child becomes the parent's left subtree
				if(root.right.val.compareTo( parent.val ) < 0) { 
					parent.left = root.right;
				}//the node's right child becomes the parent's right subtree
				else { 
					parent.right = root.right;
				}
				//add right child's left subtree back into the tree;
				insert(removable); 
			}
		}//We're removing an interior node with one child
		else { 
			//node has left child only
			if(root.left != null) { 
				//left child becomes tree root
				if(root == treeRoot) { 
					treeRoot = root.left;
				}//let left child take its place
				else {
					parent.left = root.left; 
				}
			}//node has right child only
			else { 
				//right child becomes tree root
				if(root == treeRoot) { 
					treeRoot = root.right;
				}//let right child take its place
				else {
					parent.right = root.right; 
				}
			}
		}
	}
	
	/**
	 * Clear the tree.
	 */
	public void clear() {
		treeRoot = null;
	}
	
	/**
	 * Display the tree elements in ascending order.
	 */
	public String toString() { 
		StringBuilder sb = new StringBuilder();
		sb.append( "[" );
		//we have an empty tree
		if(treeRoot == null) { 
			sb.append( "]" );
			return sb.toString();
		}
		//perform in-order traversal
		toString(treeRoot, sb); 
		//delete extra whitespace and commas
		sb.deleteCharAt( sb.length()-1 ); 
		sb.deleteCharAt( sb.length()-1 ); 
		sb.deleteCharAt( sb.length()-1 );
		sb.append( "]" );
		return sb.toString();
	}
	
	private void toString( Node<T> root, StringBuilder sb ) { 
		//traverse left subtree first
		if(root.left != null) 
			toString( root.left, sb );
		//now visit the node
		sb.append( root + " , " ); 
		//traverse right subtree after
		if(root.right != null)
			toString( root.right, sb ); 
	}
	
	public class Node<T extends Comparable<? super T>> {

		T	val;
		Node<T>	left, right;

		Node( T val ) {
			this.val = val;
		}
		
		public String toString() {
			return val.toString();
		}
	}

	public static void main( String args[] ) {

		BST<Integer> t = new BST<Integer>();
		t.insert( 5 );
		t.insert( 2 );
		t.insert( 7 );
		t.insert( 1 );
		System.out.println(t);
	
		
		///////////////////
		//Tree operations
		///////////////////
		if(t.search( 5 ) != null){
			System.out.println("found 5");
		}
		else{
			System.out.println("5 not found");
		}
		if(t.search( 55 ) != null){
			System.out.println("found 55");
		}
		else{
			System.out.println("55 not found");
		}
		System.out.println("removing 7"); 
		t.remove( 7 ); 
		System.out.println(t);
		System.out.println("removing 2"); 
		t.remove( 2 ); 
		System.out.println(t);
		System.out.println("removing 1"); 
		t.remove( 1 ); 
		System.out.println(t);
		System.out.println("removing 55"); 
		t.remove( 55 ); 
		System.out.println(t);
		System.out.println("removing 5"); 
		t.remove( 5 ); 
		System.out.println(t);
		System.out.println("removing 6"); 
		t.remove( 6 ); 
		System.out.println(t);
		
	}
	
}


Is This A Good Question/Topic? 0
  • +

Replies To: Unbalanced Binary Search Tree

#2 blackcompe   User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • Posts: 2,547
  • Joined: 05-May 05

Re: Unbalanced Binary Search Tree

Posted 16 October 2011 - 03:03 AM

Changes on 10/16/2011: Fixed a bug in BST.adjust(). Allows duplicate data.
Was This Post Helpful? 0
  • +
  • -

#3 blackcompe   User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • Posts: 2,547
  • Joined: 05-May 05

Re: Unbalanced Binary Search Tree

Posted 01 November 2011 - 04:22 PM

Changes on 11/1/2011: BST.search(T val) and BST.remove(T val) return an instance of T instead of Node, which is private to BST.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1