Skip to content

Instantly share code, notes, and snippets.

@xnnyygn
Created November 26, 2013 06:23
Show Gist options
  • Save xnnyygn/7654194 to your computer and use it in GitHub Desktop.
Save xnnyygn/7654194 to your computer and use it in GitHub Desktop.
binary search tree in java
import java.util.Iterator;
import java.util.LinkedList;
public class BinarySearchTree<T extends Comparable<T>> implements Iterable<T> {
// tree node
class Node {
T value;
Node leftChild;
Node rightChild;
// assumption: left < value < right
Node(T value) {
this.value = value;
}
}
// position of child, for remove
enum ChildPostion {
ROOT, // current node is root
LEFT, // current node is left child of parent node
RIGHT; // current node is right child of parent node
}
private Node root;
/**
* Test if element in tree.
*
* @param x element
* @return true if contains, otherwise false
*/
public boolean contains(T x) {
return contains(x, root);
}
private boolean contains(T x, Node node) {
if (node == null) return false;
int relation = x.compareTo(node.value);
if (relation == 0 /* equal */) return true;
if (relation < 0 /* less than */) return contains(x, node.leftChild);
return contains(x, node.rightChild);
}
/**
* Insert multiple elements.
*
* @param xs elements
*/
public void insert(T... xs) {
for (T x : xs) {
insert(x);
}
}
/**
* Insert element into tree.
*
* @param x element to insert
*/
public void insert(T x) {
if (root == null)
root = new Node(x);
else
insert(x, root);
}
private void insert(T x, Node node) {
int relation = x.compareTo(node.value);
if (relation == 0 /* equal */)
throw new IllegalArgumentException("duplicated element [" + x + "]");
if (relation < 0 /* less than */) {
if (node.leftChild == null) {
node.leftChild = new Node(x);
} else {
insert(x, node.leftChild);
}
} else {
// greater than
if (node.rightChild == null) {
node.rightChild = new Node(x);
} else {
insert(x, node.rightChild);
}
}
}
/**
* Insert element into tree.
*
* @param x element to insert
*/
public void insert2(T x) {
root = insert2(x, root);
}
private Node insert2(T x, Node node) {
if (node == null) return new Node(x);
int relation = x.compareTo(node.value);
if (relation == 0 /* equal */)
throw new IllegalArgumentException("duplicated element [" + x + "]");
if (relation < 0 /* less than */) {
node.leftChild = insert2(x, node.leftChild);
} else {
// greater than
node.rightChild = insert2(x, node.rightChild);
}
// no node created, just return node itself
return node;
}
/**
* Remove element.
*
* @param x element to remove
*/
public void remove(T x) {
if (root == null) throw new IllegalStateException("empty tree");
remove(x, root, null, ChildPostion.ROOT);
}
private void remove(T x, Node node, Node parent, ChildPostion position) {
if (node == null) return; // no such element, do nothing
int relation = x.compareTo(node.value);
if (relation < 0 /* less than */) {
remove(x, node.leftChild, node, ChildPostion.LEFT);
} else if (relation > 0 /* greater than */) {
remove(x, node.rightChild, node, ChildPostion.RIGHT);
} else {
// current one is the node contains the element to be removed
remove(node, parent, position);
}
}
private void remove(Node node, Node parent, ChildPostion position) {
if (node.leftChild == null) {
if (node.rightChild == null) {
// case 1: no child, just remove node itself
connectNode(parent, position, null);
} else {
// case 2: only right child presents
// connect parent to right child
connectNode(parent, position, node.rightChild);
}
} else {
// left child presents
if (node.rightChild == null) {
// case 2: only left child presents
// connect parent to left child
connectNode(parent, position, node.leftChild);
} else {
// case 3: left and right child both present
// find in-order successor
// node contains minimum value in right child tree
Node min = node.rightChild;
Node minParent = node;
while (min.leftChild != null) {
minParent = min;
min = min.leftChild;
}
// replace value
node.value = min.value;
// remove in-order successor
ChildPostion minPosition =
minParent == node ? ChildPostion.RIGHT : ChildPostion.LEFT;
remove(min, minParent, minPosition);
}
}
}
private void connectNode(Node parent, ChildPostion position, Node newChild) {
switch (position) {
case ROOT:
root = newChild;
break;
case LEFT:
parent.leftChild = newChild;
break;
case RIGHT:
parent.rightChild = newChild;
break;
default:
throw new IllegalArgumentException("unexpected child position ["
+ position + "]");
}
}
public Iterator<T> iterator() {
return inorderIterator();
}
// in-order iterator
class InOrderIterator implements Iterator<T> {
class NodeWithStatus {
Node node;
boolean expanded;
NodeWithStatus(Node node, boolean expanded) {
this.node = node;
this.expanded = expanded;
}
T getValue() {
return node.value;
}
boolean isEmpty() {
return node == null;
}
}
private LinkedList<NodeWithStatus> stack;
public InOrderIterator(Node node) {
stack = new LinkedList<NodeWithStatus>();
pushItem(unexpandedNode(root));
}
private void pushItem(NodeWithStatus item) {
if (!item.isEmpty()) {
stack.push(item);
}
}
private NodeWithStatus unexpandedNode(Node node) {
return new NodeWithStatus(node, false);
}
private NodeWithStatus expandedNode(Node node) {
return new NodeWithStatus(node, true);
}
public boolean hasNext() {
return !stack.isEmpty();
}
public T next() {
if (!hasNext()) throw new IllegalStateException("no next element");
NodeWithStatus item;
while (!(item = stack.pop()).expanded) {
Node node = item.node;
pushItem(unexpandedNode(node.rightChild));
pushItem(expandedNode(node));
pushItem(unexpandedNode(node.leftChild));
}
return item.getValue();
}
public void remove() {
throw new UnsupportedOperationException("unsupported operation");
}
}
public Iterator<T> inorderIterator() {
return new InOrderIterator(root);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment