Thread: red black tree delete() without using successor() help...

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    15

    red black tree delete() without using successor() help...

    i checked google and most of the rbt delete implementation are using successor
    is there a way to do it without the successor???
    he told the class to follow the book "intro to algorithms" but he wrote his version w/o even looking at the book and he wrote his answer w/o successor...
    ive implemented my own with successor but my professor is forcing the class to do it w/o it

    heres my codes
    Code:
    void deleteRb(string data)
    	{
    		treeNode* y;
    		treeNode* z = searchDelete(data); //searchDelete finds where the node is to be deleted
    		treeNode* x;
    
    		if ( z->left == NULL || z->right == NULL )
    			y=z;
    		else 
    			y = treeSuccessor(z);
    		if (y->left != NULL)
    			x= y->left;
    		else
    			x= y->right;
    		x->parent = y->parent;
    		if ( y->parent == NULL)
    			root = x;
    		else if (y = y->parent->left)
    			y->parent->left = x;
    		else
    			y->parent->right = x;
    		if ( y != z)
    			z->data = y->data;
    		if ( y->red = false)
    			deleteFixUp(x);
    	}
    ^the delete()

    Code:
    treeNode* treeSuccessor(treeNode* x)
    	{
    		if (x->right != NULL)
    			return treeMinimum (x->right);
    
    		treeNode* y;
    		y = x->parent;
    		while ( y != NULL)
    		{
    			if ( x == y->right)
    			{
    				x=y;
    				y=y->parent;
    			}
    
    		return y;
    		}
    	}
    ^successor()

    can someone help me...

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >is there a way to do it without the successor???
    Yes and no. If you mean without finding the successor at some point in the algorithm, no, because that's an integral part of correctly maintaining the tree's structure and invariants. If you mean without taking an extra step of finding the successor, absolutely. In fact, I have such an example in the top-down deletion function here which is described in simpler detail here.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problem in creating a tree
    By Lorin_sz in forum C Programming
    Replies: 1
    Last Post: 09-26-2005, 01:24 PM
  2. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  3. delete whole tree
    By hankspears in forum C Programming
    Replies: 3
    Last Post: 04-29-2002, 11:40 AM
  4. memory management...
    By master5001 in forum Game Programming
    Replies: 24
    Last Post: 01-07-2002, 05:50 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM