import java.util.ArrayList;
public class AVLTree<K extends Comparable<K>, V> {
private Node root;
private int size;
public AVLTree() {
root = null;
size = 0;
}
public static void main(String[] args) {
ArrayList<Integer> words = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
words.add(i);
}
AVLTree<Integer, Integer> tree = new AVLTree<>();
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());
}
/**
* Get the height of the max long branch.
*
* @param node
* @return
*/
private int getHeight(Node node) {
if (node == null) {
return 0;
}
return node.height;
}
/**
* The height difference between left and right branches.
*
* @param node
* @return
*/
private int getBalanceFactor(Node node) {
if (node == null) {
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}
/**
* Rotate when right is higher
*
* @param node
* @return
*/
private Node rightRotate(Node node) {
// node nodex
// / \ / \
// nodex N5 right rotate N1 node
// / \ - - - - - - > / \ / \
// N1 N4 N2 N3 N4 N5
// / \
// N2 N3
Node nodex = node.left;
Node N3 = nodex.right;
nodex.right = node;
node.left = N3;
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
nodex.height = Math.max(getHeight(nodex.left), getHeight(nodex.right)) + 1;
return nodex;
}
/**
* Rotate when right is higher
*
* @param node
* @return
*/
private Node leftRotate(Node node) {
// node nodex
// / \ / \
// N1 nodex left rotate node N3
// / \ - - - - - - > / \ / \
// N2 N3 N1 N2 N4 N5
// / \
// N4 N5
Node nodex = node.right;
Node N2 = nodex.left;
nodex.left = node;
node.right = N2;
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
nodex.height = Math.max(getHeight(nodex.left), getHeight(nodex.right)) + 1;
return nodex;
}
/**
* Insert new element.
*
* @param key
* @param value
*/
public void insert(K key, V value) {
root = insert(root, key, value);
}
/**
* Insert content under a specific node and adjust the balance of the tree afterwards, 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;
}
// Update current height after inserting new node which may change.
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
return keepBalance(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;
}
Node retNode;
// search left
if (key.compareTo(node.key) < 0) {
node.left = remove(node.left, key);
retNode = node;
}
// search right
else if (key.compareTo(node.key) > 0) {
node.right = remove(node.right, key);
retNode = node;
}
// exactly the current one is the wanted node
else {
// 4 situations to be considered separately.
size--;
// 1. both empty
if (node.left == null && node.right == null) {
retNode = null;
}
// 2. left empty
else if (node.left == null) {
retNode = node.right;
}
// 3. right empty
else if (node.right == null) {
retNode = node.left;
}
// 4. both non-empty
else {
// 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;
retNode = successor;
}
}
if (retNode == null) {
return null;
}
return keepBalance(node);
}
/**
* Adjust the tree to make it balanced.
*
* @param node
* @return
*/
private Node keepBalance(Node node) {
int balanceFactor = getBalanceFactor(node);
// left branch is much higher, run right rotate
if (balanceFactor > 1) {
if (getBalanceFactor(node.left) < 0) {
node.left = leftRotate(node.left);
}
return rightRotate(node);
}
// right branch is much higher, run left rotate
if (balanceFactor < -1) {
if (getBalanceFactor(node.right) > 0) {
node.right = rightRotate(node.right);
}
return leftRotate(node);
}
return node;
}
/**
* Verify if the tree is balanced.
*
* @return
*/
public boolean isBalanced() {
return isBalanced(root);
}
/**
* Verify if the tree is balanced recursively, usually called by
* <code>{@link #isBalanced(Node)}</code>..
*
* @param node
* @return
*/
private boolean isBalanced(Node node) {
if (node == null) {
return true;
}
int balanceFactor = getBalanceFactor(node);
if (Math.abs(balanceFactor) > 1) {
return false;
}
return isBalanced(node.left) && isBalanced(node.right);
}
public boolean contains(K key) {
return search(root, key) != null;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* 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;
int height;
Node(K key, V value) {
this.key = key;
this.value = value;
this.left = null;
this.right = null;
this.height = 1;
}
}
}