Skip to content

Instantly share code, notes, and snippets.

@AlexAbraham1

AlexAbraham1/BinarySearchTree.java

Created February 1, 2015 21:20
Show Gist options
  • Save AlexAbraham1/369a1caa8afcd4777f1d to your computer and use it in GitHub Desktop.
Save AlexAbraham1/369a1caa8afcd4777f1d to your computer and use it in GitHub Desktop.
Download ZIP
Raw
BinarySearchTree.java
package com.abraham.trees;
public class BinarySearchTree<E extends Comparable<E>> extends BinaryTree<E> {
protected Node<E> root;
protected Node<E> nil;
public static void main(String[] args) {
BinarySearchTree<Integer> bt = new BinarySearchTree<Integer>();
bt.insert(2);
bt.insert(4);
bt.insert(9);
bt.inorderWalk(new Visitor<Integer>() {
@Override
public BinaryTree.Node<Integer> visit(BinaryTree.Node<Integer> node) {
System.out.println(node);
return node;
}
});
// System.out.println(bt.minimum());
// System.out.println(bt.maximum());
System.out.println();
System.out.println();
bt.delete(9);
bt.inorderWalk(new Visitor<Integer>() {
@Override
public BinaryTree.Node<Integer> visit(BinaryTree.Node<Integer> node) {
System.out.println(node);
return node;
}
});
// System.out.println(bt.minimum());
// System.out.println(bt.maximum());
}
@Override
public Node<E> search(E key) {
return search(root, key);
}
protected Node<E> search(Node<E> node, E key) {
int compareValue;
if (node == nil || (compareValue = key.compareTo(node.data)) == 0) return node;
if (compareValue < 0) return search(node.left, key);
return search(node.right, key);
}
public Node<E> minimum() {
return treeMinimum(root);
}
protected Node<E> treeMinimum(Node<E> node) {
while (node.left != nil) node = node.left;
return node;
}
public Node<E> maximum() {
return treeMaximum(root);
}
protected Node<E> treeMaximum(Node<E> node) {
while (node.right != nil) node = node.right;
return node;
}
public Node<E> successor(Node<E> node)
{
if (node.right != nil) return treeMinimum(node.right);
else {
Node<E> parent = node.parent;
while (parent != nil && parent.right == node) {
node = parent;
parent = parent.parent;
}
return parent;
}
}
public Node<E> predecessor(Node<E> node)
{
if (node.left != nil) return treeMaximum(node.left);
else {
Node<E> parent = node.parent;
while (parent != nil && parent.left == node) {
node = parent;
parent = parent.parent;
}
return node;
}
}
@Override
public Node<E> insert(E data) {
Node<E> node = new Node<E>(data, nil);
return treeInsert(node);
}
protected Node<E> treeInsert(Node<E> newNode) {
Node<E> parent = nil;
Node<E> node = root;
while (node != nil) {
parent = node;
if (newNode.compareTo(node) <= 0) node = node.left;
else node = node.right;
}
newNode.parent = parent;
if (parent == nil) root = newNode;
else {
if (newNode.compareTo(parent) <= 0) parent.left = newNode;
else parent.right = newNode;
}
return newNode;
}
@Override
public void delete(E data) {
Node<E> node = search(data);
if (node != nil) delete(node);
}
protected void delete(Node<E> node) {
if (node == nil) throw new IllegalArgumentException("Can't delete nil!!!");
Node<E> replacement;
if (node.left == nil) {
replacement = node.right;
} else if (node.right == nil) {
replacement = node.left;
} else {
replacement = successor(node);
delete(replacement);
replacement.left = node.left;
replacement.right = node.right;
node.left.parent = replacement;
node.right.parent = replacement;
}
if (replacement != nil) {
replacement.parent = node.parent;
}
if (root == node) {
root = replacement;
} else {
if (node == node.parent.left) {
node.parent.left = replacement;
} else {
node.parent.right = replacement;
}
}
}
protected static class Node<E extends Comparable<E>> extends BinaryTree.Node<E> implements Comparable<Node<E>> {
E data;
Node<E> left;
Node<E> right;
Node<E> parent;
Node<E> nil;
public Node(E data, Node<E> nilNode) {
super(data, nilNode);
this.data = data;
this.nil = nilNode;
this.left = nil;
this.right = nil;
this.parent = nil;
}
@Override
public int compareTo(Node<E> node) {
return this.data.compareTo(node.data);
}
}
}
Raw
BinaryTree.java
package com.abraham.trees;
public class BinaryTree<E> {
protected Node<E> root;
protected Node<E> nil;
public static void main(String[] args) {
BinaryTree<Integer> bt = new BinaryTree<Integer>();
bt.insert(2);
bt.insert(4);
bt.insert(9);
bt.inorderWalk(new Visitor<Integer>() {
@Override
public Node<Integer> visit(Node<Integer> node) {
System.out.println(node);
return node;
}
});
System.out.println(getMin(bt));
System.out.println(getMax(bt));
System.out.println();
bt.delete(9);
bt.inorderWalk(new Visitor<Integer>() {
@Override
public Node<Integer> visit(Node<Integer> node) {
System.out.println(node);
return node;
}
});
System.out.println(getMin(bt));
System.out.println(getMax(bt));
}
public BinaryTree() {
setNil(new Node<E>(null, nil));
root = nil;
}
protected void setNil(Node<E> node) {
nil = node;
node.parent = nil;
node.left = nil;
node.right = nil;
}
protected boolean isNil(Node<E> node) {
return node == nil;
}
public void inorderWalk(Visitor<E> v) {
inorderWalk(root, v);
}
protected void inorderWalk(Node<E> node, Visitor<E> v) {
if (!isNil(node)) {
inorderWalk(node.left, v);
v.visit(node);
inorderWalk(node.right, v);
}
}
public Node<E> search(E key) {
return search(root, key);
}
protected Node<E> search(Node<E> node, E key) {
Node<E> result = nil;
if (node == nil) return nil;
if (node.data.equals(key)) return node;
if (node.left != nil) result = search(node.left, key);
if (result == nil) result = search(node.right, key);
return result;
}
public static <E extends Comparable<E>> Node<E> getMin(BinaryTree<E> tree) {
return getMin(tree.root, tree.nil, tree.nil);
}
private static <E extends Comparable<E>> Node<E> getMin(Node<E> currentNode, Node<E> currentMax, Node<E> nil) {
if (currentMax == nil) currentMax = currentNode;
if (currentNode == nil) return currentMax;
if (currentNode.data.compareTo(currentMax.data) < 0) currentMax = currentNode;
currentMax = getMin(currentNode.left, currentMax, nil);
currentMax = getMin(currentNode.right, currentMax, nil);
return currentMax;
}
public static <E extends Comparable<E>> Node<E> getMax(BinaryTree<E> tree) {
return getMax(tree.root, tree.nil, tree.nil);
}
private static <E extends Comparable<E>> Node<E> getMax(Node<E> currentNode, Node<E> currentMax, Node<E> nil) {
if (currentMax == nil) currentMax = currentNode;
if (currentNode == nil) return currentMax;
if (currentNode.data.compareTo(currentMax.data) > 0) currentMax = currentNode;
currentMax = getMax(currentNode.left, currentMax, nil);
currentMax = getMax(currentNode.right, currentMax, nil);
return currentMax;
}
public Node<E> insert(E data) {
Node<E> node = new Node<E>(data, nil);
return treeInsert(node);
}
protected Node<E> treeInsert(Node<E> newNode) {
Node<E> parent = nil;
Node<E> node = root;
int random = 0;
while (node != nil) {
parent = node;
random = (int) System.nanoTime() % 2; //Random number 0 or 1
node = random == 0 ? node.left : node.right; //Go right or left based on
}
newNode.parent = parent;
if (parent == nil) root = newNode;
else {
if (random == 0) parent.left = newNode; //can't check for node.left because might be a leaf and
//that would give left priority in leafs (not random)
else parent.right = newNode;
}
return newNode;
}
public void delete(E data) {
Node<E> node = search(data);
if (node != nil) delete(node);
}
protected void delete(Node<E> node) {
if (node == nil) throw new IllegalArgumentException("Can't delete nil!!!");
Node<E> replacement;
if (node.left == nil) {
replacement = node.right;
} else if (node.right == nil) {
replacement = node.left;
} else {
Node<E> temp = node.left;
while (temp.left != nil) {
temp = temp.left;
}
replacement = temp;
delete(replacement);
replacement.left = node.left;
replacement.right = node.right;
node.left.parent = replacement;
node.right.parent = replacement;
}
if (replacement != nil) {
replacement.parent = node.parent;
}
if (root == node) root = replacement;
else {
if (node == node.parent.left) node.parent.left = replacement;
else node.parent.right = replacement;
}
}
protected static class Node<E> {
E data;
Node<E> left;
Node<E> right;
Node<E> parent;
Node<E> nil;
public Node(E data, Node<E> nilNode) {
this.data = data;
this.nil = nilNode;
this.left = nil;
this.right = nil;
this.parent = nil;
}
@Override
public String toString() {
if (this == nil) return "nil";
return data.toString();
}
}
public interface Visitor<E> {
public Node<E> visit(Node<E> node);
}
}
Raw
Issues
Right now the issue I get is my inOrderWalk doesn't print out anything. I think the reason is that it is using the BinaryTree.Node from the BinaryTree class instead of the BinarySearchTree node from the BinarySearchTree class
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment