public void insert(int value) {		
		// Case 1
		if (root == null) {
			root = new RedBlackNode(BLACK);
			root.setValue(value);
			//insert fake leaves
			root.setRight(new RedBlackNode(true, true));
			root.setLeft(new RedBlackNode(true, true));
			return;
		}
			
		// insert node as red
		RedBlackNode tmp = findParent(value);
		RedBlackNode child = new RedBlackNode(RED);
		child.setValue(value);
		child.setParent(tmp);
		if (value < tmp.getValue()) {
			tmp.setLeft(child);
		}
		else {
			tmp.setRight(child);
		}
		
		//insert fake leaves
		child.setRight(new RedBlackNode(true, true));
		child.setLeft(new RedBlackNode(true, true));
		
		RedBlackNode x = child;
		while ( (x != root) && (((RedBlackNode) x.getParent()).getColor() == RED)) {
			if (x.getParent().isLeft()) {
				RedBlackNode gParent = grandparent(x);
				RedBlackNode uncle = (RedBlackNode) gParent.getRight();
				if (uncle.getColor() == RED) {
					((RedBlackNode) child.getParent()).setBlack();
					uncle.setBlack();
					gParent.setRed();
					x = gParent; // move x up the tree
				}
				else { 
					if (x.isRight()) {
						// move x up and rotate
						x = (RedBlackNode) x.getParent();
						rotate_left(x);
					}
					((RedBlackNode) x.getParent()).setBlack();
					grandparent(x).setRed();
					rotate_right(grandparent(x));
				}
			}
			else { // parent is right child
				RedBlackNode gParent = grandparent(x);
				RedBlackNode uncle = (RedBlackNode) gParent.getLeft();
				if (uncle.getColor() == RED) {
					((RedBlackNode) child.getParent()).setBlack();
					uncle.setBlack();
					gParent.setRed();
					x = gParent; // move x up the tree
				}
				else { 
					if (x.isLeft()) {
						// move x up and rotate
						x = (RedBlackNode) x.getParent();
						rotate_right(x);
					}
					((RedBlackNode) x.getParent()).setBlack();
					grandparent(x).setRed();
					rotate_left(grandparent(x));
				}
			}
		}
		root.setBlack();
	}