这个比Avl树更复杂,借鉴别人写出来。
#include<iostream>using namespace std;
template<class T>
class Node
{ public:T key;bool color;//Red--1,Black--0Node* parent;Node* leftChild;Node* rightChild;Node(T data,bool color,Node* p, Node* l,Node* r):key(data),color(color),parent(p),leftChild(l),rightChild(r){} ;// friend class RedBlackTree<T>;
};
template<class T>
class RedBlackTree
{ Node<T>* NIL;Node<T>* root;public:RedBlackTree(T data=0){ NIL=new Node<T>(0,false,NULL,NULL,NULL);root=NIL;}Node<T>* GetRoot(){return root;}Node<T>* GetMin(Node<T>* x);Node<T>* FindElement(Node<T>* x,T k);void LeftRotate(Node<T>* x);void RightRotate(Node<T>* y);void RBInsert(T data);void RBInsertFixup(Node<T>* z);void RBDelete(T data);void RBDeleteFixUp(Node<T>* x);
};