rb-tree.txt

红黑树的算法

	 int ret =true;
	 while(x !=0)					//从根节点开始，向下寻找适当的插入点
	 {
		 y =x;
		 ret =key > x->key;
		 x =ret? x->left :x->right; 
	 }								//离开 while 之后，x 指向插入点，y 指向插入点之父节点
	
	 TreeNode<type>* j =y; 			//令 j 指向插入点之父节点
	 if(ret)						//如果离开 while 时的 ret 为真(表示遇到大的，插入左侧)
		 if(j ==begin()){
			 //cout<<"lizhi--+ __insert first be invoked"<<endl;
			 return __insert(x,y,key);
			}
		 else
			 decrement(j);
	if(j->key > key) 				// 小于新值（表示遇「小」，将安插于右侧）
	{
		//cout<<"lizhi--+ __insert second be invoked"<<endl;
		return __insert(x,y,key);
	}

	// 进行至此，表示新值一定与树中键值重复，那么就不该插入新值。
	return RBT_STATUS_OK;

}

RbtStatus __insert(TreeNode<type>* x_, TreeNode<type>* y_, type& v) {
	// 参数x_ 为新值安插点，参数y_ 为安插点之父节点，参数v 为新值。
  TreeNode<type>* x = (TreeNode<type>*) x_;
  TreeNode<type>* y = (TreeNode<type>*) y_;
  TreeNode<type>* z;
	//cout<<"lizhi--+ __insert begin"<<endl;
  // key_compare 是键值大小比较准则。应该会是个 function object。
  if (y == header || x != 0 || v >y->key) {
    //cout<<"lizhi--+ __insert 0"<<endl;
    //z = new TreeNode<type>(v);  // 产生一个新节点
    z = new TreeNode<type>(v);  // 产生一个新节点
    //cout<<"lizhi--+ __insert 01"<<endl;
    y->left = z;          // 这使得当 y 即为 header时，leftmost() = z
    //cout<<"lizhi--+ __insert 02"<<endl;
    
    if (y == header) {
    	//cout<<"lizhi--+ __insert 03"<<endl;
      root() = z;
      rightmost() = z;
    }
    else if (y == leftmost())	// 如果y为最左节点
    {
    	//cout<<"lizhi--+ __insert 04"<<endl;
      leftmost() = z;           	// 维护leftmost()，使它永远指向最左节点
    }
  }
  else {
  	//cout<<"lizhi--+ __insert 1"<<endl;
    //z = new TreeNode<type>(v);		// 产生一个新节点
    z = new TreeNode<type>(v);  // 产生一个新节点
    
    y->right = z;				// 令新节点成为安插点之父节点 y 的右子节点
    if (y == rightmost())
      rightmost() = z;          	// 维护rightmost()，使它永远指向最右节点
  }
  
  //cout<<"lizhi--+ __insert 2"<<endl;
  z->parent = y;		// 设定新节点的父节点
  z->left = 0;		// 设定新节点的左子节点
  z->right = 0; 		// 设定新节点的右子节点
  z->color = RED;
  //cout<<"lizhi--+ __insert 3"<<endl;
                   // 新节点的颜色将在 insertFixup() 设定（并调整）
  insertFixup(z);	// 参数一为新增节点，参数二为 root
  ++node_count;		// 节点数累加
  //cout<<"lizhi--+ __insert end"<<endl;
  return RBT_STATUS_OK;	// 传回一个迭代器，指向新增节点
}

void insertFixup(TreeNode<type> *x) {
    // maintain red-black tree balance
    // after inserting node x

    // check red-black properties
	//1. 如果 x =root 为根，while 不执行，直接返回
	//2. 如果 x->parent->color == RED 则要处理，否则不用处理
	//

	TreeNode<type>* father =x->parent;
//	
	
	while (x != root() && father->color == RED) {
        // we have a violation
		TreeNode<type>* grandfather =father->parent;
		//1. father is left
        if (father == grandfather->left)	
		{
            TreeNode<type> *rightuncle = grandfather->right;
			//1.1 right uncle is red, father is red, now grandfather must be black
			//so, only changing the color is ok.
            if (rightuncle && rightuncle->color == RED)
			{
                // uncle is RED
                father->color = BLACK;
                rightuncle->color = BLACK;
                grandfather->color = RED;
                x = grandfather;	//?????	哦，在这之后，要继续循环的
            }
			//1.2 right uncle is black, father is red, now grandfather must be black
			//
			else
			{
                // uncle is BLACK
                if (x == father->right) {
                    // make x a left child
                    x = father;
                    rotateLeft(x);
                }
                // recolor and rotate
                father->color = BLACK;
                grandfather->color = RED;
                rotateRight(grandfather);
            }
        }// if (father ==
		//2. father is right
		else {
            // mirror image of above code
            TreeNode<type> *leftuncle = grandfather->left;
			//2.1 left uncle is red
            if (leftuncle && leftuncle->color == RED) 
			{

                // uncle is RED
                father->color = BLACK;
                leftuncle->color = BLACK;
                grandfather->color = RED;
                x = grandfather;
            }
			//2.2 left uncle is black
			else
			{
                // uncle is BLACK
                if (x == father->left) {
                    x = father;
                    rotateRight(x);
                }
                father->color = BLACK;
                grandfather->color = RED;
                rotateLeft(grandfather);
            }
        }// 2. end
    }// while
    root()->color = BLACK;
}

RbtStatus Erase(TreeNode<type>* z)
{
	TreeNode<type> *x, *y;

    if (z->left == 0 || z->right == 0) {
        // y has a 0 node as a child
        y = z;
    } else {
        // find tree successor with a 0 node as a child
        y = z->right;
        while (y->left != 0) y = y->left;
    }

    // x is y's only child
    if (y->left != 0)
        x = y->left;
    else
        x = y->right;

    // remove y from the parent chain
    x->parent = y->parent;
    if (y->parent)
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    else
        root() = x;

    if (y != z) {
        z->key = y->key;
    }


    if (y->color == BLACK)
        deleteFixup (x);

    delete y;
	y =NULL;
	node_count --;
    return RBT_STATUS_OK;
}


type* Find(const type& key)
{
	TreeNode<type> *current;
    current = root();

    while(current != 0) {
        if(key ==current->key) {
            return &(current->key);
        } else {
            current = (key > current->key) ?
                current->left : current->right;
        }
    }
    return NULL;
}

//void Destroy()
//{
//	Delete(root());
//	node_count =0;
//	
//	header->parent =NULL;
//	header->color =RED;
//	header->left =header;
//	header->right =header;
//}
//void Delete(TreeNode<type> *p)
//{
//	if (p == NULL) return;
//
//    Delete(p->left);
//    Delete(p->right);
//    delete p;
//	p =NULL;
//}


void Inorder(TreeNode<type>  *p)
{
	if (p == NULL) return;
    Inorder(p->left);
    cout<<"lizhi--+ Inorder-> "<<p->GetKey()<<endl;
    Inorder(p->right);
	
}

friend ostream& operator<<(ostream& out, RBTree<type>& tree)
{
	TreeNode<type> * p =tree.root();
	if(p ==NULL)		return out<<"the tree root is null"<<endl;
	tree.Inorder(p);
	return out<<"###-------- tree out over --------###"<<endl;
}

void increment(TreeNode<type>*& node)
{
    if (node->right != 0) {		// 如果有右子节点。状况(1)
      node = node->right;		// 就向右走
      while (node->left != 0)	// 然后一直往左子树走到底
        node = node->left;		// 即是解答
    }
    else
	{					// 没有右子节点。状况(2)
      TreeNode<type>* y = node->parent;	// 找出父节点
    
      while (node == y->right) {	// 如果现行节点本身是个右子节点，
		 node = y;				// 就一直上溯，直到「不为右子节点」止。
		 y = y->parent;
      }
      if (node->right != y){		// 「若此时的右子节点不等于此时的父节点」
        node = y;				// 状况(3) 此时的父节点即为解答。
	  }
                                // 否则此时的node 为解答。状况(4)
    }//else

    // 注意，以上判断「若此时的右子节点不等于此时的父节点」，是为了应付一种
    // 特殊情况：我们欲寻找根节点的下一节点，而恰巧根节点无右子节点。
    // 当然，以上特殊作法必须配合 RB-tree 根节点与特殊之header 之间的
    // 特殊关系。
}

  // 以下其实可实作于 operator-- 内，因为再无他处会呼叫此函式了。
void decrement(TreeNode<type>*& node)
  {
    if (node->color == RED &&	// 如果是红节点，且
        node->parent->parent == node)		// 父节点的父节点等于自己，
      node = node->right;				// 状况(1) 右子节点即为解答。
    // 以上情况发生于node为header时（亦即 node 为 end() 时）。
    // 注意，header 之右子节点即 mostright，指向整棵树的 max 节点。
    else if (node->left != 0) {			// 如果有左子节点。状况(2)
      TreeNode<type>* y = node->left;			// 令y指向左子节点
      while (y->right != 0)				// 当y有右子节点时
        y = y->right;					// 一直往右子节点走到底
      node = y;						// 最后即为答案
    }
    else {							// 既非根节点，亦无左子节点。
      TreeNode<type>* y = node->parent;			// 状况(3) 找出父节点
      while (node == y->left) {			// 当现行节点身为左子节点
        node = y;						// 一直交替往上走，直到现行节点
        y = y->parent;					// 不为左子节点
      }
      node = y;						// 此时之父节点即为答案
    }
  }

};

#endif