RB Tree | Inser & Delete bugs

[gavra]

Hi,
For those who already seen my last post probably understand this one (XD)
So I am trying to implement a red black tree in C++ and it seems to be buggy \=

main:

int main()
{
	RedBlackTree* rbt = new RedBlackTree();
	rbt->Insert(new RBNode(1, BLACK));
	rbt->Insert(new RBNode(4, BLACK));
	RBNode* x = new RBNode(5, BLACK);
	rbt->Insert(x);
	
	rbt->Insert(new RBNode(3, BLACK));
	rbt->Insert(new RBNode(2, BLACK));
	rbt->Insert(new RBNode(6, BLACK));
	//rbt->Delete(x);

	rbt->Print();

	cout << endl << "Success.";
	return 0;
}

Classes:
Gavra's Pastebin - Pastebin.com

After running main I gets:
1, 3, 2, 4, 5, 6,
which isn't right since the print is in-order.

if you will remove the comment next to the delete call you will get this:
6, 4, 5, 6,
well I think you get what's wrong here

Your help would be really appriciated
Thank you.

[iMalc]

If the ordering is being screwed up, then your rotations are probably incorrect.

The delete must have several issues to produce that result. Don't worry about the delete for now though. Just focus on getting the insert correct first. Trying to get deletions correct when your tree is sometimes wrong to begin with, well just isn't going to happen.
What I find really useful with developing this sort of thing is to have something which verifies the tree at each step for me, so I can see exactly which operations screw it up. Here is the verification function I wrote for my red-black tree:

template <class TNode>
bool VerifyHelper(const TNode *head, int &numBlack) {
	int numLeft=0, numRight=0;
	if (head != NULL) {
		if (head->left != NULL) {
			if ((*head < *(head->left))
			|| (head->red && head->left->red)
			|| !VerifyHelper(head->left, numLeft)) return false;
		}
		if (head->right != NULL) {
			if ((*(head->right) < *head)
			|| (head->red && head->right->red)
			|| !VerifyHelper(head->right, numRight)) return false;
		}
		if (numLeft != numRight) return false;
		numBlack = numLeft + (head->red ? 0 : 1);
	}
	return true;
}	

template <class TNode>
bool Verify(const TNode *head) {
	int numBlack=0;
	return (!red(head)) && VerifyHelper(head, numBlack);
}

This checks ordering, number of black nodes from root to each leaf, ensures there are no consecutive red nodes, and ensures the head is black - basically everything.

Your should be able to make whatever small modifications are needed to that to have it work with your code. Just call Verify with the head node and if it returns true you're good, and if it returns false, your tree is violating one of the properties I just listed.

[gavra]

Thanks.
Finally I found all of my mistakes.
I updated the files at pastebin if anyone here wants.