import java.util.ArrayList;
public class BinarySearchTree<K extends Comparable<K>, V> {
private Node root;
private int size;
public BinarySearchTree() {
root = null;
size = 0;
}
public static void main(String[] args) {
ArrayList<Integer> words = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
words.add(i);
}
BinarySearchTree<Integer, Integer> tree = new BinarySearchTree<>();
for (Integer word : words) {
if (!tree.contains(word)) {
tree.insert(word, 0);
}
tree.set(word, tree.search(word).value + 1);
}
System.out.println("Height: " + tree.getHeight(tree.root));
System.out.println(tree.getMin().key + ": " + tree.getMin().value);
tree.remove(tree.getMin().key);
System.out.println(tree.getMin().key + ": " + tree.getMin().value);
System.out.println("Is valid BST? " + tree.isBST());
}
/**
* Insert content to BST
*
* @param key
* @param value
*/
public void insert(K key, V value) {
root = insert(root, key, value);
}
/**
* Insert content under a specific node, usually called by
* <code>{@link #insert(K, V)}</code>.
*
* @param node
* @param key
* @param value
* @return
*/
private Node insert(Node node, K key, V value) {
if (node == null) {
size++;
return new Node(key, value);
}
// insert to left branch
if (key.compareTo(node.key) < 0) {
node.left = insert(node.left, key, value);
}
// insert to right branch
else if (key.compareTo(node.key) > 0) {
node.right = insert(node.right, key, value);
}
// update the node with given value instead of creating a new one
else {
node.value = value;
}
return node;
}
/**
* Update the node bind the given key with new value.
*
* @param key
* @param value
* @return
*/
public void set(K key, V value) {
Node node = search(root, key);
if (node == null) {
throw new IllegalArgumentException(key + " Not Present!");
}
node.value = value;
}
/**
* Search the whole BST for the wanted node binding given key.
*
* @param key
* @return
*/
private Node search(K key) {
return search(root, key);
}
/**
* Search the specific node for the wanted node binding given key, usually called by
* <code>{@link #search(K)}</code>.
*
* @param node
* @param key
* @return
*/
private Node search(Node node, K key) {
if (node == null) {
return null;
}
// exactly the wanted node
if (key.compareTo(node.key) == 0) {
return node;
}
// wanted node on left branch
else if (key.compareTo(node.key) < 0) {
return search(node.left, key);
}
// wanted node on right branch
return search(node.right, key);
}
/**
* Search the whole BST for the node binding the smallest key.
*
* @param
*/
private Node getMin() {
return getMin(this.root);
}
/**
* Search under the given node for the node binding the smallest key, usually called by
* <code>{@link #getMin()}</code>.
*
* @param node
*/
private Node getMin(Node node) {
if (node.left == null) {
return node;
}
return getMin(node.left);
}
/**
* Delete the node binding the given key under the whole BST.
*
* @param key
* @return
*/
public V remove(K key) {
if (isEmpty()) {
return null;
}
Node node = search(root, key);
if (node != null) {
root = remove(root, key);
return node.value;
}
return null;
}
/**
* Delete the node binding the given key under the given node, usually called by
* <code>{@link #remove(K)}</code>.
*
* @param node
* @param key
* @return
*/
private Node remove(Node node, K key) {
if (node == null) {
return null;
}
// search left
if (key.compareTo(node.key) < 0) {
node.left = remove(node.left, key);
return node;
}
// search right
else if (key.compareTo(node.key) > 0) {
node.right = remove(node.right, key);
return node;
}
// exactly the current one is the wanted node
// 4 situations to be considered separately.
size--;
// 1. both empty
if (node.left == null && node.right == null) {
return null;
}
// 2. left empty
if (node.left == null) {
return node.right;
}
// 3. right empty
if (node.right == null) {
return node.left;
}
// 4. both non-empty
// Find the min node on right branch which should be a node without left branch.
Node successor = getMin(node.right);
// Remove the min node from its original position and serves as a successor of current
// node that going to be removed.
successor.right = remove(node.right, successor.key);
successor.left = node.left;
// unlink the removed node, so that the gc will quickly find it.
node.left = node.right = null;
return successor;
}
public boolean contains(K key) {
return search(root, key) != null;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public int getHeight() {
return getHeight(root);
}
private int getHeight(Node root) {
if (root == null) {
return 0;
}
int left = getHeight(root.left);
int right = getHeight(root.right);
return Math.max(left, right) + 1;
}
/**
* Verify current tree whether it's a qualified Binary Search Tree or not.
*
* @return
*/
public boolean isBST() {
ArrayList<K> keys = new ArrayList<>();
inOrderTraversal(root, keys);
for (int i = 1; i < keys.size(); i++) {
if (keys.get(i - 1).compareTo(keys.get(i)) > 0) {
return false;
}
}
return true;
}
private void inOrderTraversal(Node node, ArrayList<K> keys) {
if (node == null) {
return;
}
inOrderTraversal(node.left, keys);
keys.add(node.key);
inOrderTraversal(node.right, keys);
}
private class Node {
K key;
V value;
Node left;
Node right;
Node(K key, V value) {
this.key = key;
this.value = value;
left = null;
right = null;
}
}
}