【数据结构】红黑树 – C++实现

前言

红黑树是一种自平衡的二叉查找树,效率极其之高,不过代码量惊人。

本文参考了skywang12345大佬的博客红黑树(四)之 C++的实现,有些图片也来自于他,若有侵权,请联系我们

介绍

红黑树(Red-Black tree,RBT)

该树满足二叉查找树性质,除此之外还有许多额外信息

红黑性:

  1. 每个结点非黑即红
  2. 根节点是黑色的
  3. NIL结点也是黑色的
  4. 如果一个结点是红色的,那么它的子结点必须是黑色的
  5. 从一个结点到该节点的子孙结点的所有路径上包含相同数目的黑结点

其实,红黑树和B树(或称4阶B树,即2-3-4树)有密切的联系,实际上它们本质相同,因为将红黑叔所有的红结点收缩到上层的父黑结点里,那么这样就是一棵2-3-4树。

由性质5,确保没有一条路径会比其他路径长出两倍。(证明见算法导论)因此红黑树非常优秀

实现

红黑树是依靠旋转来维持平衡的。

  1. 基本定义
    enum RBTColor{RED,BLACK};
    
    template<class T>
    class RBTNode{
    	public:RBTColor color;//color
    	public:T key;//key
    	public:RBTNode *left;//left child
    	public:RBTNode *right;//right child
    	public:RBTNode *p;//parent
    
    	//constructor
    	public:RBTNode(T key,RBTColor c,RBTNode *p,RBTNode *left,RBTNode *right){
    		this -> color = color;
    		this -> key = key;
    		this -> p = p;
    		this -> left = left;
    		this -> right = right;
    	}
    };
    
    template<class T>
    class RBT{
    	private:RBTNode<T> *root;//the Red-Black tree's root
    
    	public:RBT();//constructor
    	public:~RBT();//destructor
    
    	public:void preOrder();//preorder tree walk
    	public:void inOrder();//inorder tree walk
    	public:void postOrder();//postorder tree walk
    
    	public:RBTNode<T>* search(T key);//find a key in the Red-Black tree
    	public:RBTNode<T>* iterativeSearch(T key);//also find a key in the Red-Black tree,but it's iterative
    
    	public:T minimum();//return the minimum key
    	public:T maximum();//return the maximum key
    
    	public:RBTNode<T>* successor(RBTNode<T> *x);//find a node which its key >= x.key but it is min
    	public:RBTNode<T>* predecessor(RBTNode<T> *x);//find a node which its key <= x.key but it is max
    
    	public:void insert(T key);//insert a key into Red-Black tree
    
    	public:void remove(T key);//remove a key out of the Red-Black tree
    
    	public:void destroy();//delete the tree
    
    	public:void print();
    	
    	//inner interface
    	private:void preOrder(RBTNode<T> *root) const;
    	private:void inOrder(RBTNode<T> *root) const;
    	private:void postOrder(RBTNode<T> *root) const;
    
    	private:RBTNode<T>* search(RBTNode<T> *root,T key) const;
    	private:RBTNode<T>* iterativeSearch(RBTNode<T>* root,T key) const;
    
    	private:RBTNode<T>* minimum(RBTNode<T> *root);
    	private:RBTNode<T>* maximum(RBTNode<T> *root);
    
    	private:void leftRotate(RBTNode<T>* &root,RBTNode<T> *x);
    	private:void rightRotate(RBTNode<T>* &root,RBTNode<T> *y);
    
    	private:void insert(RBTNode<T>* &root,RBTNode<T> *node);
    	private:void insertFixup(RBTNode<T>* &root,RBTNode<T> *node);
    
    	private:void remove(RBTNode<T>* &root,RBTNode<T> *node);
    	private:void removeFixup(RBTNode<T>* &root,RBTNode<T> *node,RBTNode<T> *p);
    
    	private:void destroy(RBTNode<T>* &root);
    
    	private:void print(RBTNode<T>* root,T key,int direction);
    
    #define rb_p(r) ((r) -> p)
    #define rb_color(r) ((r) -> color)
    #define rb_is_red(r) ((r) -> color == RED)
    #define rb_is_black(r) ((r) -> color == BLACK)
    #define rb_set_black(r) do{(r) -> color = BLACK;}while(0)
    #define rb_set_red(r) do{(r) -> color = RED;}while(0)
    #define rb_set_p(r,pg) do{(r) -> p = (pg);}while(0)
    #define rb_set_color(r,c) do{(r) -> color = (c);}while(0)
    };

    RBTNode是结点,RBT是红黑树,有些函数重载过是为了面向对象,或是更好实现

    里面的宏定义是C语言版本留下的,因为Linux内的实现就用了此宏定义

  2. 左旋
    /* 
     *      px                              px
     *     /                               /
     *    x                               y                
     *   /  \    --(leftRotate)-->       / \                #
     *  lx   y                          x  ry     
     *     /   \                       /  \
     *    ly   ry                     lx  ly  
    */
    template<class T>
    void RBT<T>::leftRotate(RBTNode<T>* &root,RBTNode<T> *x){
    	//let x's right child to be y
    	RBTNode<T> *y = x -> right;
    
    	//let y's left child to be x's right child
    	//if y has the left child,let x to be y's parent
    	x -> right = y -> left;
    	if(y -> left != NULL){
    		y -> left -> p = x;
    	}
    
    	//let x's parent to be y's parent
    	y -> p = x -> p;
    
    	if(x -> p == NULL){//if x doesn't have parent
    		root = y;//let y to be root
    	}else{
    		if(x -> p -> left == x){//if x is the left child of its parent
    			x -> p -> left = y;//let y to be x's parent's left child
    		}else{//else x is the right child of its parent
    			x -> p -> right = y;//let y to be x's parrnt's right child
    		}
    	}
    
    	//let x to b y's left child
    	y -> left = x;
    
    	//let x'parent to be y
    	x -> p = y;
    }

    对x进行左旋,意味着x变成一个左结点,左旋只改变常数个指针操作,因此复杂度为Θ(1)

  3. 右旋
    /* 
     *            py                               py
     *           /                                /
     *          y                                x                  
     *         /  \    --(rightRotate)-->       /  \                    #
     *        x   ry                           lx   y  
     *       / \                                   / \                   #
     *      lx  rx                                rx  ry
    */
    template<class T>
    void RBT<T>::rightRotate(RBTNode<T>* &root,RBTNode<T> *y){
    	//let x to be current node's left child
    	RBTNode<T> *x = y -> left;
    
    	//let x's right child to be y's left child
    	//if x has the right child,let y to be x's right child's parent
    	y -> left = x -> right;
    	if(x -> right != NULL){
    		x -> right -> p = y;
    	}
    
    	//let y's parent to be x's parent
    	x -> p = y -> p;
    
    	if(y -> p == NULL){//if y doesn't have the parent
    		root = x;//let x to be the root
    	}else{
    		if(y == y -> p -> right){
    			y -> p -> right = x;
    		}else{
    			y -> p -> left = x;
    		}
    	}
    
    	x -> right = y;
    
    	y -> p = x;
    }

    与左旋对称

  4. 插入
    
    

    将一个结点插入到红黑树中会引起集合的动态变化,一定要修改数据结构来体现这个变化。

    可以先将红黑树当作一棵二叉查找树,将结点插入后,为其着色为红色,然后通过一系列旋转和重新着色来修正这棵树,使其满足红黑性。

    1. 红黑树当作一棵二叉查找树,将结点插入
      
      

      红黑树本身就是一棵二叉查找树,将结点插入后,仍然满足BST性,而旋转和着色的操作并不会改变BST性。

    2. 将插入的节点着色为”红色”
      
      

      将插入的结点着为红色,不会破坏红黑性5,这样可以少违背一条性质,易于编写。

    3. 通过修正操作使其成为红黑树
      
      

      在第二步中,我们没有违背性质5,但是违背了其他性质,

      1. 对于性质1,显然不会违背
      2. 对于性质2,显然不会违背,除外树为空
      3. 对于性质3,显然不会违背,插入操作不会影响NIL结点
      4. 性质4则可能违背
    4. 实现
      template<class T>
      void RBT<T>::insert(RBTNode<T>* &root,RBTNode<T> *node){
      	RBTNode<T> *y = NULL;
      	RBTNode<T> *x = root;
      
      	while(x != NULL){//this tree is also a BST,let's insert the node into BST
      		y = x;
      		if(node -> key < x -> key){
      			x = x -> left;
      		}else{
      			x = x -> right;
      		}
      	}
      
      	node -> p = y;
      
      	if(y != NULL){
      		if(node -> key < y -> key){
      			y -> left = node;
      		}else{
      			y -> right = node;
      		}
      	}else{
      		root = node;
      	}
      
      	node -> color = RED;//let the node's color to be red
      
      	insertFixup(root,node);//fix the tree
      }
      template<class T>
      void RBT<T>::insert(T key){
      	RBTNode<T> *z = NULL;
      	
      	if((z = new RBTNode<T>(key,BLACK,NULL,NULL,NULL)) == NULL){
      		return;//if falut to create a new node,return
      	}
      
      	insert(root,z);
      }

      内部接口:将node插入到root为根的树中

      外部接口:将key插入到树中。下面是插入的修正操作

      //when you insert a node into a RBT,that RBT totally will be unbalanced,this method is that let this tree to be RBT
      template<class T>
      void RBT<T>::insertFixup(RBTNode<T>* &root,RBTNode<T> *node){
      	RBTNode<T> *p,*gp;
      
      	while((p = rb_p(node)) && rb_is_red(p)){//if node has parent and parent's color is red
      		gp = rb_p(p);
      
      		if(p == gp -> left){//if parent is gparent's left child
      			{//case 1:uncle is red
      				RBTNode<T> *u = gp -> right;
      				if(u && rb_is_red(u)){
      					rb_set_black(u);
      					rb_set_black(p);
      					rb_set_black(gp);
      					node = gp;
      					continue;
      				}
      			}
      
      			if(p -> right == node){//case 2:uncle is black and it is to be the current node's right child
      				RBTNode<T> *tmp;
      				leftRotate(root,p);
      				tmp = p;
      				p = node;
      				node = tmp;
      			}
      
      			//case 3:uncle is black and it is to be the current node's left child
      			rb_set_black(p);
      			rb_set_red(gp);
      			rightRotate(root,gp);
      		}else{//if node's parent is gparent'sright child
      			{//case 1:uncle is red
      				RBTNode<T> *u = gp -> left;
      				if(u && rb_is_red(u)){
      					rb_set_black(u);
      					rb_set_black(p);
      					rb_set_red(gp);
      					node = gp;
      					continue;
      				}
      			}
      
      			if(p -> left == node){//case 2:uncle is black and it is to be the current node's left child
      				RBTNode<T> *tmp;
      				rightRotate(root,p);
      				tmp = p;
      				p = node;
      				node = tmp;
      			}
      
      			//case 3:uncle is black and it is to be the current node's right child
      			rb_set_black(p);
      			rb_set_red(gp);
      			leftRotate(root,gp);
      		}
      	}
      
      	rb_set_black(root);//let root's color to be black
      }

       

    5. 删除
      
      

      首先将红黑树当作一棵BST,删除该结点,然后修正

      1. 将红黑树当作一棵BST,删除该结点
        
        

        和BST删除一样,分3种情况

        1. 被删结点没有儿子,那么删掉就好了
        2. 被删结点有一个儿子,那么删掉,然后用这个儿子顶替它
        3. 被删结点有两个儿子,这种情况有点复杂
          1. 先找出它的后继结点
          2. 将它后继结点的内容复制给该结点
          3. 删除它的后继结点
            
            

            在这里,后继节点相当于替身,在将后继节点的内容复制给”被删除节点”之后,再将后继节点删除。这样就巧妙的将问题转换为”删除后继节点”的情况了,下面就考虑后继节点。 在”被删除节点”有两个非空子节点的情况下,它的后继节点不可能是双子非空。既然”的后继节点”不可能双子都非空,就意味着”该节点的后继节点”要么没有儿子,要么只有一个儿子。

          4. 如果后继结点有零个儿子,走情况1
          5. 如果后继结点有一个儿子,走情况2
      2. 修正
      3. 实现
        template<class T>
        void RBT<T>::removeFixup(RBTNode<T>* &root,RBTNode<T> *node,RBTNode<T> *p){
        	RBTNode<T> *o;
        
        	while((!node || rb_is_black(node)) && node != root){
        		if(p -> left == node){
        			 o = p -> right;
        			 if(rb_is_red(o)){
        			 	rb_set_black(o);
        			 	rb_set_red(p);
        			 	leftRotate(root,p);
        			 	o = p -> right;
        			 }
        
        			 if((!o -> left || rb_is_black(o -> left)) && (!o -> right || rb_is_black(o -> right))){
        			 	rb_set_red(o);
        			 	node = p;
        			 	p = rb_p(node);
        			 }else{
        			 	if(!o -> right || rb_is_black(o -> right)){
        			 		rb_set_black(o -> left);
        			 		rb_set_red(o);
        			 		rightRotate(root,o);
        			 		o = p -> right;
        			 	}
        
        			 	rb_set_color(o,rb_color(p));
        			 	rb_set_black(p);
        			 	rb_set_black(o -> right);
        			 	leftRotate(root,p);
        			 	node = root;
        			 	break;
        			 }
        		}else{
        			o = p -> left;
        			if(rb_is_red(o)){
        				rb_set_black(o);
        				rb_set_red(p);
        				rightRotate(root,p);
        				o = p -> left;
        			}
        			
        			if((!o -> left || rb_is_black(o -> left)) && (!o -> right || rb_is_black(o -> right))){
        				rb_set_red(o);
        				node = p;
        				p = rb_p(node);
        			}else{
        				if(!o -> left || rb_is_black(o -> left)){
        					rb_set_black(o -> right);
        					rb_set_red(o);
        					leftRotate(root,o);
        					o = p -> left;
        				}
        
        				rb_set_color(o,rb_color(p));
        				rb_set_black(p);
        				rb_set_black(o -> left);
        				rightRotate(root,p);
        				node = root;
        				break;
        			}
        		}
        	}
        
        	if(node){
        		rb_set_black(node);
        	}
        }
        
        template<class T>
        void RBT<T>::remove(RBTNode<T>* &root,RBTNode<T> *node){
        	RBTNode<T> *child,*p;
        	RBTColor color;
        
        	if((node -> left != NULL) && (node -> right != NULL)){//case 3:two child
        		RBTNode<T> *r = node;//replaced node
        
        		r = r -> right;//get successor node
        		while(r -> left != NULL){
        			r = r -> left;
        		}
        
        		if(rb_p(node)){//node isn't root
        			if(rb_p(node) -> left == node){
        				rb_p(node) -> left = r;
        			}else{
        				rb_p(node) -> right = r;
        			}
        		}else{
        			root = r;//update the root
        		}
        
        		child = r -> right;//child is replace's right child
        		p = rb_p(r);
        		color = rb_color(r);//save the color
        
        		if(p == node){//the node is its successor's parent
        			p = r;
        		}else{
        			if(child){//child isn't void
        				rb_set_p(child,p);
        			}
        
        			p -> left = child;
        
        			r -> right = node -> right;
        			rb_set_p(node -> right,r);
        		}
        
        		r -> p = node -> p;
        		r -> color = node -> color;
        		r -> left = node -> left;
        		node -> left -> p = r;
        
        		if(color == BLACK){
        			removeFixup(root,child,p);
        		}
        
        		delete node;
        		return;
        	}
        
        	if(node -> left != NULL){
        		child = node -> left;
        	}else{
        		child = node -> right;
        	}
        
        	p = node -> p;
        
        	color = node -> color;
        
        	if(child){
        		child -> p = p;
        	}
        
        	if(p){
        		if(p -> left == node){
        			p -> left = child;
        		}else{
        			p -> right = child;
        		}
        	}else{
        		root = child;
        	}
        
        	if(color == BLACK){
        		removeFixup(root,child,p);
        	}
        	delete node;
        }
        template<class T>
        void RBT<T>::remove(T key){
        	RBTNode<T> *node;
        
        	if((node = search(root,key)) != NULL){//find the node
        		remove(root,node);
        	}
        }

        修正操作:

        template<class T>
        void RBT<T>::removeFixup(RBTNode<T>* &root,RBTNode<T> *node,RBTNode<T> *p){
        	RBTNode<T> *o;
        
        	while((!node || rb_is_black(node)) && node != root){
        		if(p -> left == node){
        			 o = p -> right;
        			 if(rb_is_red(o)){//case 1:x's brother is red
        			 	rb_set_black(o);
        			 	rb_set_red(p);
        			 	leftRotate(root,p);
        			 	o = p -> right;
        			 }
        
        			 if((!o -> left || rb_is_black(o -> left)) && (!o -> right || rb_is_black(o -> right))){//case 2:x's brother is black and its two child are both black
        			 	rb_set_red(o);
        			 	node = p;
        			 	p = rb_p(node);
        			 }else{
        			 	if(!o -> right || rb_is_black(o -> right)){//case 3:x's brother is black and brother's left child is red,right child is black
        			 		rb_set_black(o -> left);
        			 		rb_set_red(o);
        			 		rightRotate(root,o);
        			 		o = p -> right;
        			 	}
        
        				//case 4:x'brother is black and its right child is red,left child whatever color it's(we don't care about that)
        			 	rb_set_color(o,rb_color(p));
        			 	rb_set_black(p);
        			 	rb_set_black(o -> right);
        			 	leftRotate(root,p);
        			 	node = root;
        			 	break;
        			 }
        		}else{
        			o = p -> left;
        			if(rb_is_red(o)){//case 1:x'brother is red
        				rb_set_black(o);
        				rb_set_red(p);
        				rightRotate(root,p);
        				o = p -> left;
        			}
        			
        			if((!o -> left || rb_is_black(o -> left)) && (!o -> right || rb_is_black(o -> right))){//case 2:x's brother is black,its children are both black
        				rb_set_red(o);
        				node = p;
        				p = rb_p(node);
        			}else{
        				if(!o -> left || rb_is_black(o -> left)){//case 3:x's brother is black,its left child is red,another one is black
        					rb_set_black(o -> right);
        					rb_set_red(o);
        					leftRotate(root,o);
        					o = p -> left;
        				}
        
        				//case 4:x'brother is black and its right child is red,left child whatever color it's(we don't care about that)
        				rb_set_color(o,rb_color(p));
        				rb_set_black(p);
        				rb_set_black(o -> left);
        				rightRotate(root,p);
        				node = root;
        				break;
        			}
        		}
        	}
        
        	if(node){
        		rb_set_black(node);
        	}
        }

         

    6. 完整实现:
      #include<iostream>
      #include<iomanip>
      
      enum RBTColor{RED,BLACK};
      
      template<class T>
      class RBTNode{
      	public:RBTColor color;//color
      	public:T key;//key
      	public:RBTNode *left;//left child
      	public:RBTNode *right;//right child
      	public:RBTNode *p;//parent
      
      	//constructor
      	public:RBTNode(T key,RBTColor c,RBTNode *p,RBTNode *left,RBTNode *right){
      		this -> color = color;
      		this -> key = key;
      		this -> p = p;
      		this -> left = left;
      		this -> right = right;
      	}
      };
      
      template<class T>
      class RBT{
      	private:RBTNode<T> *root;//the Red-Black tree's root
      
      	public:RBT();//constructor
      	public:~RBT();//destructor
      
      	public:void preOrder();//preorder tree walk
      	public:void inOrder();//inorder tree walk
      	public:void postOrder();//postorder tree walk
      
      	public:RBTNode<T>* search(T key);//find a key in the Red-Black tree
      	public:RBTNode<T>* iterativeSearch(T key);//also find a key in the Red-Black tree,but it's iterative
      
      	public:T minimum();//return the minimum key
      	public:T maximum();//return the maximum key
      
      	public:RBTNode<T>* successor(RBTNode<T> *x);//find a node which its key >= x.key but it is min
      	public:RBTNode<T>* predecessor(RBTNode<T> *x);//find a node which its key <= x.key but it is max
      
      	public:void insert(T key);//insert a key into Red-Black tree
      
      	public:void remove(T key);//remove a key out of the Red-Black tree
      
      	public:void destroy();//delete the tree
      
      	public:void print();
      	
      	//inner interface
      	private:void preOrder(RBTNode<T> *root) const;
      	private:void inOrder(RBTNode<T> *root) const;
      	private:void postOrder(RBTNode<T> *root) const;
      
      	private:RBTNode<T>* search(RBTNode<T> *root,T key) const;
      	private:RBTNode<T>* iterativeSearch(RBTNode<T>* root,T key) const;
      
      	private:RBTNode<T>* minimum(RBTNode<T> *root);
      	private:RBTNode<T>* maximum(RBTNode<T> *root);
      
      	private:void leftRotate(RBTNode<T>* &root,RBTNode<T> *x);
      	private:void rightRotate(RBTNode<T>* &root,RBTNode<T> *y);
      
      	private:void insert(RBTNode<T>* &root,RBTNode<T> *node);
      	private:void insertFixup(RBTNode<T>* &root,RBTNode<T> *node);
      
      	private:void remove(RBTNode<T>* &root,RBTNode<T> *node);
      	private:void removeFixup(RBTNode<T>* &root,RBTNode<T> *node,RBTNode<T> *p);
      
      	private:void destroy(RBTNode<T>* &root);
      
      	private:void print(RBTNode<T>* root,T key,int direction);
      
      #define rb_p(r) ((r) -> p)
      #define rb_color(r) ((r) -> color)
      #define rb_is_red(r) ((r) -> color == RED)
      #define rb_is_black(r) ((r) -> color == BLACK)
      #define rb_set_black(r) do{(r) -> color = BLACK;}while(0)
      #define rb_set_red(r) do{(r) -> color = RED;}while(0)
      #define rb_set_p(r,pg) do{(r) -> p = (pg);}while(0)
      #define rb_set_color(r,c) do{(r) -> color = (c);}while(0)
      };
      
      //constructor
      template<class T>
      RBT<T>::RBT(){
      	root = NULL;
      }
      
      //destructor
      template<class T>
      RBT<T>::~RBT(){
      	destroy();
      }
      
      //preorder tree walk,inner interface
      template<class T>
      void RBT<T>::preOrder(RBTNode<T> *root) const{
      	if(root != NULL){
      		std::cout << root -> key << " ";
      		preOrder(root -> left);
      		preOrder(root -> right);
      	}
      }
      //preorder tree walk,outer interface
      template<class T>
      void RBT<T>::preOrder(){
      	preOrder(root);
      }
      
      //inorder tree walk,inner interface
      template<class T>
      void RBT<T>::inOrder(RBTNode<T> *root) const{
      	if(root != NULL){
      		inOrder(root -> left);
      		std::cout << root -> key << " ";
      		inOrder(root -> right);
      	}
      }
      //inorder tree walk,outer interface
      template<class T>
      void RBT<T>::inOrder(){
      	inOrder(root);
      }
      
      //postorder tree walk,inner interface
      template<class T>
      void RBT<T>::postOrder(RBTNode<T> *root) const{
      	if(root != NULL){
      		postOrder(root -> left);
      		postOrder(root -> right);
      		std::cout << root -> key << " ";
      	}
      }
      //postorder tree walk,outer interface
      template<class T>
      void RBT<T>::postOrder(){
      	postOrder(root);
      }
      
      //find a key in the Red-Black tree,inner interface
      template<class T>
      RBTNode<T>* RBT<T>::search(RBTNode<T> *root,T key) const{
      	if(root == NULL || root -> key == key){
      		return root;
      	}
      
      	if(key < root -> key){
      		return search(root -> left,key);
      	}else{
      		return search(root -> right,key);
      	}
      }
      //find a key in the Red-Black tree,outer interface
      template<class T>
      RBTNode<T>* RBT<T>::search(T key){
      	search(root,key);
      }
      
      //also find a key in the Red-Black tree,but it's iterative,inner interface
      template<class T>
      RBTNode<T>* RBT<T>::iterativeSearch(RBTNode<T> *root,T key) const{
      	while((root != NULL) && (root -> key != key)){
      		if(key < root -> key){
      			root = root -> left;
      		}else{
      			root = root -> right;
      		}
      	}
      
      	return root;
      }
      
      //also find a key in the Red-Black tree,but it's iterative,outer interface
      template<class T>
      RBTNode<T>* RBT<T>::iterativeSearch(T key){
      	iterativeSearch(root,key);
      }
      
      //return the minimum key while the root is the "root",inner interface
      template<class T>
      RBTNode<T>* RBT<T>::minimum(RBTNode<T> *root){
      	if(root == NULL){
      		return NULL;
      	}
      
      	while(root -> left != NULL){
      		root = root -> left;
      	}
      
      	return root;
      }
      //return the minimum key,outer interface
      template<class T>
      T RBT<T>::minimum(){
      	RBTNode<T> *p = minimum(root);
      
      	if(p != NULL){
      		return p -> key;
      	}
      
      	return (T)NULL;
      }
      
      //return the maximum key while the root is the "root",inner interface
      template<class T>
      RBTNode<T>* RBT<T>::maximum(RBTNode<T> *root){
      	if(root == NULL){
      		return NULL;
      	}
      
      	while(root -> right != NULL){
      		root = root -> right;
      	}
      
      	return root;
      }
      //return the maximum key,outer interface
      template<class T>
      T RBT<T>::maximum(){
      	RBTNode<T> *p = maximum(root);
      	if(p != NULL){
      		return p -> key;
      	}
      
      	return (T)NULL;
      }
      
      //find a node which its key >= x.key but it is min
      template<class T>
      RBTNode<T>* RBT<T>::successor(RBTNode<T> *x){
      	//if x has right child,it's easy to know that x's successor is a subtree's minimum which its root is x'right child
      	if(x -> right != NULL){
      		return minimum(x -> right);
      	}
      
      	//else if x doesn't have right child so that there are two cases:
      	//case 1:x is a left child(whatever who its parent is) that x's successor is x's parent
      	//case 2:x is a right child(whatever who its parent is) that find x's lowest parent and that parent have to has a left child
      	RBTNode<T> *y = x -> p;
      	while((y != NULL) && (x == y -> right)){
      		x = y;
      		y = y -> p;
      	}
      
      	return y;
      }
      
      //find a node which its key <= x.key but it is max
      template<class T>
      RBTNode<T>* RBT<T>::predecessor(RBTNode<T> *x){
      	//if x has left child,it's easy to know that x's predecessor is a subtree's maximum which its root is x'right child
      	if(x -> left != NULL){
      		return maximum(x -> left);
      	}
      	
      	//else if x doesn't have left child so that there are two cases:
      	//case 1:x is a right child(whatever who its parent is) that x's predecessor is x's parent
      	//case 2:x is a left child(whatever who its parent is) that find x's lowest parent and that parent have to has a right child
      	RBTNode<T> *y = x -> p;
      	while((x != NULL) && (x == y -> left)){
      		x = y;
      		y = y -> p;
      	}
      
      	return y;
      }
      
      /* 
       *      px                              px
       *     /                               /
       *    x                               y                
       *   /  \    --(leftRotate)-->       / \                #
       *  lx   y                          x  ry     
       *     /   \                       /  \
       *    ly   ry                     lx  ly  
      */
      template<class T>
      void RBT<T>::leftRotate(RBTNode<T>* &root,RBTNode<T> *x){
      	//let x's right child to be y
      	RBTNode<T> *y = x -> right;
      
      	//let y's left child to be x's right child
      	//if y has the left child,let x to be y's parent
      	x -> right = y -> left;
      	if(y -> left != NULL){
      		y -> left -> p = x;
      	}
      
      	//let x's parent to be y's parent
      	y -> p = x -> p;
      
      	if(x -> p == NULL){//if x doesn't have parent
      		root = y;//let y to be root
      	}else{
      		if(x -> p -> left == x){//if x is the left child of its parent
      			x -> p -> left = y;//let y to be x's parent's left child
      		}else{//else x is the right child of its parent
      			x -> p -> right = y;//let y to be x's parrnt's right child
      		}
      	}
      
      	//let x to b y's left child
      	y -> left = x;
      
      	//let x'parent to be y
      	x -> p = y;
      }
      
      /* 
       *            py                               py
       *           /                                /
       *          y                                x                  
       *         /  \    --(rightRotate)-->       /  \                    #
       *        x   ry                           lx   y  
       *       / \                                   / \                   #
       *      lx  rx                                rx  ry
      */
      template<class T>
      void RBT<T>::rightRotate(RBTNode<T>* &root,RBTNode<T> *y){
      	//let x to be current node's left child
      	RBTNode<T> *x = y -> left;
      
      	//let x's right child to be y's left child
      	//if x has the right child,let y to be x's right child's parent
      	y -> left = x -> right;
      	if(x -> right != NULL){
      		x -> right -> p = y;
      	}
      
      	//let y's parent to be x's parent
      	x -> p = y -> p;
      
      	if(y -> p == NULL){//if y doesn't have the parent
      		root = x;//let x to be the root
      	}else{
      		if(y == y -> p -> right){
      			y -> p -> right = x;
      		}else{
      			y -> p -> left = x;
      		}
      	}
      
      	x -> right = y;
      
      	y -> p = x;
      }
      
      //when you insert a node into a RBT,that RBT totally will be unbalanced,this method is that let this tree to be RBT
      template<class T>
      void RBT<T>::insertFixup(RBTNode<T>* &root,RBTNode<T> *node){
      	RBTNode<T> *p,*gp;
      
      	while((p = rb_p(node)) && rb_is_red(p)){//if node has parent and parent's color is red
      		gp = rb_p(p);
      
      		if(p == gp -> left){//if parent is gparent's left child
      			{//case 1:uncle is red
      				RBTNode<T> *u = gp -> right;
      				if(u && rb_is_red(u)){
      					rb_set_black(u);
      					rb_set_black(p);
      					rb_set_black(gp);
      					node = gp;
      					continue;
      				}
      			}
      
      			if(p -> right == node){//case 2:uncle is black and it is to be the current node's right child
      				RBTNode<T> *tmp;
      				leftRotate(root,p);
      				tmp = p;
      				p = node;
      				node = tmp;
      			}
      
      			//case 3:uncle is black and it is to be the current node's left child
      			rb_set_black(p);
      			rb_set_red(gp);
      			rightRotate(root,gp);
      		}else{//if node's parent is gparent'sright child
      			{//case 1:uncle is red
      				RBTNode<T> *u = gp -> left;
      				if(u && rb_is_red(u)){
      					rb_set_black(u);
      					rb_set_black(p);
      					rb_set_red(gp);
      					node = gp;
      					continue;
      				}
      			}
      
      			if(p -> left == node){//case 2:uncle is black and it is to be the current node's left child
      				RBTNode<T> *tmp;
      				rightRotate(root,p);
      				tmp = p;
      				p = node;
      				node = tmp;
      			}
      
      			//case 3:uncle is black and it is to be the current node's right child
      			rb_set_black(p);
      			rb_set_red(gp);
      			leftRotate(root,gp);
      		}
      	}
      
      	rb_set_black(root);//let root's color to be black
      }
      
      template<class T>
      void RBT<T>::insert(RBTNode<T>* &root,RBTNode<T> *node){
      	RBTNode<T> *y = NULL;
      	RBTNode<T> *x = root;
      
      	while(x != NULL){//this tree is also a BST,let's insert the node into BST
      		y = x;
      		if(node -> key < x -> key){
      			x = x -> left;
      		}else{
      			x = x -> right;
      		}
      	}
      
      	node -> p = y;
      
      	if(y != NULL){
      		if(node -> key < y -> key){
      			y -> left = node;
      		}else{
      			y -> right = node;
      		}
      	}else{
      		root = node;
      	}
      
      	node -> color = RED;//let the node's color to be red
      
      	insertFixup(root,node);//fix the tree
      }
      template<class T>
      void RBT<T>::insert(T key){
      	RBTNode<T> *z = NULL;
      	
      	if((z = new RBTNode<T>(key,BLACK,NULL,NULL,NULL)) == NULL){
      		return;//if falut to create a new node,return
      	}
      
      	insert(root,z);
      }
      
      template<class T>
      void RBT<T>::removeFixup(RBTNode<T>* &root,RBTNode<T> *node,RBTNode<T> *p){
      	RBTNode<T> *o;
      
      	while((!node || rb_is_black(node)) && node != root){
      		if(p -> left == node){
      			 o = p -> right;
      			 if(rb_is_red(o)){//case 1:x's brother is red
      			 	rb_set_black(o);
      			 	rb_set_red(p);
      			 	leftRotate(root,p);
      			 	o = p -> right;
      			 }
      
      			 if((!o -> left || rb_is_black(o -> left)) && (!o -> right || rb_is_black(o -> right))){//case 2:x's brother is black and its two child are both black
      			 	rb_set_red(o);
      			 	node = p;
      			 	p = rb_p(node);
      			 }else{
      			 	if(!o -> right || rb_is_black(o -> right)){//case 3:x's brother is black and brother's left child is red,right child is black
      			 		rb_set_black(o -> left);
      			 		rb_set_red(o);
      			 		rightRotate(root,o);
      			 		o = p -> right;
      			 	}
      
      				//case 4:x'brother is black and its right child is red,left child whatever color it's(we don't care about that)
      			 	rb_set_color(o,rb_color(p));
      			 	rb_set_black(p);
      			 	rb_set_black(o -> right);
      			 	leftRotate(root,p);
      			 	node = root;
      			 	break;
      			 }
      		}else{
      			o = p -> left;
      			if(rb_is_red(o)){//case 1:x'brother is red
      				rb_set_black(o);
      				rb_set_red(p);
      				rightRotate(root,p);
      				o = p -> left;
      			}
      			
      			if((!o -> left || rb_is_black(o -> left)) && (!o -> right || rb_is_black(o -> right))){//case 2:x's brother is black,its children are both black
      				rb_set_red(o);
      				node = p;
      				p = rb_p(node);
      			}else{
      				if(!o -> left || rb_is_black(o -> left)){//case 3:x's brother is black,its left child is red,another one is black
      					rb_set_black(o -> right);
      					rb_set_red(o);
      					leftRotate(root,o);
      					o = p -> left;
      				}
      
      				//case 4:x'brother is black and its right child is red,left child whatever color it's(we don't care about that)
      				rb_set_color(o,rb_color(p));
      				rb_set_black(p);
      				rb_set_black(o -> left);
      				rightRotate(root,p);
      				node = root;
      				break;
      			}
      		}
      	}
      
      	if(node){
      		rb_set_black(node);
      	}
      }
      
      template<class T>
      void RBT<T>::remove(RBTNode<T>* &root,RBTNode<T> *node){
      	RBTNode<T> *child,*p;
      	RBTColor color;
      
      	if((node -> left != NULL) && (node -> right != NULL)){//case 3:two child
      		RBTNode<T> *r = node;//replaced node
      
      		r = r -> right;//get successor node
      		while(r -> left != NULL){
      			r = r -> left;
      		}
      
      		if(rb_p(node)){//node isn't root
      			if(rb_p(node) -> left == node){
      				rb_p(node) -> left = r;
      			}else{
      				rb_p(node) -> right = r;
      			}
      		}else{
      			root = r;//update the root
      		}
      
      		child = r -> right;//child is replace's right child
      		p = rb_p(r);
      		color = rb_color(r);//save the color
      
      		if(p == node){//the node is its successor's parent
      			p = r;
      		}else{
      			if(child){//child isn't void
      				rb_set_p(child,p);
      			}
      
      			p -> left = child;
      
      			r -> right = node -> right;
      			rb_set_p(node -> right,r);
      		}
      
      		r -> p = node -> p;
      		r -> color = node -> color;
      		r -> left = node -> left;
      		node -> left -> p = r;
      
      		if(color == BLACK){
      			removeFixup(root,child,p);
      		}
      
      		delete node;
      		return;
      	}
      
      	if(node -> left != NULL){
      		child = node -> left;
      	}else{
      		child = node -> right;
      	}
      
      	p = node -> p;
      
      	color = node -> color;
      
      	if(child){
      		child -> p = p;
      	}
      
      	if(p){
      		if(p -> left == node){
      			p -> left = child;
      		}else{
      			p -> right = child;
      		}
      	}else{
      		root = child;
      	}
      
      	if(color == BLACK){
      		removeFixup(root,child,p);
      	}
      	delete node;
      }
      template<class T>
      void RBT<T>::remove(T key){
      	RBTNode<T> *node;
      
      	if((node = search(root,key)) != NULL){//find the node
      		remove(root,node);
      	}
      }
      
      template<class T>
      void RBT<T>::destroy(RBTNode<T>* &root){
      	if(root == NULL){
      		return;
      	}
      
      	if(root -> left != NULL){
      		return destroy(root -> left);
      	}
      
      	if(root -> right != NULL){
      		return destroy(root -> right);
      	}
      
      	delete root;
      	root = NULL;
      }
      
      template<class T>
      void RBT<T>::destroy(){
      	destroy(root);
      }
      
      template<class T>
      void RBT<T>::print(RBTNode<T>* root, T key, int direction){
          if(root != NULL){
              if(direction==0){//root is the root node
                  std::cout << std::setw(2) << root -> key << "(B) is root" << std::endl;
              }else{//root is the child node
                  std::cout << std::setw(2) << root -> key <<  (rb_is_red(root) ? "(R)":"(B)") << " is " << std::setw(2) << key << "'s "  << std::setw(12) << (direction == 1 ? "right child" : "left child") << std::endl;
      		}
      		
              print(root -> left,root -> key,-1);
              print(root -> right,root -> key,1);
          }
      }
      
      template<class T>
      void RBT<T>::print(){
          if (root != NULL)
              print(root,root -> key,0);
      }