red black tree implementation in c++

rb.cpp

#ifndef _RED_BLACK_ //protection from multiple inclusion
#define _RED_BLACK_
struct NODE
{
	int key;
	int color; //black = 0 and red = 1
	NODE* p; //pointer to parent
	NODE* r; //pointer to right child
	NODE* l; //pointer to left child
};
NODE NULL_NODE = {-1,0,0,0,0}; //sentinal
class RBT //assumed no equal keys
{
	private:
		NODE* ROOT;
	public:
		RBT()
		{
			ROOT = 0; //initally points to nothing
		}
		NODE* search(int k) const //search for node with key k
		{
			if(ROOT == 0) return &NULL_NODE; //no tree
			NODE* CURRENT = ROOT;
			for(;;)
			{
				if(k == CURRENT->key) return CURRENT;
				else if(k < CURRENT->key)
				{
					if(CURRENT->l == 0) return &NULL_NODE; //no node with given key
					else CURRENT = CURRENT->l;
				}
				else if(k > CURRENT->key)
				{
					if(CURRENT->r == 0) return &NULL_NODE; //no node with given key
					else CURRENT = CURRENT->r;
				}
			}
		}
		NODE* minimum(NODE& N) const
		{
			if(ROOT == 0) return &NULL_NODE; //no tree
			NODE* CURRENT = search(N.key); //pointer to sub-tree root
			while(CURRENT->l != 0) CURRENT = CURRENT->l; //find minimun
			return CURRENT;
		}
		bool insert_node(int k) //true if successful, false otherwise.
		{
			NODE* insert = new NODE;
			//using new instead of just declaring as NODE insert because memory can be freed
			//in delete_node and insert->key looks more intuitive (well, to me anyway) than insert.key
			insert->key = k;
			insert->color = 1; //red is default
			insert->p = 0; //if it is the root, parent is null pointer
			insert->l = 0; /*	So that leaves will have	*/
			insert->r = 0; /*	null pointers for children	*/
			if(ROOT == 0) //first insert
			{
				ROOT = insert;
				return true;
			}
			for(;;)
			{
				if(k == insert->key) break;
				else if(k < insert->key)
				{
					if(insert->l != 0) insert = insert->l;
					else 
					{
						insert->l = insert;
						insert->p = insert;
						break;
					}
				}
				else if(k > insert->key)
				{
					if(insert->r != 0) insert = insert->r;
					else
					{
						insert->r = insert;
						insert->p = insert;
						break;
					}
				}
			}
			//fixing up violations
			while(insert->p != ROOT && insert->p->color == 1)
			{
				if(insert->p == insert->p->p->l) // insert is in the left subtree
				{
					NODE* aunt = insert->p->p->r; // chose aunt insted of uncle because aunt has one
					if(aunt->color == 1)	// character less than uncle. I am not sexist.
					{
						//case 1
						insert->color = 0;
						aunt->color = 0;
						insert->p->p->color = 1;
						insert = insert->p->p;
						continue;
					}
					else if(insert = insert->p->p->r)
					{
						//case 2
						left_rotate(insert->p->key); //rotations defined below
					}
					else
					{
						//case 3
						insert->p->color = 0;	// recoloring first and rotating next because
						insert->p->p->color = 1; // rotating changes parent-child relations
						right_rotate(insert->p->p->key);
						return true;
					}
				}
				else // insert is in the right subtree
				{
					// same code with l interchanged with r. Copy-pasted (you can prolly tell by the cringy comment in the next line)
					NODE* aunt = insert->p->p->l; // chose aunt insted of uncle because aunt has one
					if(aunt->color == 1)		  // character less than uncle. I am not a sexist.
					{
						//case 1
						insert->color = 0;
						aunt->color = 0;
						insert->p->p->color = 1;
						insert = insert->p->p;
						continue;
					}
					else if(insert = insert->p->p->l)
					{
						//case 2
						right_rotate(insert->p->key); //rotations defined below
					}
					else
					{
						//case 3
						insert->p->color = 0;	// recoloring first and rotating next because
						insert->p->p->color = 1; // rotating changes parent-child relations
						left_rotate(insert->p->p->key);
						return true;
					}
				}
			}
			return false; //couldn't insert
		}
		void transplant(NODE* u, NODE* v)
		{
			if(u->p == 0) ROOT = v; // u is the root
			else if(u == u->p->l) u->p->l = v; // u is a left child
			else u->p->r = v; // u is a right child
			v->p = u->p;
		}
		bool delete_node(int k) //true if successful, false otherwise.
		{
			NODE* del = search(k); //search for the node to be deleted
			int original_color = del->color;
			NODE* y = del;
			NODE* x; // x becomes either y's right child or 0
			if(del->l == 0) // no left child
			{
				x = del->r; 
				transplant(del,del->r);
			}
			else if(del->r == 0) // no right child
			{
				x = del->l;
				transplant(del,del->l);
			}
			else // both children
			{
				y = minimum(*del->r); // successor
				original_color = y->color;
				x = y->r;
				if(y->p->key == del->key) x->p == y; //del's right child turned out to be its successor
				else
				{
					transplant(y,y->r);
					y->r = del->r;
					y->r->p = y;
				}
				y->l = del->l;
				y->l->p = y;
				y->color = del->color;
			}
			//fixing up violations
			if(original_color == 0)
			{
				NODE* aunt;
				while(x != ROOT && x->color == 0)
				{
					if(x->p->l) //x a the left child
					{
						aunt = x->p->r;
						if(aunt->color == 1)
						{
							// case 1
							aunt->color = 0;
							x->p->color = 1;
							left_rotate(x->p->key);
							aunt = x->p->r;
						}
						if(aunt->l->color == 0 && aunt->r->color == 0)
						{
							//case 2
							aunt->color = 1;
							x = x->p;
						}
						else if(aunt->r->color == 0)
						{
							//case 3
							aunt->l->color = 0;
							aunt->color = 1;
							right_rotate(aunt->key);
							aunt = x->p->r;
						}
						//case 4
						aunt->color = x->p->color;
						x->p->color = 0;
						aunt->r->color = 0;
						left_rotate(x->p->key);
						x = ROOT;
					}
					// interchange l and r
					else
					{
						aunt = x->p->l;
						if(aunt->color == 1)
						{
							// case 1
							aunt->color = 0;
							x->p->color = 1;
							left_rotate(x->p->key);
							aunt = x->p->l;
						}
						if(aunt->r->color == 0 && aunt->l->color == 0)
						{
							//case 2
							aunt->color = 1;
							x = x->p;
						}
						else if(aunt->l->color == 0)
						{
							//case 3
							aunt->r->color = 0;
							aunt->color = 1;
							left_rotate(aunt->key);
							aunt = x->p->l;
						}
						//case 4
						aunt->color = x->p->color;
						x->p->color = 0;
						aunt->l->color = 0;
						left_rotate(x->p->key);
						x = ROOT;
					}
				}
				x->color = 0;
			}
			return false; //couldn't delete
		}
		void left_rotate(int k)
		{
			NODE* x = search({k}); //node to be rotated
			NODE* y = x->r; //set y
			x->r = y->l; //y's left subtree is x's right subtree
			if(y->l != 0) y->l->p = x;
			y->p = x->p; //linking parent
			if(x->p == 0) ROOT = y;
			else if(x == x->p->l) x->p->l =y;
			else x->p->r = y;
			y->l = x; //put x on y's left
			x->p = y;
		}
		// same with x and y interchanged
		void right_rotate(int k)
		{
			NODE* x = search({k}); //node to be rotated
			NODE* y = x->l; //set y
			x->l = y->r; //y's right subtree is x's left subtree
			if(y->r != 0) y->r->p = x;
			y->p = x->p; //linking parent
			if(x->p == 0) ROOT = y;
			else if(x == x->p->r) x->p->r =y;
			else x->p->l = y;
			y->r = x; //put x on y's right
			x->p = y;
		}
};
#endif

#include
#include "rb.cpp"
using namespace std;
int main()
{
RBT r;
r.insert_node(1);
r.insert_node(2);
r.insert_node(3);
r.insert_node(4);
r.insert_node(5);
cout<<r.search(2)<<endl;
cout<<r.search(6)<<endl;
}

used above code to test