package collections;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;
public class BSTSet implements SortedTreeSet {
Node root;
private int size;
private int height;
/**
*This is a Node object.
*
*/
private static class Node {
@SuppressWarnings("unchecked")
Comparable val;
Node left; // Referenz auf ein kleineres Objekt
Node right; // Referenz auf ein groesseres Element
Node parent; // Referenz auf den Parent
/**
* Constructor of a new node object.
* @param val
* value of the node
* @param left
* left child node
* @param right
* right child node
* @param parent
* parent of the node
*/
@SuppressWarnings("unchecked")
public Node(Comparable val, Node left, Node right, Node parent) {
this.val = val;
this.left = left;
this.right = right;
this.parent = parent;
}
}
/**
* Iterator Class for BST
*
*/
@SuppressWarnings("unchecked")
private static class BSTIterator implements Iterator {
private Stack par;
private BSTIterator(Node root) {
par = new Stack();
Node next = root;
while (next != null) {
par.push(next);
next = next.left;
} // while
} // bst iterator
public boolean hasNext() {
return !par.empty();
} // has next
public Object next() {
if (par.empty()) {
throw new NoSuchElementException();
} // if
else {
Node cur = (Node) par.pop();
Node next = cur.right;
while (next != null) {
par.push(next);
next = next.left;
} // while
return cur.val;
} // else
} // next
public void remove() {
throw new UnsupportedOperationException();
} // remove
} // iterator
/**
* Start: Tree is Empty.
*/
public BSTSet() {
root = null;
}
/**
* Retuns the height of the tree.
*/
@Override
public int height() {
return height;
}
/**
* Prints the the tree inOrder.
*/
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
sb.append("[");
traverseInOrder(root, sb);
sb.append("]");
return sb.toString();
} // to string
/**
* Walk throw the tree and adds the values.
* @param t
* current Node
* @param sb
* StringBuffer object
*/
private void traverseInOrder(Node t, StringBuffer sb) {
if (t != null) {
traverseInOrder(t.left, sb);
if (sb.length() > 1)
sb.append(", ");
sb.append(t.val);
traverseInOrder(t.right, sb);
} // if
} // traverse
/**
* Adds a new node in the Tree when the key isn't alredy in the tree.
*/
@SuppressWarnings("unchecked")
@Override
public boolean add(Comparable key) {
Node x, current, parent;
parent = null;
current = root;
// Till the end of the tree.
while (current != null) {
int cmpRes = key.compareTo(current.val);
// Node is alredy in the tree => return false;
if (cmpRes == 0)
return false;
parent = current;
if (cmpRes < 0)
current = current.left;
else
current = current.right;
// if
} // while
// New node and initialize.
x = new Node(key, null, null, parent);
size++;
// Set the new node at the right position or as root.
if (parent != null) {
int cmpRes = key.compareTo(parent.val);
if (cmpRes < 0){
parent.left = x;
if(parent.right == null)
height++;
}
else{
parent.right = x;
if(parent.left == null)
height++;
}
} else{
root = x;
height++;
}
return true;
} // add
/**
* Searchs for a key in the tree.
*/
@Override
@SuppressWarnings("unchecked")
public boolean contains(Comparable key) {
Node current = root;
while (current != null) {
int cmpRes = key.compareTo(current.val);
// Node is alredy in the tree => return false;
if (cmpRes == 0)
return true;
if (cmpRes < 0)
current = current.left;
else
current = current.right;
}
return false;
} // contains
/**
* Returns the current size of the tree.
*/
@Override
public int getSize() {
return size;
}
/**
* Returns the BSTIterator for this tree;
*/
@SuppressWarnings("unchecked")
@Override
public Iterator iterator() {
return new BSTIterator(root);
}
/**
* Removes a key from the tree.
*/
@SuppressWarnings("unchecked")
@Override
public boolean remove(Comparable key) {
Node x, y, z;
z = root;
while (z != null) {
int cmpRes = key.compareTo(z.val);
if (cmpRes == 0)
break;
else if (cmpRes < 0)
z = z.left;
else
z = z.right;
} // while
// Node is not in the tree.
if (z == null)
return false;
if (z.left == null || z.right == null)
y = z;
else {
y = z.right;
while (y.left != null)
y = y.left;
}
if (y.left != null)
x = y.left;
else
x = y.right;
if (x != null)
x.parent = y.parent;
if (y.parent != null)
if (y == y.parent.left)
y.parent.left = x;
else
y.parent.right = x;
else
root = x;
if (y != z) {
y.left = z.left;
if (y.left != null)
y.left.parent = y;
// if
y.right = z.right;
if (y.right != null)
y.right.parent = y;
// if
y.parent = z.parent;
if (z.parent != null)
if (z == z.parent.left)
z.parent.left = y;
else
z.parent.right = y;
// if
else
root = y;
} // if
size--;
return true;
} // remove
} // class BST
