红黑树-维基百科

所需积分/C币:36 2019-03-10 21:46:50 2.46MB PDF
47
收藏 收藏
举报

红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组
2018/3/27 红黑杯-维基百科,白出的百科仝书 node* grandparent(node *n return n>parent->parent node* uncle(node *n)( if(n->parent== grandparent(n)->left) return grandparent (n)right IllIiiliili else return grandparent (n)->left 情形1:新节点N位于树的根上,没有父节点。在这种情形下,我们把它重绘为黑色以满足性质2。因为它在每个路径上对 黑节点数日增加一,性质5匹配。 void insert casel(node *n n>color= blacK insert case2 ( n) 情形2:新节点的父节点P是黑色,所以性质4没有失效(新节点是红色的)。在这种情形卜,树仍是有效的。性质5也木 受到威胁,尽管新节点N有两个黑色叶子子节点;但由于新节点N是红色,通过它的每个子节点的路径就都有同通过它 所取代的黑色的叶子的路径同样数目的黑色节点,所以依然满足这个性质 ========== ===== ====================-=========-====-===== d void insert case2(node *n) if(n>parent>color BLACK) return;/*州仍∥有效 insert case3 世mmm -= 注意:在下列情形下我们假定新节点的父节点为红色,所以它有祖父节点;因为如果父节点是根节点,那父节点就应当 是黑色。所以新节点总有一个叔父节点,尽管在情形4和5下它可能是叶子节点 情形3:如果父节点P和叔父节点U二者都是红色,(此时新插入节 点N做为P的左子节点或右子节点都属于情形3,这里右图仅显示 N做为P左子的情形)则我们可以将它们两个重绘为黑色并重绘祖 父节点G为红色(用来保持性质5)。现在我们的新节点N有了 向虚→亲 个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都 必定通过祖父节点G,在这些路径上的黑节点数目没有改变。但 是,红色的祖父节点G可能是根节点,这就违反了性质2,也有可 能祖父节点G的父节点是红色的,这就违反了性质4。为了解决这个问题,我们在祖父节点G上递归地进行情形1的整个 过程。(把⑤当成是新加入的节点进行各种情形的检查) ,,,,,,, void insert case3 (node *n)[ if(uncle(n)!= nulL & uncle (n)->color=RED) parent>calor= BLACK clc (n)->color- blACK grandparent (n)->color-RED insert casel(grandparent(n)) insert case4 (n) https:/zh.wikipediaorg/wiki/%e7%ba%a2%e9%bb%91%e6%a0%91 3/15 2018/3/27 红黑杯-维基百科,白出的百科仝书 注意:在余下的情形下,我们假定父节点P是其父亲G的左子节点。如果它是右子节点,情形4和情形5中的左和石应当 对调。 情形4父节点P是红色而叔父节点U是黑色或缺少,并且新节点N是其 Q Q 父节点P的右子节点而父节点P又是其父节点的左子节点。在这种情 形下,我们进行一次左旋转调换新节点和其父节点的角色接着,我 们按情形5处理以前的父节点F以解决仍然失效的性质4,注这个改 如→白区盈 变会导致某些路径通过它们以前不通过的新节点N(比如图中1号叶 子节点)或不过节(1如图中3号计子节点),但由于这两个点意 节点都是红色的,所以性质5仍有效 d void insert case 4(node *n)[ f(n== n>parent->right & n->parent == grandparent(n)->left left(n->parent n= n>left 3 else if(n==n->parent->left & n>parent= grandparent(n)->right rotate right(n->parent) insert case5 (n) 情形5:父节点P是红色而叔父节点∪是黑色或缺少,新节点N是 其父节点的左子节点,而父节点P又是其父节点G的左子节点 在这种情形下,我们进行针对祖父节点G的一次右旋转;在旋转 产生的树中,以前的父节点P现在是新节点N和以前的祖父节点 G的父节点。我们知道以前的祖父节点G是黑色,否则父节点P 就不可能是红色(如果P和G都是红色就违反了性质4,所以G必 须是黑色)。我们切换以前的父节点P和祖父节点G的颜色,结 果的树满足性质4。性质5也仍然保持满足,因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G,现在 它们都通过以前的父节点P。在各自的情形下,这都是三个节点中唯一的黑色节点。 void insert case5node *n olor= blacK grandparent (n)->color= RED if(n = n-parent->left & n->parent grandparent (n)->left) rotate right(grandparent(n)) els /it Here, n= n-parent -right & n-parent= grandparent n)-right * rotate left(grandparent(n)) 注意插入实际上是原地算法,因为上述所有调用都使用了尾部递归。 删除 如果需要删除的节点有两个儿子,那么问题可以被转化成删除另一个只有一个儿子的节点的问题(为了表述方便,这 里所指的儿子,为非叶子节点的儿子)。对于二叉查找树,在删除带有两个非叶子儿子的节点的时候,我们找到要么在 它的左子树中的最大元素、要么在它的右子树中的最小元素,并把它的值转移到要删除的节点中(如在这里所展示的那 样)。我们接着删除我们从中复制出值的那个节点,它必定有少于两个非叶子的儿子。因为只是复制了一个值,不违反 任何性质,这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删狳的芍点还是我们 从中复制出值的那个节点。 https:/zh.wikipediaorg/wiki/%e7%ba%a2%e9%bb%91%e6%a0%91 4/15 2018/3/27 红黑-维基百科,白出的百科仝书 在本文余下的部分中,我们只需要讨论删除只有一个儿子的节点(如果它两个儿子都为空,即均为叶子,我们任意将 其中一个看作它的儿子)。如果我们删除一个红色节点(此时该节点的儿子将都为叶子节点),它的父亲和儿子一定是 黑色的。所以我们可以简单的用它的黑色儿子替换它,并不会破坏性质3和性质4。通过被删除节点的所有路径只是少了 个红色节点,这样可以继续保证性质5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是 去除这个黑色节点,用它的红色儿子顶替上来的话,会破坏性质5,但是如果我们重绘它的儿子为黑色,则曾经通过它 的所有路径将通过它的黑色儿子,这样可以继续保持性质5。 需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候,这是一种复杂的情况。我们首先把要删除的节 点替换为它的儿子。出于方便,称呼这个儿子为N(在新的位置上),称呼它的兄弟(它父亲的另一个儿子)为S。在 下面的示意图中,我们还是使用P称呼N的父亲,S工称呼S的左儿子,SR称呼S的右儿子。我们将使用下述函数找到兄弟 节点 istruct node x Sibling(struct node *n if(n==n->parent->left) return n >parent>right return n->parent ->left 我们可以使用下列代码进行上述的概要步骤,这里的函数 replace node替换 child到n在树中的位置。出于方便,在本章 节中的代码将假定空叶子被用不是NULL的实际节点对象来表示(在牺入章节中的代码可以同任何一和袤示一起工 作 Void delete one child(struct node * n) k recondition, n has at most one non nu// chila struct node *child=is leaf(n-right)? n->left n->right replace node(n, child BLACK( f(child->color--RED hild->color- BLACK delete casc1 (child Iilil =〓==== 如果N和它初始的父亲是黑色,则删除它的父亲导致通过N的路径都比不通过它的路径少了一个黑色节点。因为这违反 了性质5,树需要被重新平衡。有几种情形需要考虑: 情形1:N是新的根。在这种情形下,我们就倣完了。我们从所有路径去除了一个黑色节点,而新根是黑色的,所以性质 都保持着 elete casel(struct node *r) if(n->parent ! NULL delete case2 ( n) ===== ======== 注意:在情形2、5和6卜,我们假定N是它父亲的左儿子。如果它是右儿子,则在这些情形卜的左和石应当对调。 https:/zh.wikipediaorg/wiki/%e7%ba%a2%e9%bb%91%e6%a0%91 5/15 2018/3/27 红黑杯-维基百科,白出的百科仝书 情形2:S是红色。在这种情形下我们在N的父亲上做左旋转,把 Q 红色兄弟转换成N的祖父,我们接着对调N的父亲和祖父的颜色。 这两个操作后,尽管所有路径上黑色节点的数目没有改变 但现在N有了一个黑色的兄弟和一个红色的父亲(它的新兄弟是黑 色因为它是红色S的一个儿子),所以我们可以接下去按情形4、 情形5或情形6来处理 (注意:这里的图中没有显示出来,N是删除了黑色节点后替换上来的子节点,所以这个过程中由P->X->N变成了P >N,实际上是少了一个黑色节点,也可以理解为 Parent( Black)和 Silbing(Red)那么他们的孩子黑色节点的数目肯定不 等,让他们做新兄弟肯定是不平衡的,还需后面继续处理。这里看英文版本的[1(hts;/ en.wikipedia. org/wki/Re d%E2%80%93 black tree)较的明了) loid delete case2(struct node *n) struct node *s= sibling (n) if(s->color--RED)( n->parent->color- RED s-color black if(n=n>parent->left rotate left(n->parent rotate right(n->parent delete casc3 (n) 情形3:N的父亲、S和S的儿子都是黑色的。在这种情形下, 我们简单的重绘S为红色。结果是通过S的所有路径,它们就是 以前不通过N的那些路径,都少了一个黑色节点。因为删除N的 初始的父亲使通过N的所有路径少了一个黑色节点,这使事情△△ gQ→g自 都平衡了起来。但是,通过P的所有路径现在比不通过P的路径 少了—个黑色节点,所以仍然违反性质5。要修正这个问题,我 们要从情形开始,在P上做重新平衡处理。 鼠void delete case3(struct node =n) struct node *s= sibling (n) if((n->parent->color==BLACK)&& BLaCK&& i s->left>color = BlACK)&& (s->right->color- BLACk))( s->color= red delete casel(n->parent) e⊥se https:/zh.wikipediaorg/wiki/%e7%ba%a2%e9%bb%91%e6%a0%91 6/15 2018/3/27 红黑树-维基百科,白由的百科全书 情形4:S和S的儿子都是黑色,但是N的父亲是红色。在这种 情形下,我们简单的交换N的兄弟和父亲的颜色。这不影响不 通过N的路径的黑色节点的数目,但是它在通过N的路径上对黑 色节点数目增加了一,添补了在这些路径上朋除的黑色节点,△△国 void delete case(struct nodc *n T!!!!!!!l struct node *s= sibling (n if ((n">parent->color =- RED)&& is->color=- BLACK)&& (s->left->color==)&& (s right->color= BLACk))( s→> color-RED n->parent->color- BLACK delete casc5 (n !!!!I L========= 情形5:S是黑色,S的左儿子是红色,S的右儿子是黑色,而N是它父亲的 左儿子。在这种情形下我们在S上做右旋转,这样S的左儿子成为S的父亲和 N的新兄弟。我们接着交换S和它的新父亲的颜色。所有路径仍有同样数目 的黑色节点,但是现在N有了一个黑色兄弟,他的右儿子是红色的,所以 我们进入了情形6。N和它的父亲都不受这个变换的影响。 A nnn void delete case5(struct node *n) struct node *s= sibling (n) if (s>colo BLACk vial idue to Case 2(even though Case two changed the sibling to a siblings chilo the sibling's child can t be red, since no red parent can have a red child che lelt ol ihie lelt ol li i/ or right of the right, so case six will rotate correct if((n =-n->parent->left)&& i(s->right->color= BLACK)&& is-left->color==reD)i this last test is trivial too due to cases 2-4 s>color= reD s>left>color= BlaCk rotate right (s y else if((n=-n->parent-right)&& :s->left-color==BlACK)&& (s->right->color=reD) this last test is trivial too duc to cases 2-d >color= red s->right->color- BLACK rotate left (s) delete case (n) ============== https:/zh.wikipediaorg/wiki/%e7%ba%a2%e9%bb%91%e6%a0%91 7/15 2018/3/27 红黑树-维基百科,白由的百科全书 情形6:S是黑色,S的右儿子是红色,而N是它父亲的左儿子。 在这种情形下我们在N的父亲上做左旋转,这样S成为N的父亲 (P)和S的右儿子的父亲。我们接着交换N的父亲和S的颜色,并 使5的右儿子为黑色子树在它的根上的仍是同样的颜色,所以性 质3没有被违反。但是,N现在增加了一个黑色祖先:要么N的父 亲变成黑色,要么它是黑色而S被增加为一个黑色祖父。所以,通 点意座 过N的路径都增加了一个黑色节点。 此时,如果一个路径不通过N,则有两种可能性 它通过N的新兄弟。那么它以前和现在都必定通过S和N的父亲,而它们只是交换了颜色。所以路径保 持了同样数目的黑色节点 ■它通过N的新叔父,S的右儿子。那么它以前通过S、S的父亲和S的右儿子,但是现在只通过S,它被 假定为它以前的父亲的颜色,和S的右儿子,它被从红色改变为黑色。合成效果是这个路径通过了同 样数目的黑色节点。 在任何情况下,在这些路径上的黑色节点数目都没有改变。所以我们恢复了性质4。在示意图中的白色节点可以是红色 或黑色,但是在变换前后都必须指定相同的颜色。 nu n void delete case(struct node * n) struct node *s= sibling (n) s>color=n>parent->color n>parent- >color= BLACK; if(n==n->parent->left)t s>right->color- BLACK rotate left(n->parent) s->lcft->color- BlaCK rotate right(n->parent) 同样的,函数调用都使用了尾部递归,所以算法是原地算法。此外,在旋转之后不再做递归调用,所以进行了恒定数目 (最多3次)的旋转 c++示例代码 https:/zh.wikipediaorg/wiki/%e7%ba%a2%e9%bb%91%e6%a0%91 815 2018/3/27 红黑杯-维基百科,白出的百科仝书 =de fine black 1 Fdcfinc red 0 include iostream> dusing namespace std: ic lass bst rivate struct node int value bo Node xleftTree, *rightTree, *parent Node(: value(0), color(rED), leftTree (\UlD), rightTree ( NULl), parent (null) Node* grandparent t if(parent = NULL)t return NULL return parent→ parent Node* uncle o ir(grandparent==NULL) return NULL if(parent= grandparentorightTree) return grandparent(->lcftTrec return grandparent.Tree Node* sibling i if(parent->leftTree == this return parent rightTree return parent->leftTree i void rotate right(Node p)t Node *gp= p>grandparent o Node *fa=p>parent; Node y=p>rightTree fa >leftTree= y if(y ! NIL) y->parent =fa: p-rightTree= fa fa->parent=p if(root = fa rolt=P p->parent- gp if( NULL)( elssp-leftTree gp->rightTree=p void rotatc_ _ lcft(Nodc *p) if(p->parent - NULL p return Node *gp= p>grandparent O Node *fa- p->parent https:/zh.wikipediaorg/wiki/%e7%ba%a2%e9%bb%91%e6%a0%91 9/15 2018/3/27 红黑杯-维基百科,白出的百科仝书 ghtiree = v: if(y ! NIL y->parent- fa P-pleftiree fa fa parent= p if(root== fa) p->paren NULL) if(gp->leftTree fa gp->leftTree =p else gp->righ void inorder(Node *p) t return if(p->leftTre inorder(p- >leftTree) lillililii cout s p-)valu if(p->rightTree inorder (p-rightTree string output Color (bool calor) f return color BLACK: RED Nodok gct Smallest Child(Nodc *p)f if(p-lef tTree--NIL) return p return getSmallestChild(p->leftTree i bool delete child (Node *p, int data) if(p >value data)( if(p->leftTrcc- NIL) return false return delete child(p->leftTree, data lse if(p->value( data)( if(p-rightTree=- NIL)( return false return delete child(p->rightTree, data llllil lse if(p->value= data)t if(p->right'Tree==NIL)( delete one child (p) return true Node *smallest= getSmallestChild(p->rightTree) swap(p->value, smallest->value delete one child (smallest) return true return false i void delete one child ( Node +p) Node *child-p->leftTree = NIL p->right Tree: p->leftTree if(p parent = NULL & p-leftTree= NIL & p rightTree= NIL)( p https:/zh.wikipediaorg/wiki/%e7%ba%a2%e9%bb%91%e6%a0%91 10/15

...展开详情
试读 15P 红黑树-维基百科
立即下载 身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 分享达人

关注 私信
上传资源赚钱or赚积分
最新推荐
红黑树-维基百科 36积分/C币 立即下载
1/15
红黑树-维基百科第1页
红黑树-维基百科第2页
红黑树-维基百科第3页

试读结束, 可继续读2页

36积分/C币 立即下载