Thread: RB Tree | Inser & Delete bugs

  1. #1
    Registered User gavra's Avatar
    Join Date
    Jun 2008

    RB Tree | Inser & Delete bugs

    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 \=

    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(new RBNode(3, BLACK));
    	rbt->Insert(new RBNode(2, BLACK));
    	rbt->Insert(new RBNode(6, BLACK));
    	cout << endl << "Success.";
    	return 0;
    Gavra's Pastebin -

    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.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    New Zealand
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Finally I found all of my mistakes.
    I updated the files at pastebin if anyone here wants.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. avl tree delete question
    By nik in forum C++ Programming
    Replies: 1
    Last Post: 12-23-2010, 01:32 AM
  2. Delete Binary Tree Node
    By matrixx333 in forum C Programming
    Replies: 4
    Last Post: 11-30-2009, 12:39 AM
  3. Delete all from a Binary Tree
    By Silvio in forum C Programming
    Replies: 5
    Last Post: 04-25-2009, 06:23 AM
  4. Replies: 17
    Last Post: 11-16-2006, 09:06 PM
  5. delete whole tree
    By hankspears in forum C Programming
    Replies: 3
    Last Post: 04-29-2002, 11:40 AM