# Unbalanced Binary Search Tree

Page 1 of 1

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

### #1 blackcompe

• D.I.C Lover

Reputation: 1159
• 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) {
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 {
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{
}
if(t.search( 55 ) != null){
System.out.println("found 55");
}
else{
}
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

• D.I.C Lover

Reputation: 1159
• 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.

### #3 blackcompe

• D.I.C Lover

Reputation: 1159
• 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.