RBTree.h

#include <iostream>

template <typename T>
class RBTree
{
public:
	RBTree();
	bool insert(const T&);
	bool del(const T&);
	void show() { 
		Mid_Order(root);
	}
	
private:
	
	enum { RED, BLACK };
	
typedef struct _node
	{
		bool color;
		T data;
		struct _node * p, *left, *right;
	}Node;

	Node *root;
	Node *nil;
	unsigned int Size;
	
	void RB_Ins_Fix(Node *);
	void RB_Del_Fix(Node *);
	void Left_Rotate(Node *);
	void Right_Rotate(Node *);

	void Replace(Node *, Node *);
	void Mid_Order(const Node *);
};

template <typename T>
RBTree<T>::RBTree()
{
	Node *p = new Node;
	Size = 0;
	nil = new Node;
	nil->color = BLACK;
	nil->p = nil->left = nil->right = NULL;
	root = nil;
}

template <typename T>
bool RBTree<T>::insert(const T& val)
{
	Node *pf = nil;
	Node *pc = root;
	while (pc != nil)
	{
		pf = pc;
		if (val >= pc->data)
			pc = pc->right;
		else
			pc = pc->left;
	}
	Node *pn = new Node;
	pn->data = http://www.mamicode.com/val;>

main.cpp
#include <iostream>
#include "RBTree.h"
using namespace std;
int main()
{     
	RBTree<int> a;
	for (int i = 0; i < 10; ++i)
	{	
		a.insert(i);
		a.show();
		cout << endl;
	}
		
	for (int i = 0; i < 10; ++i)
	{
		a.del(i);
		a.show();
		cout << endl;
	}

	cout << endl;
	cout << "ok\n";
	cin.get();
	cin.get();
	return 0;
}


二叉树 - 红黑树