精华内容
下载资源
问答
  • 红黑树 删除

    2014-07-30 10:46:11
    红黑树是一种特殊的二叉查找树,其删除结点首先要按二叉查找树删除结点的算法进行 一、普通二叉查找树删除一个结点: (1)待删除结点没有子结点,即它是一个叶子结点,此时直接删除 (2)待删除结点只有一个子...

    红黑树是一种特殊的二叉查找树,其删除结点首先要按二叉查找树删除结点的算法进行

    一、普通二叉查找树删除一个结点:

    (1)待删除结点没有子结点,即它是一个叶子结点,此时直接删除

    (2)待删除结点只有一个子结点,则可以直接删除;如果待删除结点是根结点,则它的子结点变为根结点;如果待删除结点不是根结点,则用它的子结点替代它的位置。

    (3)待删除结点有两个子结点,首先找出该结点的后继结点(即右子树中数值最小的那个结点),然后将两个结点进行值交换(即:只交换两个结点的数值,不改变结点的颜色),此时待删除节点变为后继结点,删除后继结点结。由于后继结点不可能有左子结点,对调后的待删除结点也不会有左子结点,因此要把它删除的操作会落入情况(1)或情况(2)中。

    二、.红黑树的删除结点算法

      1.  待删除结点有一个外部结点,操作为: 
        该节点是黑色,其非空子节点为红色 ;则将其子节点提升到该结点位置,颜色变黑

      2.待删除结点有两个外部结点,操作如下:

        (1)若该结点是红色,则可直接删除,不影响红黑树的性质,算法结束

        (2)若该结点是黑色,则删除后红黑树不平衡。此时要进行“双黑”操作

                记该结点为V,则删除了V后,从根结点到V的所有子孙叶结点的路径将会比树中其他的从根结点到叶结点的路径拥有更少的黑色结点, 破坏了红黑树性质4。此时,用“双黑”结点来表示从根结点到这个“双黑”结点的所有子孙叶结点的路径上都增加一个黑色结点。  
    双黑含义:该结点需要代表两个黑色结点,才能维持树的平衡

    红黑树删除操作 - 枫叶 - 枫叶

    图1

       如图1,要删除结点90,则删除后从根结点到结点90的所有子树结点的路径上的黑色结点比从根点到叶结点的路径上的黑结点少。因而,删除结点90后,用子结点NULL代替90结点,并置为“双黑”结点。


    3.“双黑”结点的处理

    分三种情况:

                           (1)双黑结点的兄弟结点是红色结点

                           (2)双黑结点的兄弟结点是黑色,且有两个黑色结点

                           (3)双黑色结点的兄弟结点是黑色,且子结点有红色结点

    (1)双黑结点的兄弟结点是红色结点

    处理方法:把父节点染成红色,兄弟节点染成黑色,然后对当前节点的父节点进行左旋,重新进入算法。

    (2)双黑结点的兄弟结点是黑色,且有两个黑色结点        

    处理方法:从当前节点和兄弟节点中抽取一重黑色追加到父节点,把父节点当成新的当前节点,重新进入算法。

    (3)双黑色结点的兄弟结点是黑色,且子结点有红色结点    
    A情况:双黑结点近侄子结点(双黑结点若为左孩子,则双黑结点的兄弟结点的左孩子为近侄子结点;同理,处理双黑结点为右孩子))为红色。
    处理方法:把兄弟节点染红,近侄子节点染黑,然后以兄弟节点为支点进行右旋,重新进入算法。

    B情况:双黑结点远侄子结点(双黑结点若为左孩子,则双黑结点的兄弟结点的右孩子为远侄子结点;同理,处理双黑结点为右孩子)为红色。
    处理方法:把兄弟节点染成当前父节点的颜色,把当前节点的父节点染成黑色,远侄子节点染成黑色,然后以当前节点的父节点为支点进行左旋,并把当前节点x指向旋转后树的根节点,算法结束,所有性质调整正确。


    插入过程

    插入顺序为:12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17

    插入节点12:为根节点 

     

    插入节点1:父节点为黑色,结束

    插入节点9:父节点为红色,叔父节点为黑色,LR,case2+case3

    插入节点2:父节点为红色,叔节点为红色,case1

    插入节点0:父节点为黑色,结束

    插入节点11:父节点为黑色,结束

    插入节点7:父节点为红色,叔节点为红色,case1

    插入节点19:父节点为黑色,结束

    插入节点4:父节点为红色,叔父节点为黑色,RL,case2+case3

    插入节点15:父节点为红,叔父节点为红,case1

    插入节点18:父节点为红,叔父节点为黑,LR,case2+case3

    插入节点5:父节点为红,叔父节点为红,case1

    父节点为红,叔父节点为红,case1

    插入节点14:父节点为红,叔父节点为红,case1

    插入节点13:父节点为红,叔父节点为黑,LL,case3

    插入节点10:父节点为黑,结束

    插入节点16:父节点为红,叔父节点为红,case1

    父节点为红,叔父节点为黑,RL,case2+case3

    插入节点6:父节点为红,叔父节点为黑,LR,case2+case3

    插入节点3:父节点为黑色,结束

    插入节点8:父节点为红,叔父节点为红,case1

    父节点为红,叔父节点为黑,RR,case3

    插入节点17:父节点为红,叔父节点为黑,RR,case3

    删除过程

    原始红黑树

    删除12:用13覆盖12,转换为删除13

    自己为黑,兄弟为黑,兄弟左子为黑,右子为红,case4

    删除1:用2覆盖1,转换为删除2

    自己为黑,当前节点3为红,变黑

    删除9:用10覆盖9,转化为删除10

    自己为黑,兄弟为黑,兄弟的双子为黑,case2

    自己为红,结束

    删除2:用3覆盖2,转换为删除3

    自己为黑,兄弟为黑,兄弟的双子为黑,case2

    自己为红,变黑,结束

    删除0:自己为红,结束

    删除11:当前节点为红,变黑,结束

    删除7:自己为黑,当前节点为红,变黑

    删除19:当前节点为黑,兄弟为黑,兄弟的左子为红,case4

    删除4,用5覆盖4,转换为删除5

    自己为黑,兄弟为黑,兄弟双子为黑,case2

    自己为红,变黑,结束

    删除15:自己为黑,兄弟为黑,兄弟的右子为黑,左子为红,case3+case4

    删除18:自己为黑,兄弟为黑,兄弟的双子为黑,case2

    自己为红,变黑,结束

    删除5:用8覆盖5,转换为删除8

    自己为红,结束

    删除14:用16覆盖14,转换为删除16

    自己为红,结束

    删除13:自己为黑,兄弟为黑,兄弟的双子为黑,case2

    自己为黑,兄弟为黑,兄弟的双子为黑,case2

    删除10:用16覆盖10,转换为删除10

    自己为黑,当前节点为红,变黑

    删除16:用17覆盖16,转换为删除17

    自己为黑,兄弟为红,case1

    自己为黑,兄弟为黑,兄弟的双子为黑,case2

    删除6:用8覆盖6,转化为删除8

    自己为红,结束

    删除3:自己为黑,兄弟为黑,兄弟的双子为黑,case2

    删除8:当前节点为红,变黑,结束

    删除17:结束





    另外一篇关于红黑树 添加、删除的链接: http://hi.baidu.com/coolinc/item/c2073dc375dfe8bd0c0a7bf6
    展开全文
  • 看这篇文章 需要了解AVL树,知道AVL树的 删除,旋转调整等操作。这是我对红黑树删除的一些理解

    看这篇文章 需要了解AVL树,知道AVL树的 删除,旋转调整等操作

    学到红黑树,不太想看算法导论里的伪码,手头有本侯大师的STL源码剖析,但里面只讲了插入,没讲删除。然后上网看了些博客的讲解,大家各有不同角度来理解。但大多都在讲解,几种几种情况,然后怎么转换颜色,怎么旋转。看的我不是很明白。不知道为什么要这样处理,会不会破坏红黑树的结构等等,然后自己想了想,总结了一下自己的理解。只是逻辑上的理解红黑树删除,然后打算去看一下STL中红黑树的代码,再回来审视一下这篇总结吧

    //  这个是我在一个很简单的画图工具里画的 包括文字都弄在一张图里了。然后40多兆  上传不了。。。。  切成了几块,可能看起来效果不太好




    2.2.2





    展开全文
  • 红黑树删除例子

    万次阅读 2020-01-16 12:01:14
    这里不将原理了,只放几个例子供大家观看,如有错误请留言 删除3 红色节点直接删即可 删除2 右子节点替代2,1变黑即可 删除5 比较麻烦 删除66

    这里不将原理了,只放几个例子供大家观看,如有错误请留言

    在这里插入图片描述
    删除3
    红色节点直接删即可
    在这里插入图片描述

    删除2
    在这里插入图片描述
    右子节点替代2,1变黑即可
    在这里插入图片描述
    然后发现不满足到每个节点的黑色子点数目一致,将1和5染红,3变黑即可
    删除5
    在这里插入图片描述
    比较麻烦在这里插入图片描述

    删除66
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 红黑树删除的实现

    2014-11-06 10:20:08
    在将红黑树中某个节点删除时,分几个步骤,shou

    在将红黑树中某个节点删除时,分几个步骤,首先找到该节点的位置,然后删除该节点,最后调整红黑树。

    本文代码还存在一个问题没有解决,当连续删除到第3个节点时会出现问题,现在暂时还没找出问题,以后有空慢慢研究。

    1、找出要删除的节点

    TREE rb_delete_find(TREE r, int d)	// find the node that need deleted
    {
    	NODE *x;
    	x = r;
    	while(x != NULL)
    	{
    		if(x->key == d)
    			break;
    		else if(d < x->key)
    			x = x->left;
    		else
    			x = x->right;
    	}
    	
    	if(x == NULL)
    	{
    		printf("find failed\n", x->key);
    		return NULL;
    	}
    	else
    	{
    		printf("find success, %d\n", x->key);
    		return rb_delete(r, x);
    	}
    }

    2、删除节点

    在找到要删除的节点后,根据不同的情形将节点删除。代码如下:

    TREE rb_delete(TREE r, NODE *z)
    {
    	NODE *x, *y = z, *tmp;
    	int y_original_color = y->color;
    	
    	tmp = (TREE)malloc(sizeof(NODE));
    	tmp->key = -1;
    	tmp->color = 1;
    	tmp->left = NULL;
    	tmp->right = NULL;
    	
    	if(z->left == NULL)
    	{
    		x = z->right;
    		r = rb_delete_node(r, z, z->right);
    		if(x == NULL)
    		{
    			x = tmp;
    			x->p = z->p;
    			z->p->right = x;
    		}
    	}
    	else if(z->right == NULL)
    	{
    		x = z->left;
    		r = rb_delete_node(r, z, z->left);
    		
    	}
    	else	//左右孩子都不为空 
    	{
    		y = tree_minimum(z->right);			//y要么没有子节点要么只有右孩子 
    		y_original_color = y->color;
    		x = y->right;
    		
    		if(y->p != z)
    		{
    			r = rb_delete_node(r, y, y->right);
    			y->right = z->right;
    			y->right->p = y;
    		}
    		r = rb_delete_node(r, z, y);
    		y->left = z->left;
    		y->left->p = y;
    		y->color = z->color;
    		
    		if(NULL == x)
    		{
    			x = tmp;
    			x->p = y;
    			y->right = x;
    		}
    	}
    //	printf("root->key: %d \tx->key: %d\n", r->key, x->key);
    //	printf("root->left: %d \troot->right: %d\n", r->left->key, r->right->key);
    	/**在删除或移动黑色节点时,需要将他的黑色下推给他的孩子节点。若孩子节点为空,
    		这时将无法将黑色下推。若黑色向上推则会导致黑高的不相等。
    		在此通过创建临时节点,将其作为叶子节点。叶子节点的颜色为黑色,值为-1. 
    	**/ 
    	
    	//printf("------------r.key = %d   x.key = %d\n",r->key, x->key);
    	//y_original_color保存了移动或删除的节点的颜色,当移动或删除的节点为红色时,红黑树的性质没有被破坏,
    	//而当移动或删除的节点为黑色时,红黑树的性质被破坏了,这是就需要对其进行调整。 
    	if(y_original_color == 1)	//1:黑色, 0:红色  
    	{
    		r = rb_delete_fixup(r, x);
    	}
    	
    	return r;
    }

    3、红黑树的调整

    当删除或移动的节点为黑色时,需要对红黑树进行调整,以使得其继续保持红黑树的性质。具体的调整过程见上一篇文章。

    调整代码如下:

    TREE rb_delete_fixup(TREE r, NODE *z)
    {
    	NODE *x = z, *w;
    	
    	while(x!=r && x->color==1)
    	{
    		if(x == x->p->left)		//x is left child
    		{
    			w = x->p->right;
    			if(w!=NULL && w->color == 0)		//case 1: w->color=0
    			{
    				w->color = 1;
    				x->p->color = 0;
    				r = left_rotate(r, x->p);
    				w = x->p->right;
    			}
    			
    			//提取x和w的一个黑色, 上移到x的父节点。从w提出一个黑色后其变成了红色,x还剩一个黑色 
    			if((w->left==NULL ||w->left->color==1) && (w->right==NULL || w->right->color==1))	//case 2: w->color=1 && w.left=1 && w.right=1
    			{
    				w->color = 0;
    				x = x->p;
    			}
    			else
    			{
    				if(w->right==NULL || w->right->color==1)						//case 3: w->color=1 && w.left=0 && w.right=1
    				{
    					w->left->color = 1;
    					w->color = 0;
    					r = right_rotate(r, w);
    					w = x->p->right;
    				}
    				w->color = x->p->color;						//case 4: w->color=1 && w.right=0
    				x->p->color = 1;
    				w->right->color = 1;
    				r = left_rotate(r, x->p);
    				x = r;
    			}
    		}
    		else					//x is right child
    		{
    			w = x->p->left;
    			if(w->color == 0)	//case 1
    			{
    				w->color = 1;
    				x->p->color = 0;
    				r = right_rotate(r, x->p);
    				w = x->p->left;
    			}
    			if((w->left==NULL || w->left->color==1) && (w->right==NULL || w->right->color==1))	//case 2
    			{
    				w->color = 0;
    				x = x->p;
    			}
    			else
    			{
    				if(w->left==NULL || w->left->color==1)		//case 3
    				{
    					w->color = 0;
    					w->right->color = 1;
    					r = left_rotate(r, w);
    					w = x->p->left;
    				}
    											//case 4
    				w->color = x->p->color;
    				w->left->color = 1;
    				x->p->color = 1;
    				
    				r = right_rotate(r, x->p);
    				x = r;
    			}
    		}
    	}
    	x->color = 1;
    	return r;
    }

    在以上的过程中还用到了以下函数,

    首先是删除节点函数,其代码如下:

    /**
    **	删除节点x,使用y来代替x节点 
    **/
    TREE rb_delete_node(TREE r, NODE *x, NODE *y)
    {
    	if(x->p == NULL)
    	{
    		r = y;
    	}
    	else if(x == x->p->left)
    	{
    		x->p->left = y;
    	}
    	else 
    		x->p->right = y;
    	
    	if(y != NULL)
    		y->p = x->p;
    	
    	return r;
    }

    其次是查找后继节点的函数,代码如下:

    //查找节点z的后继节点 
    NODE *tree_minimum(NODE *z)
    {
    	NODE *x = z;
    	while(x->left != NULL)
    		x = x->left;
    	
    	return x;
    }

    其他的如节点的数据结构,树的左旋和右旋的具体实现函数,见红黑树的插入那篇文章。


    展开全文
  • 红黑树 删除某节点后 旋转3次 举例

    千次阅读 2017-04-28 11:15:23
    下面对红黑树删除某节点后,旋转三次的例子做出详解: 先利用代码建立树如下: 修改颜色分布为下列树: 修改颜色分布后,利用 tree->insert(1); tree->remove(1); 来判断是否是红黑树 如果不是...
  • 红黑树删除的详细介绍

    千次阅读 2019-07-19 23:39:56
    要搞清楚红黑树删除,一定要结合红黑树的5个性质: 1. 每个节点或是红的或是黑的 2. 根节点为黑色 3. 外部节点是黑色的 4. 如果一个结点是红色的,那么它的两个儿子都是黑色的 (红红不能相连) 5. 对每个...
  • 算法导论---红黑树删除详解

    千次阅读 2013-01-26 23:27:01
    红黑树删除算法详解 删除算法相较于插入要稍微复杂些。 删除操作,首先与二叉树删除一致,找到删除的节点,若是只有左节点或者只有右节点或者没有左右子树,那么删除的节点就是原来的节点,只要将删除节点的父节点...
  • 红黑树删除一个节点,可以先用普通二叉搜索树的方法,将节点从红黑树删除掉,然后再将被破坏的红黑性质进行恢复。 首先我们来看看普通二叉树的节点删除方法:  我们回忆一下普通二叉树的节点删除方法:Z...
  • 学习红黑树知识点不清楚的,可以参考这篇博文红黑树原理以及插入、删除算法 附图例说明。 因为删除操作比插入操作较难理解,需要处理的情况比较多,便于简单记忆,及快速了解删除操作,特此发博文,三句话说清楚...
  • 红黑树 删除调整步骤终极详解

    千次阅读 2019-01-14 17:16:46
    红黑树删除无疑是最难的,抛开调整,红黑树的插入删除都跟选择二叉树一样,所以前面的步骤网上很多了,在这里只讲如何调整,以满足红黑树性质。  还是从头到尾理一下吧...  先定义一下,删除节点为d,真实删除...
  • 红黑树删除节点——这一篇就够了

    千次阅读 多人点赞 2019-10-11 11:38:24
    并且它对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保,对于红黑树的概念、性质、插入、查找和旋转等这里不再多讲,不了解的请点击wikipedia rb-tree,这里重点讲一下红黑树删除,这是红黑树中最难...
  • 老话说一说,本人菜鸡,如果文章中有错误请大家批评指出!!! 该系列已经全部更完,有5篇文章: ...【算法】红黑树插入数据(变色,左旋、右旋)(二):https://blog.csdn.net/lsr40/article/details/8...
  • 在看源码之前,先说说红黑树寻找 待删除节点t 的 后继节点 的过程: 如果待删除节点t有右节点,那么后继节点为该节点右子树中最左的节点,也就是右子树中值最小的节点 如果待删除节点t无右节点,那么后继节点是向上...
  • 红黑树删除一个结点y,如果y没有孩子而且y是红色的,则直接删除。 如果y有一个孩子(单孩子必定是红色,所以y为黑色),则把y的值替换成孩子的值,移除x即可。 如果y有两个孩子,最终删除的是后继,而后继最多...
  • Java实现数据结构——红黑树删除

    千次阅读 2018-05-01 12:59:27
    回顾红黑树基本性质 每个节点或是红色,或是黑色 根节点是黑色 每个叶节点是黑色 如果一个节点是红色,那么它的两个子节点都是黑色 对于每个节点,从该节点到其所有后代叶节点的简单路径上,包含相同数目的黑色...
  • 否则无法满足红黑树黑色节点完全平衡的特性(从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点) 如果删除节点有两个子节点时,使用后继节点作为替换的删除节点,然后再按照前面两种情况处理 删除...
  • 红黑树删除本质 与 伪代码分析

    千次阅读 2014-03-28 15:44:47
    性质1. 节点是红色或黑色。 性质2.... 性质3....性质4....(从每个叶子到根的所有路径上不能有两个连续的红色节点) ...红黑树删除操作是在二叉树删除操作后(加入Nil[T]节点,并修改NULL判断逻辑),加入调整函数,使得
  • 红黑树节点的删除分为两步: 第一步与二叉查找树的删除操作相似,第二步为调整节点的着色,使其满足红黑树性质。  节点删除 首先查找待删除的节点z,找到它的位置,此时有如下情况需要考虑:  节点z为根...
  • 本文是我个人整理的关于双黑问题的场景处理过程.
  • 我的前三篇文章讲红黑树的插入介绍完毕,并且也解释了TreeMap的put的源码,接下来我们一起看下remove,红黑树如何删除节点? 该系列已经全部更完,有5篇文章:   【算法】红黑树(二叉树)概念与查询(一):...
  • 一、红黑树介绍 红黑树是特殊的二叉查找树,具有以下五个特点: (1) 节点为黑色或红色 (2)根节点为黑色 (3) 红色节点不能连续 ...在红黑树删除和插入之后,为了保持红黑树的状态,可能需要用到...
  • 前面我们讨论了红黑树的插入的实现,基本思想是分类讨论;然后分情况讨论以后我们发现插入操作调整函数只需要处理三种情况,并不是太复杂。但是删除操作会更复杂一点...下面先放出红黑树删除函数的代码://红黑树删除
  • 红黑树生成删除

    2019-07-04 17:36:38
    红黑树在线生成的一个工具,从网上找的,我这样应该得不到分。大哭https://www.cnblogs.com/bbvi/p/5576201.html 删除可能存在问题,替换节点的兄弟节点为黑色节点时有问题,其他部分是没有问题的,凑合着看看
  • 红黑树插入删除算法

    2014-09-27 11:27:36
    红黑树插入删除算法,算法导论上算法,可以运行
  • 该资源描述了红黑树插入删除的伪算法,并提供相关图示
  • 红黑树

    万次阅读 2011-02-11 21:56:00
    红黑树和之前所讲的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。...
  • 红黑树插入删除详解

    万次阅读 多人点赞 2018-07-11 15:54:05
    红黑树插入删除操作的介绍转载自:红黑树 练习题转载自:红黑树练习 R-B Tree简介  R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,...
  • 红黑树插入,删除时各种状态的平衡操作。
  • 教你初步了解红黑树

    万次阅读 多人点赞 2010-12-29 18:36:00
    教你透彻了解红黑树 作者:July、saturnman 2010年12月29日本文参考:Google、算法导论、STL源码剖析、计算机程序设计艺术。推荐阅读:Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data Structures, ...
  • 红黑树系列三:红黑树删除

    千次阅读 2014-10-11 22:24:01
    一、红黑树定义  红黑树需要满足下面4个条件:  1、每个节点不是红色就是黑色。...二、红黑树删除 对二叉查找树,我们知道删除的结点可能有三种情况:(1)为叶子结点,(2)左子树或右子树有

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 69,799
精华内容 27,919
关键字:

红黑树删除