//file RBTree.h
//written by saturnman
#ifndef _RB_TREE_H_
#define _RB_TREE_H_
#include
#include
#include
#include
using namespace std;
template
class RB_Tree
{
private:
RB_Tree(const RB_Tree& input){}
const RB_Tree& operator=(const RB_Tree& input){}
private:
enum COLOR{RED,BLACK};
class RB_Node
{
public:
RB_Node()
{
RB_COLOR = BLACK;
right = NULL;
left = NULL;
parent = NULL;
}
COLOR RB_COLOR;
RB_Node* right;
RB_Node* left;
RB_Node* parent;
KEY key;
U data;
};
public:
RB_Tree()
{
this->m_nullNode = new RB_Node();
this->m_root = m_nullNode;
this->m_nullNode->right = this->m_root;
this->m_nullNode->left = this->m_root;
this->m_nullNode->parent = this->m_root;
this->m_nullNode->RB_COLOR = BLACK;
}
bool Empty()
{
if(this->m_root == this->m_nullNode)
{
return true;
}
else
{
return false;
}
}
//find node whos key equals to key,else find the insert point;
RB_Node* find(KEY key)
{
RB_Node* index = m_root;
while(index != m_nullNode)
{
if(keykey)
{
index = index->left;
}
else if(key>index->key)
{
index = index->right;
}
else
{
break;
}
}
return index;
}
bool Insert(KEY key,U data)
{
RB_Node* insert_point = m_nullNode;
RB_Node* index = m_root;
while(index!=m_nullNode)
{
insert_point = index;
if(keykey)
{
index = index->left;
}
else if(key>index->key)
{
index = index->right;
}
else
&