rbtree.cpp

我的红黑树的c++实现。主要特点是可以用dot工具把红黑树画出来

        x = y->rchild;
    }
    else
    {
        if (NIL == y->rchild)
        {
            x = y->lchild;
        }
        else
        {
            y = y->rchild;
            while (NIL != y->lchild)
                y = y->lchild;
            x = y->rchild;
        }
    }
    if (y != z)
    {
        z->lchild->father = y;
        y->lchild = z->lchild;
        if (y != z->rchild)
        {
            x_father = y->father;
            if (NIL != x)
                x->father = y->father;
            y->father->lchild = x;
            y->rchild = z->rchild;
            z->rchild->father = y;
        }
        else
        {
            x_father = y;
        }
        if (root == z)
        {
            root = y;
        }
        else if (z == z->father->lchild)
        {
            z->father->lchild = y;
        }
        else
        {
            z->father->rchild = y;
        }
        y->father = z->father;
        bool color = y->color;
        y->color = z->color;
        z->color = color;
        y = z;
    }
    else
    {
        x_father = y->father;
        if (NIL != x)
            x->father = y->father;
        if (root == z)
        {
            root = y;
        }
        else if (z == z->father->lchild)
        {
            z->father->lchild = x;
        }
        else
        {
            z->father->rchild = x;
        }

    }

    if (BLACK == y->color)
    {
        delFixup(x);
    }
    delete y;
	return true;
}


bool rbtree::delNode() //删除函数的无参重载，可以自己输入要删除的key值
{
	int key;
	cout<<"Please enter the key you want to delete : ";
	cin>>key;
    rbtnode *x, *y, *z, *x_father;
    // 首先查找需要删除的节点
    z = find(key);
    if (NIL == z)
        return false;
    y = z, x = NIL, x_father = NIL;
    // y是x按照中序遍历树的后继
    if (NIL == y->lchild)
    {
        x = y->rchild;
    }
    else
    {
        if (NIL == y->rchild)
        {
            x = y->lchild;
        }
        else
        {
            y = y->rchild;
            while (NIL != y->lchild)
                y = y->lchild;
            x = y->rchild;
        }
    }

    if (y != z)
    {
        z->lchild->father = y;
        y->lchild = z->lchild;
        if (y != z->rchild)
        {
            x_father = y->father;
            if (NIL != x)
                x->father = y->father;
            y->father->lchild = x;
            y->rchild = z->rchild;
            z->rchild->father = y;
        }
        else
        {
            x_father = y;
        }
        if (root == z)
        {
            root = y;
        }
        else if (z == z->father->lchild)
        {
            z->father->lchild = y;
        }
        else
        {
            z->father->rchild = y;
        }
        y->father = z->father;
        bool color = y->color;
        y->color = z->color;
        z->color = color;
        y = z;
    }
    else
    {
        x_father = y->father;
        if (NIL != x)
            x->father = y->father;
        if (root == z)
        {
            root = y;
        }
        else if (z == z->father->lchild)
        {
            z->father->lchild = x;
        }
        else
        {
            z->father->rchild = x;
        }

    }

    if (BLACK == y->color)
    {
        delFixup(x);
    }
    delete y;
	return true;
}

void rbtree::delFixup(rbtnode *x)
{
    rbtnode *w = NULL;

    while (x != root && (NIL == x || BLACK == x->color))
    {
        if (x == x->father->lchild && x->father->lchild != NULL)                                // 如果x是左子树
        {
            w = x->father->rchild;                                                                // w是x的兄弟结点
            if (RED == w->color)                                                                // 如果w的颜色是红色
            {
                w->color = BLACK;
                x->father->color = RED;
                leftRotate(x->father);
                w = x->father->rchild;
            }
            if ((NIL == w->lchild  || BLACK == w->lchild->color) &&
                (NIL == w->rchild || BLACK == w->rchild->color))
            {
                w->color = RED;
                x = x->father;
                x->father = x->father->father;
            }
            else
            {
                if (NIL == w->rchild || BLACK == w->rchild->color)
                {
                    if (NIL != w->lchild)
                        w->lchild->color = BLACK;
                    w->color = RED;
                    rightRotate(w);
                    w = x->father->rchild;
                }
                w->color = x->father->color;
                x->father->color = BLACK;
                if (NIL != w->rchild)
                    w->rchild->color  = BLACK;
                leftRotate(x->father);
                break;
            }
        }
        else if(x == x->father->rchild && x->father->rchild != NULL)
        {
            w = x->father->lchild;                                                                // w是x的兄弟结点
            if (RED == w->color)                                                                // 如果w的颜色是红色                                               
            {
                w->color = BLACK;
                x->father->color = RED;
                rightRotate(x->father);
                w = x->father->lchild;
            }
            if ((NIL == w->lchild  || BLACK == w->lchild->color) &&
                (NIL == w->rchild || BLACK == w->rchild->color))
            {
                w->color = RED;
                x = x->father;
                x->father = x->father->father;
            }
            else
            {
                if (NIL == w->lchild || BLACK == w->lchild->color)
                {
                    if (NIL != w->rchild)
                        w->rchild->color = BLACK;
                    w->color = RED;
                    leftRotate(w);
                    w = x->father->lchild;
                }

                w->color = x->father->color;
                x->father->color = BLACK;
                if (NIL != w->lchild)
                    w->lchild->color  = BLACK;
                rightRotate(x->father);
                break;
            }
        }
		else break;
    }

    x->color = BLACK;
}

void rbtree::toJpg(string name)
{
	dot d;
	int count = 0;
	rbtnode * node = root;
	stack<rbtnode *> s;
	while(1)
	{
		while(NULL != node)
		{
			s.push(node);
			string *str;
			stringstream c;
			if(NIL == node)
			{
				c<<count;
				str = new string("NIL"+c.str());
				count++;
			}
			else
			{
				c<<node->key;
				str = new string(c.str());
			}
			string clr;
			if(node->color == RED) clr = "red";
			else clr = "gray40";
			d.dotInsert(str, clr);
			node = node->lchild;
		}
		if(!s.empty())
		{
			node = s.top();
			s.pop();
			node = node->rchild;
		}
		else break;
	}
	node = root;
	count = 0;
	while(1)
	{		
		while(NULL != node)
		{
			s.push(node);
			if(NIL != node)
			{
				stringstream ss;
				ss<<node->key;
				string *from = new string(ss.str());
				stringstream sl;
				stringstream sr;
				string *lto;
				string *rto;
				if (NIL != node->lchild)
				{
					sl<<node->lchild->key;
					lto = new string(sl.str());
				}
				else
				{
					sl<<count;
					lto = new string("NIL"+sl.str());
					count++;
				}
				if (NIL != node->rchild)
				{
					sr<<node->rchild->key;
					rto = new string(sr.str());
				}
				else
				{
					sr<<count;
					rto = new string("NIL"+sr.str());
					count++;
				}
				d.dotInsert(from, lto, "");
				d.dotInsert(from, rto, "");
			}
			node = node->lchild;
		}
		if(!s.empty())
		{
			node = s.top();
			s.pop();
			node = node->rchild;
		}
		else break;
	}
	d.dotToJpg(name);
}

//get the blackhight of the rbtree
int rbtree::getBh()
{
	int bh = 0;
	rbtnode *node = root;
	while (NULL != node)
	{
		if(node->color == BLACK)
			bh++;
		node = node->lchild;
	}
	return bh;
}

int rbtree::keyrank(rbtnode *node,int key)
{
	if(node->key == key)
	{
		return node->lchild->size + 1;
	}
	else if(node->key > key)
	{
		return keyrank(node->lchild, key);
	}
	else 
	{
		return node->lchild->size + 1 + keyrank(node->rchild, key);
	}
}

int rbtree::keyrank(int key)
{
	return keyrank(root, key);
}