main.cpp

本实验完成的功能是给定一个区间找出其区间树 开发环境采用VC

#ifndef RBTREE__JOHN__DMRC
#define RBTREE__JOHN__DMRC
#include <cstdlib>
#include <iostream.h>

//using namespace std;

template <class T>
class Node
{
public:
	Node() : maxEndpoint(-1), lowEndpoint(-1), highEndpoint(-1), red(false), exist(false), left(NULL), right(NULL), parent(NULL){}
	Node(T low,T high) : lowEndpoint(low), highEndpoint(high), maxEndpoint(high), red(true), exist(true), left(NULL), right(NULL), parent(NULL){}

	bool isExist() { return this ->exist; }
	bool isNULL() { return !this ->exist; }
	bool getColor() { return this ->red; }
	bool isRed(){ return this ->red; }
	bool isBlack() { return !this ->red; }
 
	void setColor(bool c) { this ->red = c; }
	void setRed() { this ->red = true; }
	void setBlack() { this ->red = false; }

	T maxEndpoint;
	T lowEndpoint;
	T highEndpoint;
	bool red;
	bool exist;
	Node<T>* left;
	Node<T>* right;
	Node<T>* parent;
};
template <class T, class E>	
class RBTree
{
public:
	RBTree() : root(NULL){}
	~RBTree();
    void inorder();
	bool Insert(T low, T high);
	T RBTreeSearch(T low, T high){};
	void iterativeRBTreeSearch(T low, T high);
	void fixMax(){fixUpMax(root);}
private:
	void fixUpMax(Node<T> * p);
	void inorder( Node<T>* );   
	Node<T>* RBTreeSearch(Node<T>* ,T low, T high){};
	Node<T>* iterativeRBTreeSearch(Node<T>* ,T low, T high);
	void delete_tree( Node<T>* );
	void left_rotate(Node<T>*);
	void right_rotate(Node<T>*);
	void insert_fixup(Node<T>*);
	void delete_fixup(Node<T>*){};
private:
	Node<T>* root;
};
#endif
template <class T, class E>
void RBTree<T, E>::delete_tree(Node<T>* p)
{
	if(p ->left)
		this ->delete_tree(p ->left);
	if(p ->right)
		this ->delete_tree(p ->right);
	delete p;
}

template <class T, class E>
RBTree<T, E>::~RBTree()
{
	this ->delete_tree(this ->root);
}
template <class T, class E>
void RBTree<T, E>::inorder()
{
   inorder(root);
   cout<<'\n';
}

//树de遍历                 

template <class T,  class E>
void RBTree<T, E>::inorder(Node<T> * p) //
{
    if (p->exist)//!= NULL
	{
        inorder(p->left);
        //visit(p);
		cout <<"lowEndpoint: "<<p->lowEndpoint<< ' ';
		cout <<"highEndpoint: "<<p->highEndpoint << ' ';
		cout <<"maxEndpoint: "<<p->maxEndpoint <<endl;

        inorder(p->right);
	}
}

template <class T, class E>
void RBTree<T, E>::iterativeRBTreeSearch(T low, T high)	//iterative search
{
	if ((iterativeRBTreeSearch(root,low,high))->exist)
	{
		cout<<"lowEndpoint: "<<( iterativeRBTreeSearch( root,low,high ) )->lowEndpoint<<' ';
		cout<<"highEndpoint: "<<( iterativeRBTreeSearch( root,low,high ) )->highEndpoint<<' ';
		cout<<"maxEndpoint: "<<( iterativeRBTreeSearch( root,low,high ) )->maxEndpoint<<endl;
		//return ( ( iterativeRBTreeSearch( root,low,high ) )->data );
	}
	else
		cout<<"no such interval! \n";
}

template <class T, class E>
Node<T>* RBTree<T, E>::iterativeRBTreeSearch(Node<T>* x,T low, T high)
{
	while (x->exist && (x->lowEndpoint>high||x->highEndpoint<low) )
	{
		//if (k<x->data)
		if ( x->left->exist && x->left->maxEndpoint>=low )
			x=x->left;
		else
			x=x->right;
	}
	return x;
}


// 调整max域               

template <class T,  class E>
void RBTree<T, E>::fixUpMax(Node<T> * p) //
{
    if (p->exist)//!= NULL
	{
        fixUpMax(p->left);
        fixUpMax(p->right);
        if ( ( p->right->exist ) && ( p->highEndpoint < p->right->maxEndpoint ) )
		{	
			Node<T>* y = p;
			while ( ( y->right->exist ) && ( y->highEndpoint < y->right->maxEndpoint ) )
			{
				p->maxEndpoint=y->right->maxEndpoint;
				y=y->right;
			}
		}
		else
			p->maxEndpoint=p->highEndpoint;
	}
}
template <class T, class E>
bool RBTree<T, E>::Insert(T low, T high)
{
	if(this ->root == NULL || this ->root ->isNULL())
	{
		if(this ->root)
			delete this ->root;

		this ->root = new Node<T>(low, high);

		this ->root ->left = new Node<T>();
		this ->root ->left ->parent = this ->root;

		//set the right node as a nil pointer
		this ->root ->right = new Node<T>();
		this ->root ->right ->parent = this ->root;

		//set the root node as black color
		this ->root ->setBlack();
		return true;
	}
	Node<T>* p = this ->root;
	while(p!=NULL)
	{
		//The data of the nodes must be different
		if ((low == p->lowEndpoint) && (high == p->highEndpoint))
			return false;

		if(low < p->lowEndpoint)
		{
			//left subtree
			if(p ->left ->isNULL())
			{
				delete p ->left;
				p ->left = new Node<T>(low,high);
				p ->left ->parent = p;

				p ->left ->left = new Node<T>();
				p ->left ->left ->parent = p ->left;

				p ->left ->right = new Node<T>();
				p ->left ->right ->parent = p ->left;

				this ->insert_fixup(p ->left);
				return true;
			}
			else
				p = p ->left;
		}
		else
		{
			if( p->right ->isNULL() )
			{
				delete p->right;

				p ->right = new Node<T>(low,high);
				p ->right ->parent = p;

				p ->right ->left = new Node<T>();
				p ->right ->left ->parent = p ->left;

				p ->right ->right = new Node<T>();
				p ->right ->right ->parent = p ->left;

				this ->insert_fixup(p ->right);
				return true;
			}
			else
				p = p ->right;
		}
	}
	return false;
}


template <class T, class E>
void RBTree<T, E>::insert_fixup(Node<T>* z)
{
	Node<T>* y;	

	while(z ->parent && z ->parent ->isRed())
	{
		if(z ->parent == z ->parent ->parent ->left)
		{
			
			y = z ->parent ->parent ->right;
			if(y ->isRed())
			{
				//case 1
				z ->parent ->setBlack();
				y ->setBlack();
				z ->parent ->parent ->setRed();
				z = z ->parent ->parent;
			}
			else
			{ 
				//combine case2 with case3
				if(z == z ->parent ->right)
				{
					// case 2 ( fall through to case 3 )
					z = z ->parent;
					this ->left_rotate(z);
				}
				// case 3
				z ->parent ->setBlack();
				z ->parent ->parent ->setRed();
				this ->right_rotate(z ->parent ->parent);
			}
		}

		//there is 3 cases in the case that parent[z] is the right node of p[p[z]]
		else
		{
			y = z ->parent ->parent ->left;
			if(y ->isRed())
			{
				// case 4
				z ->parent ->setBlack();
				y ->setBlack();
				z ->parent ->parent ->setRed();
				z = z ->parent ->parent;
			}
			else
			{ 
				if(z == z ->parent ->left)
				{
					// case 5 ( fall through to case 6 )
					z = z ->parent;
					this ->right_rotate(z);
				}
				// case 6
				z ->parent ->setBlack();
				z ->parent ->parent ->setRed();
				this ->left_rotate(z ->parent ->parent);
			}
		}
		fixUpMax(z);	//fix up maxEndpoint
	}
	
	this ->root ->setBlack();
}
template <class T, class E>
void RBTree<T, E>::left_rotate(Node<T>* x)
{
	Node<T>* y = x ->right;

	x ->right = y ->left;
	if(y ->left)
		y ->left ->parent = x;

	y ->parent = x ->parent;
	if(x ->parent == NULL)
		this ->root = y;
	else
	{
		if(x == x ->parent ->left)
			x ->parent ->left = y;
		else
			x ->parent ->right = y;
	}

	y ->left = x;
	x ->parent = y;
}

template <class T, class E>
void RBTree<T, E>::right_rotate(Node<T>* x)
{
	Node<T>* y = x ->left;

	x ->left = y ->right;
	if(y ->right)
	y ->right ->parent = x;

	y ->parent = x ->parent;
	if(x ->parent == NULL)
		this ->root = y;
	else
	{
		if(x == x ->parent ->left)
			x ->parent ->left = y;
		else
			x ->parent ->right = y;
	}
	// set relation
	y ->right = x;
	x ->parent = y;
}
int main(int argc, char *argv[])
{
	RBTree<int,int> test;
	//int i,j;
	//for (i=0;i<7;i++)
	//	test.Insert(i,i+2);
	test.Insert(16,21);
	test.Insert(8,9);
	test.Insert(5,8);
	test.Insert(0,3);
	test.Insert(6,10);
	test.Insert(15,23);
	test.Insert(25,30);
	test.Insert(26,26);
	test.Insert(17,19);
	test.Insert(19,20);
	//test.Insert(2,5);
	//test.Insert(3,7);
	//test.fixMax();
	//cout<<"before delete '6'"<<endl;
	test.inorder();
	//test.Delete(6,6);
	//cout<<'\n';
	//test.fixMax();
	test.iterativeRBTreeSearch(5,6);
	//cout<<
	//cout<<"\nafter delete '6'"<<endl;
	//test.inorder();
	//cout<<j<<endl;
    
    system("PAUSE");
    return EXIT_SUCCESS;
}