Help -- Red Black Tree

This is a discussion on Help -- Red Black Tree within the C++ Programming forums, part of the General Programming Boards category; hello, I hope everyone is fine. =) I have made a red black tree code, with the basic functionalities of ...

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    112

    Help -- Red Black Tree

    hello,
    I hope everyone is fine. =)
    I have made a red black tree code, with the basic functionalities of insertion, deletion and Search. Presently, I am not getting any error, but when the code reaches the while loop of insertfixup it crashes or whatever ( it pops up a window xstring and points to the following code
    int compare(const _Elem *_Ptr) const
    { // compare [0, _Mysize) with [_Ptr, <null>)
    _DEBUG_POINTER(_Ptr);
    return (compare(0, this->_Mysize, _Ptr, _Traits::length(_Ptr)));
    }


    Kindly help me with it. I am pasting the code here

    Code:
    #include<iostream>
    #include<string>
    
    using namespace std;
    
    class Node
    {
    public:
    
    	 string data;
    	 Node* left;
    	 Node* right;
    	 Node* parent;
    	 string color;
    	
    	 Node()
    	 {
    		 right = NULL;
    		 left  = NULL;
    		 parent= NULL;
    	 }
    	 
     };
    
    class RBT
    {
    	Node* root;
    
    public:
    	RBT()
    	{
    		root = NULL;
    		
    	}
    
    
    	void rotateLeft( Node* x )
    	{
    		Node* y = x->right;
    		x->right= y ->left;
    		y->left->parent= x;
    		y->parent = x->parent;
    		if ( x->parent == NULL)
    			root = y;
    		else if (x == x->parent->left)
    			x->parent->left=y;
    		else 
    			x->parent->right = y;
    		y->left   = x;
    		x->parent = y;
    	}
    
    	void rotateRight(Node* x)
    	{
    		Node* y = x->left;
    		x->left= y ->right;
    		y->right->parent= x;
    		y->parent = x->parent;
    		if ( x->parent == NULL)
    			root = y;
    		else if (x == x->parent->left)
    			x->parent->right=y;
    		else 
    			x->parent->left = y;
    		y->right=x;
    		x->parent=y;
    	}
    
    	void insertFixUp(Node* z)
    	{
    		
    		Node* y;
    		//cout<<"Hello";
    		
    			while( z->parent->color == "RED")
    			{
    			//cout<<"i";
    			if ( z->parent == z->parent->parent->left)
    			{
    				y= z->parent->parent->right;
    			
    				if (y->color== "RED")
    				{
    					z->parent->color = "BLACK";
    					y->color = "BLACK";
    					z->parent->parent->color = "RED";
    					z= z->parent->parent;
    
    				}
    			
    					
    				
    				else
    					if (z == z->parent->right)
    					
    					{	
    						z = z->parent;
    						rotateLeft(z);
    					}
    				
    					z->parent->color = "BLACK";
    					z->parent->parent->color = "RED";
    					rotateRight(z->parent->parent);
    					
    	
    			}
    			else
    			{		
    				z = z->parent;
    				rotateRight(z);
    			}
    					
    				z->parent->color = "BLACK";
    				z->parent->parent->color = "RED";
    				rotateLeft(z->parent->parent);
    			
    			
    		}
    		
    			//cout<<"Hello2";
    			root->color = "BLACK";
    		
    	}
    
    
    	void insert(string data)
    	{
    		Node* z = new Node;
    		z->data = data;
    		
    
    		Node* y = NULL;
    		Node* x = root;
    		while (x != NULL)
    		{
    			y=x;
    			
    			if (z->data < x->data)
    				x = x->left;
    			else 
    				x = x->right;
    		}
    		z->parent = y;
    		
    		if ( y == NULL)
    			root = z;
    		else
    		
    			if (z->data < y->data)
    				y->left = z;
    			else
    				y->right= z;
    			
    		z->left = NULL;
    		z->right = NULL;
    		z->color = "RED";
    		//z->parent = y;
    		insertFixUp(z);
    	}
    	
    
    	void inOrder(Node* abc)
    	{
    		if(abc != NULL)	
    		{
    		    if(abc->left)
    			inOrder(abc->left);
    			cout<<" "<<abc->data<<" ";
    		    if( abc->right)
    			inOrder(abc->right);
    		 }
    		else return;
    	}
    
    	void printInOrder()
    	{
    		inOrder(root);
    	}
    
    	Node* searchDelete(string data)
    	{
    		Node* y=root;
    		Node* x= root;
    		
    		while ( x != NULL )
    		{
    			if  (x->data == data)
    			{	
    				return x;
    			}
    			//y=1;	break;	}
    			
    			if (data < x->data)
    				x= x->left;
    			else 
    				x=x->right;
    		}
    
    	//return y;
    	}
    
    	void deleteRb(string data)
    	{
    		Node* y;
    		Node* z = searchDelete(data);
    		Node* 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->color == "BLACK" )
    			deleteFixUp(x);
    	}
    
    	void deleteFixUp( Node* x )
    	{
    		Node* w;
    
    		while ( x != root && x->color == "BLACK" )
    		{
    			if ( x = x->parent->left )
    			{
    				w = x->parent->right;
    				if ( w->color == "RED")
    				{
    					w->color = "RED";
    					x->parent->color = "RED";
    					rotateLeft(x->parent);
    					w = x->parent->right;
    				}
    
    				if ( w->left->color == "BLACK" && w->right->color == "BLACK")
    				{
    					w->color = "RED";
    					x = x->parent;
    				}
    
    				else 
    					if ( w->right->color == "BLACK" )
    					{
    						w->left->color = "BLACK";
    						w->color = "RED";
    						rotateRight(w);
    						w = x->parent->right;
    					}
    
    					w->color= x->parent->color;
    					x->parent->color = "BLACK";
    					w->right->color  = "BLACK";
    					rotateLeft(x->parent);
    					x = root;
    			}
    
    			else
    			{
    				w->right->color = "BLACK";
    				w->color = "RED";
    				rotateLeft(w);
    				w = x->parent->left;
    				w->color = x->parent->color;
    				x->parent->color = "BLACK";
    				w->left->color  = "BLACK";
    				rotateRight(x->parent);
    				x = root;
    			}
    		}
    		root->color = "BLACK";
    	}
    	
    	Node* treeMinimum(Node* x)
    	{
    		while (x->left != NULL)
    			x= x->left;
    
    		return x;
    	}
    
    	Node* treeSuccessor(Node* x)
    	{
    		if (x->right != NULL)
    			return treeMinimum (x->right);
    
    		Node* y;
    		y = x->parent;
    		while ( y != NULL)
    		{
    			if ( x == y->right)
    			{
    				x=y;
    				y=y->parent;
    			}
    
    		return y;
    		}
    	}
    
    	
    };
    
    
    int main()
    {
    	
    	RBT rbt;
    	Node z;
    	
    	rbt.insert("C");
    	rbt.insert("A");
    	rbt.insert("B");
    	rbt.insert("D");
    	rbt.printInOrder();
    	rbt.deleteRb("A");
    
    	system("Pause");
    
    	return 0;
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I'm guessing that means you are following a null pointer. For instance, if z is the root of the tree, then z->parent is NULL, meaning z->parent->color can't happen.

  3. #3
    Registered User
    Join Date
    Apr 2011
    Posts
    3
    Look at the code I have wrote, though it is in C, can give you clue what is wrong.

    SourceForge.net Repository - [clibutils] Contents of /src/c_rb.c

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,541
    @avinashdongre - stop digging up old threads just to spam your site!
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. I need some ideas please>>
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 08-23-2002, 01:55 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21