2 Replies - 2620 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

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 BSTAn unbalanced node-based binary search tree.
/**
 * BST.java
 * 
 * An unbalanced node-based binary search tree. On average, operations are O(log(n)).
 * Removing nodes can quickly linearize the tree so that some operations become O(n). 
 * For O(log(n)) operations in the worst case, use AVL or Red-Black Trees: {@link http://en.wikipedia.org/wiki/AVL%20tree}.
 * Inserting, removing, and searching rely on Comparable.CompareTo. 
 * 
 * @author Ryan Beckett
 * @version 1.0
 * JDK 1.7
 * 10/16/2011
 *
 */
public class BST<T extends Comparable<? super T>> {

	private Node<T>	treeRoot;

	/**
	 * Insert a value into the tree.
	 */
	public void insert(T val) {
		if(treeRoot == null) {
			treeRoot = new Node<T>(val);
		}else {
			insert(treeRoot, val);
		}
	}
	
	private void insert(Node<T> root, T val) {
		if(val.compareTo(root.val) <= 0) { 
			if(root.left == null) { //insert as left child
				root.left = new Node<T>(val);
			}else { //traverse left subtree
				insert(root.left, val);
			}
		}else if(val.compareTo(root.val) > 0) { 
			if(root.right == null) { //insert as right child
				root.right = new Node<T>(val);
			}else { //traverse right subtree
				insert(root.right, val);
			}
		}
	}
	
	private void insert(Node<T> nd) {
		if(nd == null)return;
		if(treeRoot == null) { //create tree root
			treeRoot = nd;
		}else { //insert into tree
			insert(treeRoot, nd);
		}
	}
	
	private void insert(Node<T> root, Node<T> nd) {
		if(nd.val.compareTo(root.val) <= 0) { 
			if(root.left == null) { //insert as left child
				root.left = nd;
			}else { //traverse left subtree
				insert(root.left, nd);
			}
		}else if(nd.val.compareTo(root.val) > 0) { 
			if(root.right == null) { //insert as right child
				root.right = nd;
			}else { //traverse right subtree
				insert(root.right, nd);
			}
		}
	}
	
	/**
	 * Search for a value in the tree.
	 */
	public Node<T> search(T val) {
		return search(treeRoot, val);
	}
	
	private Node<T> search( Node<T> root, T val ) {
		if(root == null)return null;
		if(val.compareTo(root.val) < 0) //traverse left subtree
			return search(root.left, val);
		else if(val.compareTo(root.val) > 0)//traverse right subtree
			return search(root.right, val);
		else //found target
			return root;
	}

	/**
	 * Perform an in-order tree traversal. Display the tree elements in ascending order.
	 */
	public void print() { 
		System.out.print("Tree: ");
		if(treeRoot == null) {
			System.out.println();
			return;
		}
		print(treeRoot);
		System.out.println();
	}
	
	private void print( Node<T> root ) { 
		if(root.left != null) //traverse left subtree first
			print( root.left );
		System.out.print( root + ", " ); //now visit the node
		if(root.right != null)
			print( root.right ); //traverse right subtree after
	}
	
	/**
	 * Remove a value from the tree and return its node.
	 */
	public Node<T> remove(T val) {
		return remove(treeRoot, treeRoot, val);	
	}
	
	private Node<T> remove(Node<T> root, Node<T> parent, T val) {
		if(root == null)return null; //end of tree; target not found
		if(val.compareTo(root.val) < 0) { //traverse left subtree
			return remove(root.left, root, val);
		}else if(val.compareTo(root.val) > 0) { //traverse right subtree
			return remove(root.right, root, val);
		}else {//found node; link root's parent to one of root's children
			adjust(root, parent);
			return root;
		}
	}
	
	/**
	 * 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) {
			if(root == treeRoot) {//We're removing the root of tree, just clear the tree.
				treeRoot = null;
			}else if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
				parent.left = null;
			}else { //it's its parent's right child
				parent.right = null;
			}
		}
		//We're removing an interior node with two children
		else if(root.right != null && root.left !=  null) { 
			Node<T> removable = root.right.left; //temporarily hold the node's right child's left subtree
			root.right.left = root.left; //make the node's left subtree the node's right child's left subtree
			if(root == treeRoot) { //We're removing the root of the tree
				treeRoot = root.right; //the node's right child becomes the tree root
			}else {
				parent.right = root.right; //replace node with its right child
			}
			insert(removable); //add the node's right child's left subtree back into the tree;
		}
		//We're removing an interior node with one child
		else { 
			if(root.left != null) { //node has left child only
				if(root == treeRoot) { //left child becomes tree root
					treeRoot = root.left;
				}else {
					if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
						parent.left = root.left; 
					}else {//it is its parent's right child
						parent.right = root.left; 
					}
				}
			}else { //node has right child only
				if(root == treeRoot) { //right child becomes tree root
					treeRoot = root.right;
				}else {
					if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
						parent.left = root.right; 
					}else {//it is its parent's right child
						parent.right = root.right; 
					}
				}
			}
		}
	}
	
	/**
	 * Clear the tree.
	 */
	public void clear() {
		treeRoot = null;
	}
	
	/* Test Driver */
	public static void main( String args[] ) {
		
		///////////////////
		//Integer example
		///////////////////
		System.out.println("---------------------nInteger list examplen---------------------");
		BST<Integer> t = new BST<Integer>();
		
		///////////////////
		//Inserting
		///////////////////
		t.insert( 5 );
		t.insert( 2 );
		t.insert( 7 );
		t.insert( 1 );
		t.insert( 5 );
		t.insert( 3 );
		t.insert( 6 );
		t.insert( 10 );
		t.insert( 3 );
		t.print();
		
		///////////////////
		//Searching
		///////////////////
		int target = 10;
		if(t.search(target) != null)
		{
			System.out.println(target+" was found");
		}else {
			System.out.println(target+" was not found");
		}
		target = 0;
		if(t.search(target) != null)
		{
			System.out.println(target+" was found");
		}else {
			System.out.println(target+" was not found");
		}
		target = 2;
		if(t.search(target) != null)
		{
			System.out.println(target+" was found");
		}else {
			System.out.println(target+" was not found");
		}
		
		///////////////////
		//Removing
		///////////////////
		System.out.println("Removing 11");
		t.remove(11);
		t.print();
		System.out.println("Removing 5");
		t.remove(5);
		t.print();
		System.out.println("Removing 1");
		t.remove(1);
		t.print();
		System.out.println("Removing 6");
		t.remove(6);
		t.print();
		System.out.println("Removing 10");
		t.remove(10);
		t.print();
		System.out.println("Removing 3");
		t.remove(3);
		t.print();
		System.out.println("Removing 3");
		t.remove(3);
		t.print();
		
		
		///////////////////
		//String example
		///////////////////
		System.out.println("n---------------------nString list examplen---------------------");
		BST<String> s = new BST<String>();
		
		///////////////////
		//Inserting
		///////////////////
		s.insert( "foo" );
		s.insert( "?>}|");
		s.insert( "bar" );
		s.insert( "qux" );
		s.insert( "baz" );
		s.insert( "?>");
		s.insert( "qux" );
		s.print();
		
		///////////////////
		//Searching
		///////////////////
		String strTarget = "?>}";
		if(s.search(strTarget) != null)
		{
			System.out.println(strTarget+" was found");
		}else {
			System.out.println(strTarget+" was not found");
		}
		strTarget = "bar";
		if(s.search(strTarget) != null)
		{
			System.out.println(strTarget+" was found");
		}else {
			System.out.println(strTarget+" was not found");
		}
		
		///////////////////
		//Removing
		///////////////////
		System.out.println("Removing bar");
		s.remove( "bar" );
		s.print();
		System.out.println("Removing baz");
		s.remove( "baz" );
		s.print();
		System.out.println("Removing qux");
		s.remove( "qux" );
		s.print();
		System.out.println("Removing ?>}|");
		s.remove( "?>}|" );
		s.print();
		System.out.println("Removing ?>}|");
		s.remove( "?>}|" );
		s.print();
	}
}

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



Is This A Good Question/Topic? 0
  • +

Replies To: 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: 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 BSTAn unbalanced node-based binary search tree.
/**
 * BST.java
 * 
 * An unbalanced node-based binary search tree. On average, operations are O(log(n)).
 * Removing nodes can quickly linearize the tree so that some operations become O(n). 
 * For O(log(n)) operations in the worst case, use AVL or Red-Black Trees: {@link http://en.wikipedia.org/wiki/AVL%20tree}.
 * Inserting, removing, and searching rely on Comparable.CompareTo. 
 * 
 * @author Ryan Beckett
 * @version 1.0
 * JDK 1.7
 * 10/16/2011
 *
 */
public class BST<T extends Comparable<? super T>> {

	private Node<T>	treeRoot;

	/**
	 * Insert a value into the tree.
	 */
	public void insert(T val) {
		if(treeRoot == null) {
			treeRoot = new Node<T>(val);
		}else {
			insert(treeRoot, val);
		}
	}
	
	private void insert(Node<T> root, T val) {
		if(val.compareTo(root.val) <= 0) { 
			if(root.left == null) { //insert as left child
				root.left = new Node<T>(val);
			}else { //traverse left subtree
				insert(root.left, val);
			}
		}else if(val.compareTo(root.val) > 0) { 
			if(root.right == null) { //insert as right child
				root.right = new Node<T>(val);
			}else { //traverse right subtree
				insert(root.right, val);
			}
		}
	}
	
	private void insert(Node<T> nd) {
		if(nd == null)return;
		if(treeRoot == null) { //create tree root
			treeRoot = nd;
		}else { //insert into tree
			insert(treeRoot, nd);
		}
	}
	
	private void insert(Node<T> root, Node<T> nd) {
		if(nd.val.compareTo(root.val) <= 0) { 
			if(root.left == null) { //insert as left child
				root.left = nd;
			}else { //traverse left subtree
				insert(root.left, nd);
			}
		}else if(nd.val.compareTo(root.val) > 0) { 
			if(root.right == null) { //insert as right child
				root.right = nd;
			}else { //traverse right subtree
				insert(root.right, nd);
			}
		}
	}
	
	/**
	 * Search for a value in the tree.
	 */
	public Node<T> search(T val) {
		return search(treeRoot, val);
	}
	
	private Node<T> search( Node<T> root, T val ) {
		if(root == null)return null;
		if(val.compareTo(root.val) < 0) //traverse left subtree
			return search(root.left, val);
		else if(val.compareTo(root.val) > 0)//traverse right subtree
			return search(root.right, val);
		else //found target
			return root;
	}

	/**
	 * Perform an in-order tree traversal. Display the tree elements in ascending order.
	 */
	public void print() { 
		System.out.print("Tree: ");
		if(treeRoot == null) {
			System.out.println();
			return;
		}
		print(treeRoot);
		System.out.println();
	}
	
	private void print( Node<T> root ) { 
		if(root.left != null) //traverse left subtree first
			print( root.left );
		System.out.print( root + ", " ); //now visit the node
		if(root.right != null)
			print( root.right ); //traverse right subtree after
	}
	
	/**
	 * Remove a value from the tree and return its node.
	 */
	public Node<T> remove(T val) {
		return remove(treeRoot, treeRoot, val);	
	}
	
	private Node<T> remove(Node<T> root, Node<T> parent, T val) {
		if(root == null)return null; //end of tree; target not found
		if(val.compareTo(root.val) < 0) { //traverse left subtree
			return remove(root.left, root, val);
		}else if(val.compareTo(root.val) > 0) { //traverse right subtree
			return remove(root.right, root, val);
		}else {//found node; link root's parent to one of root's children
			adjust(root, parent);
			return root;
		}
	}
	
	/**
	 * 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) {
			if(root == treeRoot) {//We're removing the root of tree, just clear the tree.
				treeRoot = null;
			}else if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
				parent.left = null;
			}else { //it's its parent's right child
				parent.right = null;
			}
		}
		//We're removing an interior node with two children
		else if(root.right != null && root.left !=  null) { 
			Node<T> removable = root.right.left; //temporarily hold the node's right child's left subtree
			root.right.left = root.left; //make the node's left subtree the node's right child's left subtree
			if(root == treeRoot) { //We're removing the root of the tree
				treeRoot = root.right; //the node's right child becomes the tree root
			}else {
				parent.right = root.right; //replace node with its right child
			}
			insert(removable); //add the node's right child's left subtree back into the tree;
		}
		//We're removing an interior node with one child
		else { 
			if(root.left != null) { //node has left child only
				if(root == treeRoot) { //left child becomes tree root
					treeRoot = root.left;
				}else {
					if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
						parent.left = root.left; 
					}else {//it is its parent's right child
						parent.right = root.left; 
					}
				}
			}else { //node has right child only
				if(root == treeRoot) { //right child becomes tree root
					treeRoot = root.right;
				}else {
					if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
						parent.left = root.right; 
					}else {//it is its parent's right child
						parent.right = root.right; 
					}
				}
			}
		}
	}
	
	/**
	 * Clear the tree.
	 */
	public void clear() {
		treeRoot = null;
	}
	
	private 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();
		}
	}
	
	/* Test Driver */
	public static void main( String args[] ) {
		
		///////////////////
		//Integer example
		///////////////////
		System.out.println("---------------------nInteger list examplen---------------------");
		BST<Integer> t = new BST<Integer>();
		
		///////////////////
		//Inserting
		///////////////////
		t.insert( 5 );
		t.insert( 2 );
		t.insert( 7 );
		t.insert( 1 );
		t.insert( 5 );
		t.insert( 3 );
		t.insert( 6 );
		t.insert( 10 );
		t.insert( 3 );
		t.print();
		
		///////////////////
		//Searching
		///////////////////
		int target = 10;
		if(t.search(target) != null)
		{
			System.out.println(target+" was found");
		}else {
			System.out.println(target+" was not found");
		}
		target = 0;
		if(t.search(target) != null)
		{
			System.out.println(target+" was found");
		}else {
			System.out.println(target+" was not found");
		}
		target = 2;
		if(t.search(target) != null)
		{
			System.out.println(target+" was found");
		}else {
			System.out.println(target+" was not found");
		}
		
		///////////////////
		//Removing
		///////////////////
		System.out.println("Removing 11");
		t.remove(11);
		t.print();
		System.out.println("Removing 5");
		t.remove(5);
		t.print();
		System.out.println("Removing 1");
		t.remove(1);
		t.print();
		System.out.println("Removing 6");
		t.remove(6);
		t.print();
		System.out.println("Removing 10");
		t.remove(10);
		t.print();
		System.out.println("Removing 3");
		t.remove(3);
		t.print();
		System.out.println("Removing 3");
		t.remove(3);
		t.print();
		
		
		///////////////////
		//String example
		///////////////////
		System.out.println("n---------------------nString list examplen---------------------");
		BST<String> s = new BST<String>();
		
		///////////////////
		//Inserting
		///////////////////
		s.insert( "foo" );
		s.insert( "?>}|");
		s.insert( "bar" );
		s.insert( "qux" );
		s.insert( "baz" );
		s.insert( "?>");
		s.insert( "qux" );
		s.print();
		
		///////////////////
		//Searching
		///////////////////
		String strTarget = "?>}";
		if(s.search(strTarget) != null)
		{
			System.out.println(strTarget+" was found");
		}else {
			System.out.println(strTarget+" was not found");
		}
		strTarget = "bar";
		if(s.search(strTarget) != null)
		{
			System.out.println(strTarget+" was found");
		}else {
			System.out.println(strTarget+" was not found");
		}
		
		///////////////////
		//Removing
		///////////////////
		System.out.println("Removing bar");
		s.remove( "bar" );
		s.print();
		System.out.println("Removing baz");
		s.remove( "baz" );
		s.print();
		System.out.println("Removing qux");
		s.remove( "qux" );
		s.print();
		System.out.println("Removing ?>}|");
		s.remove( "?>}|" );
		s.print();
		System.out.println("Removing ?>}|");
		s.remove( "?>}|" );
		s.print();
	}
}


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: 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 BSTAn unbalanced node-based binary search tree.
/**
 * BST.java
 * 
 * An unbalanced node-based binary search tree. On average, operations are O(log(n)).
 * Removing nodes can quickly linearize the tree so that some operations become O(n). 
 * For O(log(n)) operations in the worst case, use AVL or Red-Black Trees: {@link http://en.wikipedia.org/wiki/AVL%20tree}.
 * Inserting, removing, and searching rely on Comparable.CompareTo. 
 * 
 * @author Ryan Beckett
 * @version 1.0
 * JDK 1.7
 * 10/16/2011
 *
 */
public class BST<T extends Comparable<? super T>> {

	private Node<T>	treeRoot;

	/**
	 * Insert a value into the tree.
	 */
	public void insert(T val) {
		if(treeRoot == null) {
			treeRoot = new Node<T>(val);
		}else {
			insert(treeRoot, val);
		}
	}
	
	private void insert(Node<T> root, T val) {
		if(val.compareTo(root.val) <= 0) { 
			if(root.left == null) { //insert as left child
				root.left = new Node<T>(val);
			}else { //traverse left subtree
				insert(root.left, val);
			}
		}else if(val.compareTo(root.val) > 0) { 
			if(root.right == null) { //insert as right child
				root.right = new Node<T>(val);
			}else { //traverse right subtree
				insert(root.right, val);
			}
		}
	}
	
	private void insert(Node<T> nd) {
		if(nd == null)return;
		if(treeRoot == null) { //create tree root
			treeRoot = nd;
		}else { //insert into tree
			insert(treeRoot, nd);
		}
	}
	
	private void insert(Node<T> root, Node<T> nd) {
		if(nd.val.compareTo(root.val) <= 0) { 
			if(root.left == null) { //insert as left child
				root.left = nd;
			}else { //traverse left subtree
				insert(root.left, nd);
			}
		}else if(nd.val.compareTo(root.val) > 0) { 
			if(root.right == null) { //insert as right child
				root.right = nd;
			}else { //traverse right subtree
				insert(root.right, nd);
			}
		}
	}
	
	/**
	 * Search for a value in the tree.
	 */
	public T search(T val) {
		Node<T> res = search(treeRoot, val);
		if(res == null)return null;
		else return res.val;
	}
	
	private Node<T> search( Node<T> root, T val ) {
		if(root == null)return null;
		if(val.compareTo(root.val) < 0) //traverse left subtree
			return search(root.left, val);
		else if(val.compareTo(root.val) > 0)//traverse right subtree
			return search(root.right, val);
		else //found target
			return root;
	}

	/**
	 * Perform an in-order tree traversal. Display the tree elements in ascending order.
	 */
	public void print() { 
		System.out.print("Tree: ");
		if(treeRoot == null) {
			System.out.println();
			return;
		}
		print(treeRoot);
		System.out.println();
	}
	
	private void print( Node<T> root ) { 
		if(root.left != null) //traverse left subtree first
			print( root.left );
		System.out.print( root + ", " ); //now visit the node
		if(root.right != null)
			print( root.right ); //traverse right subtree after
	}
	
	/**
	 * Remove a value from the tree and return its node.
	 */
	public T remove(T val) {
		Node<T> res = remove(treeRoot, treeRoot, val);
		if(res == null)return null;
		else return res.val;
	}
	
	private Node<T> remove(Node<T> root, Node<T> parent, T val) {
		if(root == null)return null; //end of tree; target not found
		if(val.compareTo(root.val) < 0) { //traverse left subtree
			return remove(root.left, root, val);
		}else if(val.compareTo(root.val) > 0) { //traverse right subtree
			return remove(root.right, root, val);
		}else {//found node; link root's parent to one of root's children
			adjust(root, parent);
			return root;
		}
	}
	
	/**
	 * 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) {
			if(root == treeRoot) {//We're removing the root of tree, just clear the tree.
				treeRoot = null;
			}else if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
				parent.left = null;
			}else { //it's its parent's right child
				parent.right = null;
			}
		}
		//We're removing an interior node with two children
		else if(root.right != null && root.left !=  null) { 
			Node<T> removable = root.right.left; //temporarily hold the node's right child's left subtree
			root.right.left = root.left; //make the node's left subtree the node's right child's left subtree
			if(root == treeRoot) { //We're removing the root of the tree
				treeRoot = root.right; //the node's right child becomes the tree root
			}else {
				parent.right = root.right; //replace node with its right child
			}
			insert(removable); //add the node's right child's left subtree back into the tree;
		}
		//We're removing an interior node with one child
		else { 
			if(root.left != null) { //node has left child only
				if(root == treeRoot) { //left child becomes tree root
					treeRoot = root.left;
				}else {
					if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
						parent.left = root.left; 
					}else {//it is its parent's right child
						parent.right = root.left; 
					}
				}
			}else { //node has right child only
				if(root == treeRoot) { //right child becomes tree root
					treeRoot = root.right;
				}else {
					if(root.val.compareTo(parent.val) <= 0) { //it is its parent's left child
						parent.left = root.right; 
					}else {//it is its parent's right child
						parent.right = root.right; 
					}
				}
			}
		}
	}
	
	/**
	 * Clear the tree.
	 */
	public void clear() {
		treeRoot = null;
	}
	
	private 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();
		}
	}
	
	/* Test Driver */
	public static void main( String args[] ) {
		
		///////////////////
		//Integer example
		///////////////////
		System.out.println("---------------------nInteger list examplen---------------------");
		BST<Integer> t = new BST<Integer>();
		
		///////////////////
		//Inserting
		///////////////////
		t.insert( 5 );
		t.insert( 2 );
		t.insert( 7 );
		t.insert( 1 );
		t.insert( 5 );
		t.insert( 3 );
		t.insert( 6 );
		t.insert( 10 );
		t.insert( 3 );
		t.print();
		
		///////////////////
		//Searching
		///////////////////
		int target = 10;
		if(t.search(target) != null)
		{
			System.out.println(target+" was found");
		}else {
			System.out.println(target+" was not found");
		}
		target = 0;
		if(t.search(target) != null)
		{
			System.out.println(target+" was found");
		}else {
			System.out.println(target+" was not found");
		}
		target = 2;
		if(t.search(target) != null)
		{
			System.out.println(target+" was found");
		}else {
			System.out.println(target+" was not found");
		}
		
		///////////////////
		//Removing
		///////////////////
		System.out.println("Removing 11");
		t.remove(11);
		t.print();
		System.out.println("Removing 5");
		t.remove(5);
		t.print();
		System.out.println("Removing 1");
		t.remove(1);
		t.print();
		System.out.println("Removing 6");
		t.remove(6);
		t.print();
		System.out.println("Removing 10");
		t.remove(10);
		t.print();
		System.out.println("Removing 3");
		t.remove(3);
		t.print();
		System.out.println("Removing 3");
		t.remove(3);
		t.print();
		
		
		///////////////////
		//String example
		///////////////////
		System.out.println("n---------------------nString list examplen---------------------");
		BST<String> s = new BST<String>();
		
		///////////////////
		//Inserting
		///////////////////
		s.insert( "foo" );
		s.insert( "?>}|");
		s.insert( "bar" );
		s.insert( "qux" );
		s.insert( "baz" );
		s.insert( "?>");
		s.insert( "qux" );
		s.print();
		
		///////////////////
		//Searching
		///////////////////
		String strTarget = "?>}";
		if(s.search(strTarget) != null)
		{
			System.out.println(strTarget+" was found");
		}else {
			System.out.println(strTarget+" was not found");
		}
		strTarget = "bar";
		if(s.search(strTarget) != null)
		{
			System.out.println(strTarget+" was found");
		}else {
			System.out.println(strTarget+" was not found");
		}
		
		///////////////////
		//Removing
		///////////////////
		System.out.println("Removing bar");
		s.remove( "bar" );
		s.print();
		System.out.println("Removing baz");
		s.remove( "baz" );
		s.print();
		System.out.println("Removing qux");
		s.remove( "qux" );
		s.print();
		System.out.println("Removing ?>}|");
		s.remove( "?>}|" );
		s.print();
		System.out.println("Removing ?>}|");
		s.remove( "?>}|" );
		s.print();
	}
}


Was This Post Helpful? 0
  • +
  • -

#4 blackcompe   User is offline

  • D.I.C Lover
  • member icon

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

Re: 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 BSTAn unbalanced node-based binary search tree.
/**
 * <p>
 * An unbalanced node-based binary search tree. On average, operations are done
 * in logarithmic time. Removing nodes can quickly linearize the tree so that
 * some operations are done in linear time. For logarithmic runtime across all
 * operations in the worst case, use AVL or Red-Black Trees. Inserting,
 * removing, and searching rely on {@link Comparable#compareTo(Object) Comparable.compareTo}. The tree
 * discards null values.
 * </p>
 * 
 * @author Ryan Beckett
 * @version 1.0
 * 
 */
public class BST<T extends Comparable<? super T>> {

    private Node<T> treeRoot;

    /**
     * Insert a value into the tree.
     * 
     * @param val
     *            The value to be inserted in the tree.
     */
    public void insert(T val) {
        if (val == null)
            return;
        else if (treeRoot == null) // create tree root
            treeRoot = new Node<T>(val);
        else
            // insert into the tree
            insert(treeRoot, val);
    }

    private void insert(Node<T> root, T val) {
        if (val.compareTo(root.val) <= 0) {
            if (root.left == null) { // insert as left child
                root.left = new Node<T>(val);
            } else { // traverse left subtree
                insert(root.left, val);
            }
        } else if (val.compareTo(root.val) > 0) {
            if (root.right == null) { // insert as right child
                root.right = new Node<T>(val);
            } else { // traverse right subtree
                insert(root.right, val);
            }
        }
    }

    private void insert(Node<T> nd) {
        if (nd == null)
            return;
        if (treeRoot == null) // create tree root
            treeRoot = nd;
        else
            // insert into the tree
            insert(treeRoot, nd);
    }

    private void insert(Node<T> root, Node<T> nd) {
        if (nd.val.compareTo(root.val) <= 0) {
            if (root.left == null) { // insert as left child
                root.left = nd;
            } else { // traverse left subtree
                insert(root.left, nd);
            }
        } else if (nd.val.compareTo(root.val) > 0) {
            if (root.right == null) { // insert as right child
                root.right = nd;
            } else { // traverse right subtree
                insert(root.right, nd);
            }
        }
    }

    /**
     * Search for a value in the tree.
     * 
     * @param val
     *            The value to be searched for in the tree.
     */
    public T search(T val) {
        if (val == null)
            return null;
        Node<T> res = search(treeRoot, val);
        if (res == null)
            return null;
        else
            return res.val;
    }

    private Node<T> search(Node<T> root, T val) {
        if (root == null)
            return null;
        if (val.compareTo(root.val) < 0) // traverse left subtree
            return search(root.left, val);
        else if (val.compareTo(root.val) > 0)// traverse right subtree
            return search(root.right, val);
        else
            // found target
            return root;
    }

    /**
     * Perform an in-order tree traversal. Display the tree elements in
     * ascending order.
     */
    public void print() {
        System.out.print("Tree: ");
        if (treeRoot == null) {
            System.out.println();
            return;
        }
        print(treeRoot);
        System.out.println();
    }

    private void print(Node<T> root) {
        if (root.left != null) // traverse left subtree first
            print(root.left);
        System.out.print(root + ", "); // now visit the node
        if (root.right != null)
            print(root.right); // traverse right subtree after
    }

    /**
     * Remove a value from the tree and return it.
     * 
     * @param val
     *            The value to be removed from the tree.
     */
    public T remove(T val) {
        if (val == null)
            return null;
        Node<T> res = remove(treeRoot, treeRoot, val);
        if (res == null)
            return null;
        else
            return res.val;
    }

    private Node<T> remove(Node<T> root, Node<T> parent, T val) {
        if (root == null)
            return null; // end of tree; target not found
        if (val.compareTo(root.val) < 0) { // traverse left subtree
            return remove(root.left, root, val);
        } else if (val.compareTo(root.val) > 0) { // traverse right subtree
            return remove(root.right, root, val);
        } else {// found node; link root's parent to one of root's children
            adjust(root, parent);
            return root;
        }
    }

    /**
     * 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) {
            if (root == treeRoot) {// We're removing the root of tree, just
                                   // clear the tree.
                treeRoot = null;
            } else if (root.val.compareTo(parent.val) <= 0) { // it is its
                                                              // parent's left
                                                              // child
                parent.left = null;
            } else { // it's its parent's right child
                parent.right = null;
            }
        }
        // We're removing an interior node with two children
        else if (root.right != null && root.left != null) {
            Node<T> removable = root.right.left; // temporarily hold the node's
                                                 // right child's left subtree
            root.right.left = root.left; // make the node's left subtree the
                                         // node's right child's left subtree
            if (root == treeRoot) { // We're removing the root of the tree
                treeRoot = root.right; // the node's right child becomes the
                                       // tree root
            } else {
                parent.right = root.right; // replace node with its right child
            }
            insert(removable); // add the node's right child's left subtree back
                               // into the tree;
        }
        // We're removing an interior node with one child
        else {
            if (root.left != null) { // node has left child only
                if (root == treeRoot) { // left child becomes tree root
                    treeRoot = root.left;
                } else {
                    if (root.val.compareTo(parent.val) <= 0) { // it is its
                                                               // parent's left
                                                               // child
                        parent.left = root.left;
                    } else {// it is its parent's right child
                        parent.right = root.left;
                    }
                }
            } else { // node has right child only
                if (root == treeRoot) { // right child becomes tree root
                    treeRoot = root.right;
                } else {
                    if (root.val.compareTo(parent.val) <= 0) { // it is its
                                                               // parent's left
                                                               // child
                        parent.left = root.right;
                    } else {// it is its parent's right child
                        parent.right = root.right;
                    }
                }
            }
        }
    }

    /**
     * Clear the tree.
     */
    public void clear() {
        treeRoot = null;
    }

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

class BSTTest {

    /* Test Driver */
    public static void main(String args[]) {

        // /////////////////
        // Integer example
        // /////////////////
        System.out
                .println("---------------------nInteger list examplen---------------------");
        BST<Integer> t = new BST<Integer>();

        // /////////////////
        // Inserting
        // /////////////////
        t.insert(5);
        t.insert(2);
        t.insert(7);
        t.insert(1);
        t.insert(5);
        t.insert(3);
        t.insert(6);
        t.insert(10);
        t.insert(3);
        t.print();

        // /////////////////
        // Searching
        // /////////////////
        int target = 10;
        if (t.search(target) != null) {
            System.out.println(target + " was found");
        } else {
            System.out.println(target + " was not found");
        }
        target = 0;
        if (t.search(target) != null) {
            System.out.println(target + " was found");
        } else {
            System.out.println(target + " was not found");
        }
        target = 2;
        if (t.search(target) != null) {
            System.out.println(target + " was found");
        } else {
            System.out.println(target + " was not found");
        }

        // /////////////////
        // Removing
        // /////////////////
        System.out.println("Removing 11");
        t.remove(11);
        t.print();
        System.out.println("Removing 5");
        t.remove(5);
        t.print();
        System.out.println("Removing 1");
        t.remove(1);
        t.print();
        System.out.println("Removing 6");
        t.remove(6);
        t.print();
        System.out.println("Removing 10");
        t.remove(10);
        t.print();
        System.out.println("Removing 3");
        t.remove(3);
        t.print();
        System.out.println("Removing 3");
        t.remove(3);
        t.print();

        // /////////////////
        // String example
        // /////////////////
        System.out
                .println("n---------------------nString list examplen---------------------");
        BST<String> s = new BST<String>();

        // /////////////////
        // Inserting
        // /////////////////
        s.insert("foo");
        s.insert("?>}|");
        s.insert("bar");
        s.insert("qux");
        s.insert("baz");
        s.insert("?>");
        s.insert("qux");
        s.print();

        // /////////////////
        // Searching
        // /////////////////
        String strTarget = "?>}";
        if (s.search(strTarget) != null) {
            System.out.println(strTarget + " was found");
        } else {
            System.out.println(strTarget + " was not found");
        }
        strTarget = "bar";
        if (s.search(strTarget) != null) {
            System.out.println(strTarget + " was found");
        } else {
            System.out.println(strTarget + " was not found");
        }

        // /////////////////
        // Removing
        // /////////////////
        System.out.println("Removing bar");
        s.remove("bar");
        s.print();
        System.out.println("Removing baz");
        s.remove("baz");
        s.print();
        System.out.println("Removing qux");
        s.remove("qux");
        s.print();
        System.out.println("Removing ?>}|");
        s.remove("?>}|");
        s.print();
        System.out.println("Removing ?>}|");
        s.remove("?>}|");
        s.print();
    }
}


Was This Post Helpful? 0
  • +
  • -

#5 blackcompe   User is offline

  • D.I.C Lover
  • member icon

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

Re: 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
  • +
  • -

#6 blackcompe   User is offline

  • D.I.C Lover
  • member icon

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

Re: 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