性质
- 节点是红色或黑色
- 根节点是黑色
- 所有叶子都是黑色。(叶子是NUIL节点)
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
- 如果一个节点的一个子节点是黑色,那么这个节点一定有2个节点。
插入情景
删除情景
Code
enum Color{red,black}; template<typename T> struct BiTNode{ BiTNode *left; BiTNode *right; BiTNode *parent; Color color; T val; int son; BiTNode():son(0){} BiTNode(T val):val(val),son(1){ color=red; parent=NULL; left=NULL; right=NULL; } BiTNode *grandpa(){ if(parent==NULL)return NULL; return parent->parent; } BiTNode* sibling(){ if(parent->left==this)return parent->right; return parent->left; } BiTNode* uncle(){ if(grandpa()==NULL)return NULL; if(grandpa()->left==parent)return grandpa()->right; return grandpa()->left; } }; template<typename T,typename node=BiTNode<T>> class rb_tree{ public: rb_tree():n(0),root(NULL){ NIL=new node(); NIL->color=black; } ~rb_tree(){clear(root);delete NIL;} rb_tree(T* bg,T* ed):n(0),root(NULL){ NIL=new node(); NIL->color=black; while(bg!=ed)insert(*bg++); } bool empty()const{return n==0;} int size()const{return n;} void insert(const T& key){insert(root,key);++n;} void erase(const T& key){remove(root,key);--n;} bool find(const T& key)const{return search(root,key)!=NULL;} void clear(){clear(root);n=0;} T& MIN(){return MIN(root)->val;} T& MAX(){return MAX(root)->val;} T kth(int k){ if(k>n)return -1; node *p=root; while(p!=NIL){ if(p->left!=NIL){ if(k<=p->left->son)p=p->left; else{ k-=p->left->son; if(k==1)return p->val; k--; p=p->right; } }else{ if(k==1)return p->val; k--; p=p->right; } } } private: #define is_red(p) ((p)->color==red) #define is_black(p) ((p)->color==black) #define set_red(p) ((p)->color=red) #define set_black(p) ((p)->color=black) void clear(node* &rt) { if(rt==NIL)return; clear(rt->left); clear(rt->right); delete rt; } node* search(node* rt,const T& key) { if(rt==NULL)return NULL; node* p=rt; while(p!=NIL) { if(key==p->val)return p; if(key<p->val)p=p->left; else p=p->right; } return NULL; } node* MIN(node* rt) { node* p=rt; while(p->left!=NIL)p=p->left; return p; } node* MAX(node* rt) { node* p=rt; while(p->right!=NIL)p=p->right; return p; } node* suf(node* rt) { if(rt->right!=NIL)return MIN(rt->right); node* p=rt->parent; while(p&&rt==p->right)rt=p,p=p->parent; return p; } node* pre(node* rt) { if(rt->left!=NIL)return MAX(rt->left); node* p=rt->parent; while(p&&rt==p->left)rt=p,p=p->parent; return p; } void insert(node* &rt,const T& key){ if(rt==NULL){ rt=new node(key); rt->left=rt->right=NIL; set_black(rt); return; } push(rt,key); } int num(node* &p){return p==NIL?0:p->son;} void up_son(node* &p){p->son=num(p->left)+num(p->right)+1;} bool lson(node* &p){return p->parent->left==p;} bool rson(node* &p){return p->parent->right==p;} void push(node* rt,const T& key){ if(key<=rt->val){ if(rt->left!=NIL)push(rt->left,key); else{ node* p=new node(key); rt->left=p; p->parent=rt; p->left=p->right=NIL; up_insert(p); } }else if(key>rt->val){ if(rt->right!=NIL)push(rt->right,key); else{ node* p=new node(key); rt->right=p; p->parent=rt; p->left=p->right=NIL; up_insert(p); } } up_son(rt); } void up_insert(node *p){ if(p->parent==NULL){ root=p; set_black(p); return; } if(is_black(p->parent))return; if(is_red(p->uncle())){ set_black(p->parent); set_black(p->uncle()); set_red(p->grandpa()); up_insert(p->grandpa());return; } if(lson(p)&&rson(p->parent)){ rotate_right(p); p=p->right; } else if(rson(p)&&lson(p->parent)){ rotate_left(p); p=p->left; } if(lson(p)&&lson(p->parent)){ set_black(p->parent); set_red(p->grandpa()); rotate_right(p->parent); } else if(rson(p)&&rson(p->parent)){ set_black(p->parent); set_red(p->grandpa()); rotate_left(p->parent); } } void rotate_left(node *p){ node *grandpa=p->grandpa(); node *parent=p->parent; node *left=p->left; parent->right=left; if(left!=NIL)left->parent=parent; p->left=parent; parent->parent=p; p->parent=grandpa; if(grandpa==NULL)root=p; else{ if(grandpa->left==parent) grandpa->left=p; else grandpa->right=p; } up_son(parent);up_son(p); } void rotate_right(node *p){ node *grandpa=p->grandpa(); node *parent=p->parent; node *right=p->right; parent->left=right; if(right!=NIL)right->parent=parent; p->right=parent; parent->parent=p; p->parent=grandpa; if(grandpa==NULL)root=p; else{ if(grandpa->left==parent) grandpa->left=p; else grandpa->right=p; } up_son(parent);up_son(p); } void remove(node* p,int key){ if(key<p->val)remove(p->left,key); else if(key>p->val)remove(p->right,key); else { if(p->right==NIL){ remove_one(p); return; } node *replace=suf(p); std::swap(p->val,replace->val); remove_one(replace); } up_son(p); } void remove_one(node *p){ node *child=p->left==NIL?p->right:p->left; if(p->parent==NULL&&p->left==NIL&&p->right==NIL){ p=NULL; root=p;return; } if(p->parent==NULL){ delete p; child->parent=NULL; root=child; set_black(root);return; } if(lson(p))p->parent->left=child; else p->parent->right=child; child->parent=p->parent; if(is_black(p)){ if(is_red(child))set_black(child); else up_remove(child); } delete p; } void up_remove(node *p){ if(p->parent==NULL){ set_black(p); return; } if(is_red(p->sibling())){ set_red(p->parent); set_black(p->sibling()); if(lson(p))rotate_left(p->parent); else rotate_right(p->parent); } if(is_black(p->parent)&&is_black(p->sibling()) \ &&is_black(p->sibling()->left)&&is_black(p->sibling()->right)){ set_red(p->sibling()); up_remove(p->parent); }else if(is_red(p->parent)&&is_black(p->sibling()) \ &&is_black(p->sibling()->left)&&is_black(p->sibling()->right)){ set_red(p->sibling()); set_black(p->parent); } else{ if(is_black(p->sibling())){ if(lson(p)&&is_red(p->sibling()->left) \ &&is_black(p->sibling()->right)){ set_red(p->sibling()); set_black(p->sibling()->left); rotate_right(p->sibling()->left); }else if(rson(p)&&is_black(p->sibling()->left) \ &&is_red(p->sibling()->right)){ set_red(p->sibling()); set_black(p->sibling()->right); rotate_left(p->sibling()->right); } } p->sibling()->color=p->parent->color; set_black(p->parent); if(lson(p)){ set_black(p->sibling()->right); rotate_left(p->sibling()); }else{ set_black(p->sibling()->left); rotate_right(p->sibling()); } } } public: vector<T> DLR(){vector<T>v;DLR(root,v);return v;} vector<T> LDR(){vector<T>v;LDR(root,v);return v;} vector<T> LRD(){vector<T>v;LRD(root,v);return v;} vector<T> bfs(){vector<T>v;bfs(root,v);return v;} private: void bfs(node *Tree,vector<T>&v) { if(Tree==NULL)return; queue<node*>q; q.push(Tree); while(!q.empty()) { node *p=q.front(); v.push_back(p->val); q.pop(); if(p->left!=NIL)q.push(p->left); if(p->right!=NIL)q.push(p->right); } } void DLR(node *Tree,vector<T>&v) { if(Tree==NULL||Tree==NIL){return ;} v.push_back(Tree->val); DLR(Tree->left,v); DLR(Tree->right,v); } void LDR(node *Tree,vector<T>&v) { if(Tree==NULL||Tree==NIL){return ;} LDR(Tree->left,v); v.push_back(Tree->val); LDR(Tree->right,v); } void LRD(node *Tree,vector<T>&v) { if(Tree==NULL||Tree==NIL){return ;} LRD(Tree->left,v); LRD(Tree->right,v); v.push_back(Tree->val); } private: node *root,*NIL; int n; };