【算法导论】红黑树

红黑树

         在了解红黑树之前，我们必须先了解二叉搜索树（又称二叉排序树，我在上一篇文章中有介绍），因为红黑树是一种特殊的二叉排序树：在每个节点上增加一个存储位来表示节点的颜色，因此红黑树共有五个域：color,key,lchild,rchild,p。

         红黑树的提出：一个高度为h的二叉排序树可以实现任何一种基本的动态集合操作:插入、删除、查找等操作，但是当树才高度比较高时，二叉树就会退化成链表。而红黑树能确保在最坏的情况下，基本的动态集合操作的时间为O(logn).

红黑树的性质决定了红黑树的性能，红黑树共有五大性质：

1、  每个节点不是红的，就是黑的。

2、  根节点是黑的。

3、  每个叶节点都是黑的。

4、  若一个节点是红的，则他的子节点都是黑的。

5、  对于每个节点，从该节点出发到其子孙叶节点的所有路径上包含相同数目的黑节点。

图片的信息比笔述更加清新明了，下图就是一棵红黑树的几种形式：

上图中，为了便于处理边界问题，我们采用一个哨兵来代表NIL。哨兵NIL是一个与普通节点有相同域的对象。它的color域为BLACK，其它域可随意设置。我在程序中将p、lchild、rchild设置为NULL，将key设置为-1.将所有指向NIL的指针都指向哨兵NIL。

下面先说明两个概念:内节点和外节点

内节点：把带关键字的节点称为内节点。

外节点：把没有子节点或父节点的节点称为外节点，我们把外节点都看成是哨兵NIL。

由于我们关注的是关键字key,因此我们主要关心内节点，所以在画红黑树的时候，常常忽略叶子，如上图c所示。

在介绍红黑树的插入和删除前，我们先必须介绍旋转这个概念。因为它在红黑树的插入、删除中，要用到很多。

旋转：分为左旋、右旋，它能够保持二叉排序树性质的局部操作。至于为什么能够保持性质，我也没有深入研究。前人不知道怎么发现这个操作。

我始终认为图像更能直观的表达更准确丰富的含义，我相信大家通过下图即可以明白左旋和右旋了。

如果对上图还是不太明了，也没关系，具体举例能使你有更深刻的认识，下图是在x上左旋的过程：

下面附上左旋和右旋的代码：

/*************************************************\
函数功能：左旋
输入：    根节点、要左旋的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Left_Rotate(RBTree* root,RBTree* x,RBTree* NIL)
{
	RBTree* y=NULL;
	y=x->rchild;
	x->rchild=y->lchild;

	if(y->lchild!=NIL)
		y->lchild->p=x;
	y->p=x->p;

	if(y->p==NIL)
	   root=y;
	else if(x==x->p->lchild)
		x->p->lchild=y;
	else
		x->p->rchild=y;
	y->lchild=x;
	x->p=y;
	return root;
}

/*************************************************\
函数功能：在节点z上右旋
输入：    根节点、要右旋的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Right_Rotate(RBTree* root,RBTree* x,RBTree* NIL)
{
	RBTree* y=NULL;
	y=x->lchild;
	x->lchild=y->rchild;
	if(y->rchild!=NIL)
		y->rchild->p=x;
	y->p=x->p;
	if(y->p==NIL)
	   root=y;
	else if(x==x->p->lchild)
		x->p->lchild=y;
	else
		x->p->rchild=y;
	y->rchild=x;
	x->p=y;
	return root;
}

插入操作：插入函数和插入修正函数

        在前一篇文章中我已经介绍了二叉排序树，其中也有插入和删除操作。因为红黑树也是二叉排序树，因此其插入操作大同小异，不同之处在于，红黑树的性质会被插入和删除操作所破坏，因此就需要修正。修正包括两个操作：重新着色、旋转。

从上面的分析可知，红黑树的插入操作分为两步，首先像二叉排序树一样进行插入操作，然后调用修正函数来保持红黑树的性质。在插入操作中，我们都设置插入节点的color域为红而不是黑（如果是黑的话，性质4就不会破坏），为什么？请读者好好思考。下面为插入函数的实现：

/*************************************************\
函数功能：插入一个节点z
输入：    根节点、插入的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Insert(RBTree* root,RBTree* z,RBTree* NIL)
{
//	printf("ok ");
	RBTree* leaf=NIL;
	RBTree* p=root;//指向根节点
	while(p!=NIL)//根节点不为空
	{
		//printf("dd");
		leaf=p;    //指向父节点
		if(z->key<p->key)
			p=p->lchild;
		else
			p=p->rchild;
	}

	z->p=leaf; //z为y的孩子节点 y=leaf
	if(leaf==NIL) //根节点为空
		root=z;
	else if(z->key<leaf->key)
		leaf->lchild=z;
	else
		leaf->rchild=z;

//	printf("%d ",root->key);

//	printf("%d ",root->color);
	return root;
}

        在Insert_FixUp插入修正函数中，循环截止条件为 z->p是黑色。如果z->p是红色，显然这就违返了红黑的树性质4。在循环中，我们要讨论6种情况，但是其中三种与另外三种是相互对称的，它可以由插入节点的父节点为祖父节点的左孩子还是右孩子来区分。下面我只讨论插入节点的父节点为祖父节点的左孩子的情况。在每一次迭代中，我们可能遇到以下三种情况。

情况一：叔叔是红色的

        这时只要把插入节点z的父亲z->p和uncle都设成黑色，并把祖父z->p->p设成红色。这样仍然确保了每一条路径上的黑色节点数不变。然后把z指向z->p->p，并开始新一轮的迭代。如下图：

情况二：叔叔是黑色的情况下，插入节点为右孩子

         这时我们只要把z指向z->p，然后做一次Left-Rotate(z)。就可以把情况转化成情况三。

情况三：叔叔是黑色的情况下，插入节点为左孩子

        只要把z->p设成黑色，把z->p->p设成红色，然后就调用    Right_Rotate(z->p->p)，整棵树就修正了。情况二和情况三如下图：

插入修正函数的具体实现如下：

/*************************************************\
函数功能：插入修正来维持红黑树的性质
输入：    根节点、插入的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Insert_FixUp(RBTree* root,RBTree* z,RBTree* NIL)
{
	RBTree* y=z;
	while(y->p->color==RED)//循环截止条件为父节点为黑
	{

		if(y->p==y->p->p->lchild)//插入节点的父节点为祖父节点的左孩子
		{
			RBTree* pr=y->p->p->rchild;
			if(pr->color==RED)//情况一：叔叔是红色的
			{
				y->p->color=BLACK;
				pr->color=BLACK;
				y->p->p->color=RED;
				y=y->p->p;
			}
			else //叔叔是黑色的，分两种情况
			{
				if(y==y->p->rchild)//情况二：叔叔是黑色的情况下，插入节点为右孩子
				{
					y=y->p;
					root=Left_Rotate(root,y,NIL);//情况二可以通过左旋变成情况三
				}
				y->p->color=BLACK;//情况三：叔叔是黑色的情况下，插入节点为左孩子
				y->p->p->color=RED;
				root=Right_Rotate(root,y->p->p,NIL);
			}
		}

		else//插入节点的父节点为祖父节点的左孩子,下面的情况与上面类似
			{
			RBTree* pl=y->p->p->lchild;
			if(pl->color==RED)
			{
				y->p->color=BLACK;
				pl->color=BLACK;
				y->p->p->color=RED;
				y=y->p->p;
			}
			else
			{
				if(y==y->p->lchild)
				{
					y=y->p;
					root=Left_Rotate(root,y,NIL);
				}
				y->p->color=BLACK;
				y->p->p->color=RED;
				root=Left_Rotate(root,y->p->p,NIL);
			}
		}

	}

	root->color=BLACK;
	return root;
}

删除操作：删除函数和删除修正函数
          删除操作和插入操作一样，都可以和二叉排序树一样进行对比。红黑树的删除操作分为两步，首先像二叉排序树一样进行删除操作，然后调用修正函数来保持红黑树的性质。前一篇二叉排序树的文章也讲过，删除操作要比插入操作复杂一些，红黑树也不例外。删除函数的具体实现如下：

/*************************************************\
函数功能：删除一个节点z
输入：    根节点、要删除的节点、哨兵
输出：    根节点
\*************************************************/
 RBTree* Delete(RBTree* root,RBTree* node,RBTree* NIL)
 {
        RBTree* toDel = node;
        if (node->lchild != NIL && node->rchild != NIL)
		{
            toDel = TreeNext(node,NIL);
        }

        RBTree* temp = toDel;
        while (temp->p != NIL)
		{

            temp = temp->p;
        }

        RBTree* replace = (toDel->lchild != NIL)? toDel->lchild: toDel->rchild;
        replace->p = toDel->p;
        if (replace->p == NIL)
		{
            root = replace;
        }
        else if (toDel == toDel->p->lchild)
		{
            replace->p->lchild = replace;
        }
        else
		{
            replace->p->rchild = replace;
        }
        if (toDel != node)
		{
            node->key = toDel->key;
        }
        if (toDel->color == BLACK)
		{
            //修改树，以保持平衡。
            root=Del_FixUp(root,replace,NIL);
        }
        delete toDel;
		return root;
    }<span style="font-family: Calibri, sans-serif;"><span style="font-size: 19px;">
</span></span>

         在Del_FixUp删除操作修正函数中，循环截止条件为z->color== RED。如果z->p是黑色，即删除的节点为黑色，显然这就违返了红黑的树性质5。在循环中，我们要讨论8种情况，但是其中4种与另外4种是相互对称的，它可以由删除的节点为父节点的左孩子还是右孩子来区分。下面我只讨论删除的节点为父节点的左孩子的情况:
在每一次迭代中，我们可能遇到以下4种情况：

情况一：兄弟为红色

       这时我们根据红黑树的性质可以肯定删除的节点x->p是黑色、其兄弟节点w->lchild是黑色。我们把x->pt与brother的颜色互换，然后做一次Left-Rotate(x->p)。做完之后x的新的兄弟：原w->lchild，是黑色的。因此我们在不破坏红黑树性质的前提下，把情况一转换成了情况二、情况三、情况四中的一个，如下图（a）：

情况二：兄弟为黑色，其两个孩子为黑色

       这时我们只要把w设成红色,然后把x移到x->p，这一次操作不会破坏红黑树的性质。如下图（图中节点B不一定是红色，也可能是黑色）如下图（b）：

情况三：兄弟为黑色，且其左孩子为红色，右孩子为黑色

       我们把w与w->lchild的颜色互换，然后做Right-Rotate(w)。这样做不会破坏红黑树的性质。这时x的新的兄弟就是原w->lchild。而情况3被转化成了情况4,如上图（c）：

情况四：兄弟为黑色，且其右孩子为红色

先把w与x->parent的颜色互换，再做Left-Rotate(x->parent)。这时图中节点E（也就是原w->rchild）所在的路径就肯定少了一个黑色，而x所在的路径则多了一个黑色。那么我们就把使E也为黑色，这样就保持了红黑树的性质。如下图（d）：


具体的代码实现如下：

#include<stdio.h>
#include<malloc.h>

enum Color{RED,BLACK};

typedef struct node//红黑树的节点结构
{
	enum Color color;
	struct node *p,*lchild,*rchild;
	int key;
}RBTree;

RBTree* Insert(RBTree* root,RBTree* z,RBTree* NIL);//插入
RBTree* Insert_FixUp(RBTree* root,RBTree* z,RBTree* NIL);//插入修正
RBTree* Left_Rotate(RBTree* root,RBTree* x,RBTree* NIL);//左旋
RBTree* Right_Rotate(RBTree* root,RBTree* x,RBTree* NIL);//右旋
RBTree* Delete(RBTree* root,RBTree* node,RBTree* NIL);//删除
void Layer(RBTree *p,int n);//广度优先遍历，用于查看红黑树的节点
RBTree* TreeNext(RBTree* node,RBTree* NIL);// 查找后继
RBTree* TreePre(RBTree* node,RBTree* NIL);// 查找前趋
RBTree* TreeMax(RBTree* root,RBTree* NIL);// 查找最大值
RBTree* TreeMin(RBTree* root,RBTree* NIL);// 查找最小值
RBTree* Del_FixUp(RBTree* root,RBTree* delNode,RBTree* NIL);//删除修正

void main()
{
	int arrayA[]={11,2,14,1,7,15,5,8,4};
	int n=sizeof(arrayA)/sizeof(int);
//	printf("%d\n",BLACK);

    RBTree* NIL=(RBTree*)malloc(sizeof(RBTree));//哨兵节点即外节点
	NIL->color=BLACK;
	NIL->key=-1;
	NIL->lchild=NIL->rchild=NULL;
	NIL->p=NULL;
	RBTree *root=NULL;//根节点
	root=NIL;
	for(int i=0;i<n;i++)
	{
		RBTree* z=(RBTree*)malloc(sizeof(RBTree));
		z->color=RED;
		z->key=arrayA[i];
		z->lchild=NIL;
		z->rchild=NIL;
		z->p=NIL;
		printf("\n插入节点的关键值为%d ",z->key);
		root=Insert(root,z,NIL);
		printf("\n插入修正前的广度遍历:\n");
		Layer(root,n);
		root=Insert_FixUp(root,z,NIL);
	//	printf("%d\n",i);
		printf("插入修正后的广度遍历:\n");
		Layer(root,n);
		printf("\n");

	}
	printf("插入操作完成！！\n\n");
	printf("删除节点的关键值为%d\n ",root->lchild->rchild->key);
	printf("\n删除顶节点后的广度遍历：\n");
	root=Delete(root,root->lchild->rchild,NIL);
	n=n-1;//删除一个节点 n减一
	Layer(root,n);

	}

/*************************************************\
函数功能：插入一个节点z
输入：    根节点、插入的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Insert(RBTree* root,RBTree* z,RBTree* NIL)
{
//	printf("ok ");
	RBTree* leaf=NIL;
	RBTree* p=root;//指向根节点
	while(p!=NIL)//根节点不为空
	{
		//printf("dd");
		leaf=p;    //指向父节点
		if(z->key<p->key)
			p=p->lchild;
		else
			p=p->rchild;
	}

	z->p=leaf; //z为y的孩子节点 y=leaf
	if(leaf==NIL) //根节点为空
		root=z;
	else if(z->key<leaf->key)
		leaf->lchild=z;
	else
		leaf->rchild=z;

//	printf("%d ",root->key);

//	printf("%d ",root->color);
	return root;
}

/*************************************************\
函数功能：插入修正来维持红黑树的性质
输入：    根节点、插入的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Insert_FixUp(RBTree* root,RBTree* z,RBTree* NIL)
{
	RBTree* y=z;
	while(y->p->color==RED)//循环截止条件为父节点为黑
	{

		if(y->p==y->p->p->lchild)//插入节点的父节点为祖父节点的左孩子
		{
			RBTree* pr=y->p->p->rchild;
			if(pr->color==RED)//情况一：叔叔是红色的
			{
				y->p->color=BLACK;
				pr->color=BLACK;
				y->p->p->color=RED;
				y=y->p->p;
			}
			else //叔叔是黑色的，分两种情况
			{
				if(y==y->p->rchild)//情况二：叔叔是黑色的情况下，插入节点为右孩子
				{
					y=y->p;
					root=Left_Rotate(root,y,NIL);//情况二可以通过左旋变成情况三
				}
				y->p->color=BLACK;//情况三：叔叔是黑色的情况下，插入节点为左孩子
				y->p->p->color=RED;
				root=Right_Rotate(root,y->p->p,NIL);
			}
		}

		else//插入节点的父节点为祖父节点的左孩子,下面的情况与上面类似
			{
			RBTree* pl=y->p->p->lchild;
			if(pl->color==RED)
			{
				y->p->color=BLACK;
				pl->color=BLACK;
				y->p->p->color=RED;
				y=y->p->p;
			}
			else
			{
				if(y==y->p->lchild)
				{
					y=y->p;
					root=Left_Rotate(root,y,NIL);
				}
				y->p->color=BLACK;
				y->p->p->color=RED;
				root=Left_Rotate(root,y->p->p,NIL);
			}
		}

	}

	root->color=BLACK;
	return root;
}

/*************************************************\
函数功能：左旋
输入：    根节点、要左旋的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Left_Rotate(RBTree* root,RBTree* x,RBTree* NIL)
{
	RBTree* y=NULL;
	y=x->rchild;
	x->rchild=y->lchild;

	if(y->lchild!=NIL)
		y->lchild->p=x;
	y->p=x->p;

	if(y->p==NIL)
	   root=y;
	else if(x==x->p->lchild)
		x->p->lchild=y;
	else
		x->p->rchild=y;
	y->lchild=x;
	x->p=y;
	return root;
}

/*************************************************\
函数功能：在节点z上右旋
输入：    根节点、要右旋的节点、哨兵
输出：    根节点
\*************************************************/
RBTree* Right_Rotate(RBTree* root,RBTree* x,RBTree* NIL)
{
	RBTree* y=NULL;
	y=x->lchild;
	x->lchild=y->rchild;
	if(y->rchild!=NIL)
		y->rchild->p=x;
	y->p=x->p;
	if(y->p==NIL)
	   root=y;
	else if(x==x->p->lchild)
		x->p->lchild=y;
	else
		x->p->rchild=y;
	y->rchild=x;
	x->p=y;
	return root;
}

/*************************************************\
函数功能：删除一个节点z
输入：    根节点、要删除的节点、哨兵
输出：    根节点
\*************************************************/
 RBTree* Delete(RBTree* root,RBTree* node,RBTree* NIL)
 {
        RBTree* toDel = node;
        if (node->lchild != NIL && node->rchild != NIL)
		{
            toDel = TreeNext(node,NIL);
        }

        RBTree* temp = toDel;
        while (temp->p != NIL)
		{

            temp = temp->p;
        }

        RBTree* replace = (toDel->lchild != NIL)? toDel->lchild: toDel->rchild;
        replace->p = toDel->p;
        if (replace->p == NIL)
		{
            root = replace;
        }
        else if (toDel == toDel->p->lchild)
		{
            replace->p->lchild = replace;
        }
        else
		{
            replace->p->rchild = replace;
        }
        if (toDel != node)
		{
            node->key = toDel->key;
        }
        if (toDel->color == BLACK)
		{
            //修改树，以保持平衡。
            root=Del_FixUp(root,replace,NIL);
        }
        delete toDel;
		return root;
    }

/*************************************************\
函数功能：删除修正 维持红黑树的性质
输入：    根节点、要删除的节点、哨兵
输出：    根节点
\*************************************************/
   RBTree* Del_FixUp(RBTree* root,RBTree* delNode,RBTree* NIL)
   {
        RBTree* p = delNode;
        while (p != root && p->color == BLACK)
		{
            if (p == p->p->lchild)//要删除的节点为父节点的左孩子
			{
                RBTree* brother = p->p->rchild;
                if (brother->color == RED) //情况一：兄弟为红色
				{
                    brother->color = BLACK;
                    p->p->color = RED;
                    root=Left_Rotate(root,p->p,NIL);//经过旋转后 兄弟变为黑色，进入下面三种情况之一
                    brother = p->p->rchild;
                }
                if (brother->lchild->color == BLACK&& brother->rchild->color == BLACK)//情况二：兄弟为黑色，其两个孩子为黑色
				{
                    brother->color = RED;
                    p = p->p;
                }
                else
				{
                    if (brother->rchild->color == BLACK)//情况三：兄弟为黑色，且其左孩子为红色，右孩子为黑色
					{
                        brother->lchild->color = BLACK;
                        brother->color = RED;
                        root=Right_Rotate(root,brother,NIL);//转变为情况四
                        brother  = brother->p;
                    }
                    brother->color = brother->p->color;//情况四：兄弟为黑色，且其右孩子为红色
                    brother->p->color = BLACK;
                    brother->rchild->color = BLACK;
                    root=Left_Rotate(root,brother->p,NIL);
                    p = root;
                }
            }
            else//删除的节点为父节点的右孩子,下面的情况与上面类似
			{
                RBTree* brother = p->p->lchild;
                if (brother->color == RED)
				{
                    brother->color = BLACK;
                    p->p->color = RED;
                    root=Right_Rotate(root,p->p,NIL);
                    brother = p->p->lchild;
                }
                if (brother->lchild->color == BLACK&& brother->rchild->color == BLACK)
				{
                    brother->color = RED;
                    p = p->p;
                }
                else
				{
                    if (brother->lchild->color == BLACK)
					{
                        brother->rchild->color = BLACK;
                        brother->color = RED;
                        root=Left_Rotate(root,brother,NIL);
                        brother = brother->p;
                    }
                    brother->color = brother->p->color;
                    brother->p->color = BLACK;
                    brother->lchild->color = BLACK;
                    root=Right_Rotate(root,brother->p,NIL);
                    p = root;
                }
            }
        }
        p->color = BLACK;
		return root;
    }

   /*************************************************\
函数功能：广度优先遍历
输入：    根节点、节点数
输出：    无
\*************************************************/
void Layer(RBTree *p,int n)
{
	RBTree* queue[40];//queue数组用于存储节点地址
	int count=0;
	RBTree* s;
	int rear=0;  //队列尾指针
	int front=0; //队列头指针

	if(p!=NULL)//输入的树不为空
	{
		rear=1; //初始化
		front=0;
		queue[rear]=p;
		while(front<rear)//判断队列是否为空
		{
			front++;
			s=queue[front];
			if(s->key!=-1)
				count++;
			printf("key=%d color=%d\n",s->key,s->color);

			if(s->lchild!=NULL) //存储左右子节点
			{
				rear++;
				queue[rear]=s->lchild;
			}
			if(s->rchild!=NULL)
			{
				rear++;
				queue[rear]=s->rchild;
			}

			if(count>=n)
				break;
		}
	}
}

/*************************************************\
函数功能：查找一个节点在中序遍列中的下一个节点(后继)
输入：    一个节点、哨兵
输出：    该节点的后继节点
\*************************************************/
 RBTree* TreeNext(RBTree* node,RBTree* NIL)
 {
        RBTree* result;
        if (node->rchild!=NIL)
		{
            result = TreeMin(node->rchild,NIL);
        }
        else
		{
            result = node->p;
            RBTree* temp = node;
            while (result!=NIL&&temp==result->rchild)
			{
                temp = result;
                result = result->p;
            }
        }
        return result;
  }

/*************************************************\
函数功能：一个节点在中序遍列中的前一个节点(前趋)
输入：    一个节点、哨兵
输出：    该节点的前趋节点
\*************************************************/
    RBTree* TreePre(RBTree* node,RBTree* NIL)
	{
        RBTree* result;
        if (node->lchild !=NIL)
		{
            result = TreeMax(node->rchild,NIL);
        }
        else
		{
            result = node->p;
            RBTree* temp = node;
            while (result != NIL && temp == result->lchild)
			{
                temp = result;
                result = result->p;
            }
        }
        return result;
    }

/*************************************************\
函数功能：找到子树中最大的节点
输入：    根节点、哨兵
输出：    子树中最大的节点
\*************************************************/
    RBTree* TreeMax(RBTree* root,RBTree* NIL)
	{
        RBTree* result = root;
        while (result->rchild !=NIL)
		{
            result = result->rchild;
        }
        return result;
    }

/*************************************************\
函数功能：找到子树中最小的节点
输入：    根节点、哨兵
输出：    子树中最小的节点
\*************************************************/
    RBTree* TreeMin(RBTree* root,RBTree* NIL)
	{
        RBTree* result = root;
        while (result->lchild !=NIL)
		{
            result = result->lchild;
        }
        return result;
    }

最后给出运行结果的说明：在我电脑上的运行结果为：

（key为关键字，color=0表示为红色，color=1表示为黑色，key=-1代表空节点）

插入节点的关键值为11
插入修正前的广度遍历:
key=11 color=0
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为2
插入修正前的广度遍历:
key=11 color=1
key=2 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为14
插入修正前的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为1
插入修正前的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=0
key=1 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=1
key=14 color=1
key=1 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为7
插入修正前的广度遍历:
key=11 color=1
key=2 color=1
key=14 color=1
key=1 color=0
key=7 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=1
key=14 color=1
key=1 color=0
key=7 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为15
插入修正前的广度遍历:
key=11 color=1
key=2 color=1
key=14 color=1
key=1 color=0
key=7 color=0
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=1
key=14 color=1
key=1 color=0
key=7 color=0
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为5
插入修正前的广度遍历:
key=11 color=1
key=2 color=1
key=14 color=1
key=1 color=0
key=7 color=0
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=5 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=1
key=1 color=1
key=7 color=1
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=5 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为8
插入修正前的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=1
key=1 color=1
key=7 color=1
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=5 color=0
key=8 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
插入修正后的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=1
key=1 color=1
key=7 color=1
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=5 color=0
key=8 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1

插入节点的关键值为4
插入修正前的广度遍历:
key=11 color=1
key=2 color=0
key=14 color=1
key=1 color=1
key=7 color=1
key=-1 color=1
key=15 color=0
key=-1 color=1
key=-1 color=1
key=5 color=0
key=8 color=0
key=-1 color=1
key=-1 color=1
key=4 color=0
插入修正后的广度遍历:
key=7 color=1
key=2 color=0
key=11 color=0
key=1 color=1
key=5 color=1
key=8 color=1
key=14 color=1
key=-1 color=1
key=-1 color=1
key=4 color=0
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=15 color=0

插入操作完成！！
形成的红黑树为：

删除节点的关键值为5

删除顶节点后的广度遍历：
key=7 color=1
key=2 color=0
key=11 color=0
key=1 color=1
key=4 color=1
key=8 color=1
key=14 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=-1 color=1
key=15 color=0
请按任意键继续. . .

删除节点5后的红黑树为：

本文参考资料：《算法导论》

原文：http://blog.csdn.net/tengweitw/article/details/9863213

作者：nineheadedbird

时间： 2024-03-05 08:33:23

【算法导论】红黑树的相关文章

算法之红黑树

红黑树(一) 原理和算法详细介   1 R-B Tree简介     R-B Tree,全称是Red-Black Tree,又称为"红黑树",它一种特殊的二叉查找树.红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black). 红黑树的特性:(1)每个节点或者是黑色,或者是红色.(2)根节点是黑色.(3)每个叶子节点(NIL)是黑色. [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!](4)如果一个节点是红色的,则它的子节点必须是黑色的.(5)从一个

浅谈算法和数据结构 九 平衡查找树之红黑树

前面一篇文章介绍了2-3查找树,可以看到,2-3查找树能保证在插入元素之后能保持树的平衡状态,最坏情况下即所有的子节点都是2-node,树的高度为lgN,从而保证了最坏情况下的时间复杂度.但是2-3树实现起来比较复杂,本文介绍一种简单实现2-3树的数据结构,即红黑树(Red-Black Tree) 定义 红黑树的主要是像是对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息.红黑树中将节点之间的链接分为两种不同类型,红色链接,他用来链接两个2-nodes节点来表示一个

第十三章 红黑树

R-B Tree简介     R-B Tree,全称是Red-Black Tree,又称为"红黑树",它一种特殊的二叉查找树.红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black). 红黑树的特性:(1)每个节点或者是黑色,或者是红色.(2)根节点是黑色.(3)每个叶子节点(NIL)是黑色. [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!](4)如果一个节点是红色的,则它的子节点必须是黑色的.(5)从一个节点到该节点的子孙节点的所有路径上包含相

通过分析JDK源代码研究TreeMap红黑树算法实现

简介:TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员,其中 TreeMap 是 Map 接口的常用实现类,而 TreeSet 是 Set 接口的常用实现类.虽然 HashMap 和 HashSet 实现的接口规范 不同,但 TreeSet 底层是通过 TreeMap 来实现的,因此二者的实现方式完全一样.而 TreeMap 的实现 就是红黑树算法. TreeMap 的实现就是红黑树数据结构,也就说是一棵自平衡的排序二叉树,这样就可以保证

【C/C++学院】0828-STL入门与简介/STL容器概念/容器迭代器仿函数算法STL概念例子/栈队列双端队列优先队列/数据结构堆的概念/红黑树容器

STL入门与简介 #include<iostream> #include <vector>//容器 #include<array>//数组 #include <algorithm>//算法 using namespace std; //实现一个类模板,专门实现打印的功能 template<class T> //类模板实现了方法 class myvectorprint { public: void operator ()(const T &

数据结构和算法05 之红-黑树（看完包懂~）

(友情提示,红-黑树是基于二叉搜索树的,如果对二叉搜索树不了解,可以先看看:二叉搜索树 )                从第4节的分析中可以看出,二叉搜索树是个很好的数据结构,可以快速地找到一个给定关键字的数据项,并且可以快速地插入和删除数据项.但是二叉搜索树有个很麻烦的问题,如果树中插入的是随机数据,则执行效果很好,但如果插入的是有序或者逆序的数据,那么二叉搜索树的执行速度就变得很慢.因为当插入数值有序时,二叉树就是非平衡的了,排在一条线上,其实就变成了一个链表--它的快速查找.插入和删除指

红黑树的插入

一.红黑树的介绍 先来看下算法导论对R-B Tree的介绍: 红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其 他路径长出俩倍,因而是接近平衡的. 前面说了,红黑树,是一种二叉查找树,既然是二叉查找树,那么它必满足二叉查找树的一般性质. 下面,在具体介绍红黑树之前,咱们先来了解下 二叉查找树的一般性质: 1.在一棵二叉查找树上,执行查找.插入.删除等操作,的时间复杂

红黑树解法的why而非how

0 初衷 很多介绍红黑树的文章如同算法导论书中那样,都是上来直接给出一些分类情况,以及每个分类情况下的处理办法,而没有着重讲述为什么这么分类,为什么这个分类下执行这些操作,即只介绍了how,没有重点给出why.本篇文章的重点就在于解释why. 这样可能就导致一种现象:我按照这些分类以及分类下的操作办法,的确完整的走通想通了整个算法过程,感觉应该理解红黑树了,但是可能过了几个月后就忘记如何分类的了,忘记分类下如何操作的了. 归根到底是我们没有找出最本质的东西,比如说插入节点时遇到父子是红红的问题,

基本数据结构(算法导论)与python

Stack, Queue Stack是后进先出, LIFO, 队列为先进先出, FIFO 在python中两者, 都可以简单的用list实现, 进, 用append() 出, Stack用pop(), Queue用pop(0), pop的时候注意判断len(l)  对于优先队列, 要用到前面讲到的堆 链表和多重数组 这些数据结构在python中就没有存在的价值, 用list都能轻松实现 散列表 为了满足实时查询的需求而产生的数据结构, 查询复杂度的期望是O(1), 最差为O(n) 问题描述, 对