Generic Self-Balancing Key-Value Binary Search Tree for /r/javaexamples

BinaryTreeKV.java

/* Generic Self-Balancing Key-Value Binary Search Tree
for /r/javaexamples
by /u/Philboyd_Studge
*/

import java.util.Queue;
import java.util.LinkedList;
import java.util.List;

@SuppressWarnings("unchecked")

public class BinaryTreeKV<K extends Comparable<K>, V>
{

	// stores top of tree
	private Node root;

	// for balancing/printing
	// sorted list of nodes by key
	List<Node> inOrderList;
	Queue<Node> printQueue;
	boolean balancing;



	public BinaryTreeKV()
	{
		root = null;
		inOrderList = new LinkedList<>();
		printQueue = new LinkedList<>();
		balancing = false;
	}

	public void clear()
	{
		root = null;
	}

	public boolean isEmpty()
	{
		return root==null;
	}

	public Node getNode(K key)
	{
		return getNode(root, key);
	}

	public Node getNode(Node node, K key)
	{
		if (node==null) return null;
		if (key.compareTo(node.key) == 0) return node;
		if (key.compareTo(node.key) < 0) return getNode(node.left, key);
		return getNode(node.right, key);
	}

	public V get(K key)
	{
		return get(root, key);
	}

	private V get(Node node, K key)
	{
		if (node==null) return null;
		if (key.compareTo(node.key) ==0) return node.getValue();
		if (key.compareTo(node.key) < 0) return get(node.left, key);
		return get(node.right, key);
	}

	public int size()
	{
		return size(root);
	}

	public int size(Node node)
	{
		if (node==null) return 0;
		return size(node.left) + 1 + size(node.right);
	}

	public int depth()
	{
		return depth(root);
	}


	public int depth(Node node)
	{
		if (node == null) return 0;
		int left = depth(node.left);
		int right  = depth(node.right);
		return (left > right) ? left + 1 : right + 1;
	}

	public void delete(K key)
	{
		Node node = getNode(key);
		if (node == null) return;
		getInorderList();
		if (inOrderList.contains(node))
		{
			inOrderList.remove(node);
			clear();
			balancing = true;
			balanceTree(0, inOrderList.size()-1);
			balancing = false;
		}
	}

	public void insert(K key, V value)
	{
		if (!balancing)
		{
			if (root != null && size() > 2)
				if (depth() > size() / 2)
					System.out.println("Balancing...");
					balancing = true;
					balance();
		}
		root = insert(root, key, value);
	}

	private Node insert(Node node, K key, V value)
	{
		if (node==null)
		{
			node = new Node(key, value);
		}
		else
		{
			if (key.compareTo(node.key)==0)
			{
				node.setValue(value);
			}
			else
			{
				if (key.compareTo(node.key) < 0)
				{
					node.left = insert(node.left, key, value);
				}
				else
				{
					node.right = insert(node.right, key, value);
				}

			}
		}
		return node;
	}

	public void getInorderList()
	{
		if (!inOrderList.isEmpty()) inOrderList.clear();
		getInorderList(root);
	}

	private void getInorderList(Node node)
	{
		if (node==null) return;
		getInorderList(node.left);
		inOrderList.add(node);
		getInorderList(node.right);

	}

	private void balance()
	{
		// get the sorted list
		getInorderList();
		// clear the tree
		clear();
		// get the number of elements
		int count = inOrderList.size();
		// call the recursive function with min = 0 and max = size
		balanceTree(0, count - 1);
		// finished, set flag to false
		balancing = false;

	}

	private void balanceTree(int min, int max)
	{
		// recurse until min > max
		if (min <= max)
		{
			// get middle index
			int mid = (int) Math.ceil((double) (min + max) / 2);
			// create temp node to get key & value of middle object
			Node temp = inOrderList.get(mid);
			// insert into tree
			insert(temp.key, temp.value);
			// recurse lower elements
			balanceTree(min, mid - 1);
			// recurse higher elements
			balanceTree(mid + 1, max);
		}
	}


	public void printList()
	{
		for (Node each : inOrderList)
		{
			printQueue.add(each);
		}
		printQueueFlush();
	}

	public void printTree()
	{
		printQueue.clear();
		printTree(root);
		printQueueFlush();
	}

	private void printTree(Node node)
	{
		if (node==null) return;

		printTree(node.left);
		printQueue.add(node);
		printTree(node.right);
	}

	public void printPostOrder()
	{
		printQueue.clear();
		printPostOrder(root);
		printQueueFlush();
	}

	public void printPostOrder(Node node)
	{
		if (node==null) return;
		printPostOrder(node.left);
		printPostOrder(node.right);
		printQueue.add(node);
	}

	public void printLevelOrder()
	{
		printQueue.clear();
		printLevelOrder(root);
		printQueueFlush();
	}
	public void printLevelOrder(Node node)
	{
		Queue<Node> q = new LinkedList<>();
		q.add(node);
		while (!q.isEmpty())
		{
			Node temp = q.poll();
			printQueue.add(temp);
			if (temp.left != null) q.add(temp.left);
			if (temp.right != null) q.add(temp.right);
		}
	}

	public void printQueueFlush()
	{
		while (!printQueue.isEmpty())
		{
			System.out.print(printQueue.poll().toString());
		}
		System.out.println();
	}

	class Node
	{
		Node left;
		Node right;
		K key;
		V value;

		Node(K newKey, V newValue)
		{
			left = null;
			right = null;
			key = newKey;
			value = newValue;
		}

		public K getKey()
		{
			return key;
		}

		public V getValue()
		{
			return value;
		}

		public void setValue(V val)
		{
			value = val;
		}

		@Override
		public String toString()
		{
			return key + ":" + value + " ";
		}
	}

	public static void main( String [] args )
	{

		BinaryTreeKV<Integer, String> tree = new BinaryTreeKV<>();
		System.out.println("Is tree empty:" + tree.isEmpty());
		tree.insert(5, "Bill");
		tree.insert(3, "bob");
		tree.insert(1, "poop");
		tree.insert(2, "jane");
		tree.insert(8, "what");
		tree.insert(6, "this");
		tree.insert(7, "dsdfs");

		System.out.println("Is tree empty:" + tree.isEmpty());
		System.out.println("Tree depth:" + tree.depth());
		System.out.println("Lookup value for key `3` = " + tree.getNode(3));

		System.out.println("Inorder List");
		tree.getInorderList();
		tree.printList();
		System.out.println("Level Order:");
		tree.printLevelOrder();
		System.out.println("Tree depth:" + tree.depth());

		tree.insert(4,"dog");
		tree.insert(10,"cat");
		tree.insert(9,"help");

		tree.getInorderList();
		tree.printList();
		System.out.println("Tree depth:" + tree.depth());
		System.out.println("deleting '3'");
		tree.printLevelOrder();
		tree.delete(3);
		tree.printLevelOrder();
		tree.printTree();

	}

}