Red Black Tree Frustration!

[EASports]

Hi everyone!

I am trying to implement a red black tree and I'm having one huge problem. I recursively call my insert() method to find a null leaf, and after a rotation, the right child and parent of the rotated center are incorrect. Things may have gotten out of hand, but here is the insert method (I have confidence in the rotate methods)

private RBNode insert(Comparable x, RBNode t, RBNode parent) {

		if (t == null){
			System.out.println("Inserting " + x);
			t = new RBNode(x,null,null,true,parent);
			if(t.parent == null)
				t.red = false;
				}
		else if (x.compareTo(t.element)<0){
			t.left = insert(x,t.left,t);
			System.out.println("kicked back up");}
		else if (x.compareTo(t.element)>0){
			t.right = insert(x,t.right,t);
			System.out.println("kicked back up");}

		RBNode u = new RBNode(0);
		u = uncle(t);
		RBNode g = new RBNode(0);
		g = grandparent(t);

		if(t.red == true && t.parent != null && t.parent.red == false){			//case 2 wiki
				System.out.println("Case 2");
				if(t.right != null)
					System.out.println(t.element + "'s right child = " + t.right.element);
				else
					System.out.println(t.element + "'s right child = null");
				t.height = max(height(t.left),height(t.right))+1;
				return t;
				}

		else if(t.parent != null && t.parent.red == true && u != null && u.red == true){		//case 3 wiki
				System.out.println("Case 3");
				t.parent.red = false;
				u.red = false;
				g.red = true;
				if(g.parent == null)
					g.red = false;
				t.height = max(height(t.left),height(t.right))+1;
				return t;
					}

		if(g != null){
 		       	if ((t == t.parent.right) && (t.parent == g.left)) {		//case 4a wiki
 		       			System.out.println("Case 4a");
 		       	        rotateWithRightChild(t.parent);
 		       	        t = t.left;
 		       				}


 		       	else if ((t == t.parent.left) && (t.parent == g.right)) {		//case 4b wiki
 		       	System.out.println("Case 4b");
 		       	        rotateWithLeftChild(t.parent);
 		       	        t = t.right;
 		       	        }

			        t.parent.red = false;
 		      		g.red = true;

 		      		if ((t == t.parent.left) && (t.parent == g.left)) {
						System.out.println("Case 5a");
 		      	         rotateWithLeftChild(g);

 		      		 }

       				 else if((t == t.parent.right) && (t.parent == g.right)){
            		    /*
            		     * Here, (n == n->parent->right) && (n->parent == g->right).
            		     */
            		     System.out.println("Case 5b");
            			 rotateWithRightChild(g);

				 	if(g.right != null)
						System.out.println("Now " + g.element + "'s right child is " + g.right.element);
					else
	  					System.out.println(g.element + "'s right child = null");
       			 }}

		t.height = max(height(t.left),height(t.right))+1;
		return t;
   		}

For example, under case 5b, the rotated center will show the correct right child. But after the recursion backs up, this information is reset... Is it something with recursion that I'm not factoring in?

Thanks!

Eric