RBTree (no delete yet, can trace)

RBTree.java

import java.util.Comparator;
import java.util.LinkedList;


public class RBTree<T1,T2> {
	
	
	public static final boolean RED = true;
	public static final boolean BLACK = false;
	
	public static final int COLOR = 0;
	public static final int KEY = 1;
	
	public static void main(String[] args)
	{
		RBTree<Character,Integer> rb = new RBTree<Character, Integer>(new Comparator<Character>() {

			@Override
			public int compare(Character a, Character b) {
				return a.compareTo(b);
			}
		});
		
		String str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
		
		for (int i = 0; i < str.length(); i++)
		{
			rb.put(str.charAt(i), i);
			

			rb.printTree(COLOR);
			System.out.println();
			rb.printTree(KEY);
			System.out.println();
			System.out.println("_____________________");
		}
		
		//char key = 'H';
		//rb.put(key, rb.get(key) + 1000);
		//System.out.println(rb.get(key));
		
		//rb.printTree(COLOR);
	}
	
	class Node
	{
		T1 key;
		T2 value;
		int size;
		boolean color;
		
		Node left, right;
		
		public Node(T1 key, T2 value, boolean color) {
			this.key = key;
			this.value = value;
			this.color = color;
			
			size = 1;
		}
		
		@Override
		public String toString()
		{
			StringBuilder sb = new StringBuilder();
			sb.append("Size: " + size);
			sb.append(", Color: " + (color? "RED" : "BLACK"));
			
			return sb.toString();
		}
	}
	
	private Node root;
	
	private final Comparator<T1> cmp;
	
	public void printTree(int mode)
	{
		LinkedList<Node> workingL = new LinkedList<Node>();
		workingL.add(root);
		
		LinkedList<Node> finalL = new LinkedList<Node>();
		
		Node current;
		
		int ctr = 0;
		int limit = root.size*2;
		
		while (!workingL.isEmpty() && ctr < limit)
		{
			current = workingL.pop();
			
			if (current != null)
			{
				workingL.add(current.left);
				workingL.add(current.right);
			}
			
			finalL.add(current);
			
			ctr++;
		}
		
		int tilNext = 1;
		ctr = 0;
		
		while (!finalL.isEmpty())
		{
			if (ctr + 1 == tilNext)
			{
				System.out.println();
				tilNext*=2;
			}
			
			Node n = finalL.pop();
			
			if (n == null)
				System.out.print("_");
			else
			{
				Object data = null;
				switch (mode)
				{
					case COLOR:
						data = n.color? "R" : "B";
						break;
					case KEY:
					default:
						data = n.key;
						break;
				}
				
				System.out.print(data);
			}
			
			System.out.print(" ");
			ctr++;
		}
	}
	
	public RBTree(Comparator<T1> cmp)
	{
		this.cmp = cmp;
	}
	
	public T2 get(T1 key)
	{
		return get(root, key);
	}
	
	private T2 get(Node node, T1 key) {
		if (node == null)
			return null;
		
		if (node.key.equals(key))
			return node.value;
		
		int i = cmp.compare(key, node.key);
		
		if (i > 0)
			return get(node.right, key);
		else
			return get(node.left, key);
	}

	public void put(T1 key, T2 value)
	{
		root = put(root, key, value);
	}

	private Node put(Node node, T1 key, T2 value) {
		if (node == null)
			return new Node(key, value, RED);
		
		int i = cmp.compare(key, node.key);
		
		if (i == 0)
		{
			node.value = value;
		}
		if (i > 0)
			node.right = put(node.right, key, value);
		else
			node.left = put(node.left, key, value);
		
		//Rotate
		
		if (isRed(node.right) && !isRed(node.left)) //Adjust Right, but only if left is null
			node = rotateLeft(node);
		
		if (isRed(node.left) && isRed(node.left.left)) //Fix left
			node = rotateRight(node);
			
		if (isRed(node.left) && isRed(node.right))
			flipColors(node);
	
		updateSize(node);
		
		return node;
	}

	private void updateSize(Node node) {
		int size = 1;
		if (node.left != null)
			size += node.left.size;
		if (node.right != null)
			size += node.right.size;
		
		node.size = size;
	}

	private void flipColors(Node node) {
		
		node.color = !node.color;
		node.right.color = !node.right.color;
		node.left.color = !node.left.color;
	}

	private Node rotateRight(Node node) {
		Node top = node.left;
		Node right = node;
		
		right.left = top.right;
		top.right = right;
		updateSize(right);
				
		top.color = right.color;
		right.color = RED;
		
		
		return top;
	}

	private Node rotateLeft(Node node) {
		Node top = node.right;
		Node left = node;
		
		left.right = top.left;
		top.left = left;
		updateSize(left);
				
		top.color = left.color;
		left.color = RED;
		
		return top;
	}

	private boolean isRed(Node node) {
		
		if (node != null && node.color == RED)
			return true;
		else
			return false;
	}
}