关于红黑树的论述,讲得很仔细

所需积分/C币:5 2018-06-26 13:04:36 501KB PDF
4
收藏 收藏
举报

红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。 它是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删
憤形1:新节点N位于树的根上,没有父节点。在这种情形下,我们把它重绘为黑色以满足性质2。因为它在每个路 径上对黑节点数目增加一,性质5匹配。 void insert_case 1(node *n) if(n→ parent==NUL) n->color= bLACK. insert case2(n) 情形2:新节点的父节点P是黑色,所以性质4没有失效(新节点是红色的)。在这种情形下,树仍是有效的。性质 5也未受到威胁,尽管新节点N有两个黑色叶子子节点;但由于新节点N是红色,通过它的每个子节点的路径就都 有同通过它所替换的黑色的叶子的路径同样数目的黑色节点,所以依然满足这个性质。 void insert case 2 (node *n) if(n->parent-color== BLACK) return;/*树仍归有效* else insert_ case3(n) 注意:在下列情形下我们假定新节点的父节点为红色,所以它有祖父节点;因为如果父节点是根节点,那父节点 就应当是黑色。所以新节点总有一个叔父节点,尽管在情形4和5下它可能是叶子节点。 情形3:如果父节点P和叔父节点U二者都是红色,(此时新插入节点 Q N做为P的左子节点或右子节点都属于情形3,这里右图仅显示N做 为P左子的情形)则我们可以将它们两个重绘为黑色并重绘祖父节 d痉意→向点点意 点G为红色(用来保持性质5)。现在我们的新节点N有了一个黑色 的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过A 祖父节点G,在这些路径上的黑节点数目没有改变。但是,红色的 祖父节点G可能是根节点,这就违反了性质2,也有可能祖父节点G的父节点是红色的,这就违反了性质4。为了 解决这个问题,我们在祖父节点G上递归地进行情形1的整个过程。(把G当成是新加入的节点进行各种情形的检 查) void insert_ case3(node *n) if(uncle(n)i= NULL & uncle(n)->color = RED)( n->parent->color=bLACK; uncle(n)->color=BLACK grandparent (n)->color =RED insert_case1(grandparent(n)): else insert case4 (n) 注意:在余下的情形下,我们假定父节点P是其父亲G的左子节点。如果它是右子节点,情形4和情形5中的左和右 应当对调。 情形4父节点P是红色而叔父节点U是黑色或缺少,并且新节点N是其 父节点P的右子节点而父节点又是其父节点的左子节点在这种情形Q如 下,我们进行一次左旋转调换新节点和其父节点的角色接着,我们按 白A→白息△A 情形5处理以前的父节点P以解决仍然失效的性质4。注意这个改变会 导致某些路径通过它们以前不通过的新节点N(比如图中1号叶子节 点)或不通过节点P(比如图中3号叶子节点),但由于这两个节点都 是红色的,所以性质5仍有效。 void insert case 4(node *n) if(n ==n->parent->right &&n->parent== grandparent(n)->left) rotate_left(n->parent >left B else if(n== n->parent->left && n->parent== grandparent(n)->right)I rotate_right(n->parent) n=n->right insert case5(n) 情形5:父节点P是红色而叔父节点∪是黑色或缺少,新节点N是 这种博形下们进行计对相父节的一次右:在放产白点→只白 其父节点的左子节点,而父节点P又是其父节点G的左子节点。在 生的树中,以前的父节点P现在是新节点N和以前的祖父节点G的 父节点。我们知道以前的祖父节点G是黑色,否则父节点P就不可A 能是红色(如果P和G都是红色就违反了性质4,所以G必须是黑 色)。我们切换以前的父节点P和祖父节点G的颜色,结果的树满足性质4。性质5也仍然保持满足,因为通过这 三个节点中任何一个的所有路径以前都通过祖父节点G,现在它们都通过以前的父节点P。在各自的情形下,这都 是三个节点中唯一的黑色节点。 void insert_case5(node *n) n->parent->color= BLACK grandparent(n)->color=RED; if(n==n->parent->left & n->parent = grandparent (n)->left)[ rotate_right(grandparent(n)); y else i / Here, n== n-parent->right & n->parent = grandparent (n)->right * rotate_left(grandparent(n)): 注意插入实际上是原地算法,因为上述所有调用都使用了尾部递归。 删除 如果需要删除的节点有两个儿子,那么问题可以被转化成删除另一个只有一个儿子的节点的问题(为了表述方 便,这里所指的儿子,为非叶子节点的儿子)。对于二叉查找树,在删除带有两个非叶子儿子的节点的时候,我 们找到要么在它的左子树中的最大元素、要么在它的右子树中的最小元素,并把它的值转移到要删除的节点中 如在这里所展示的那样)。我们接着删除我们从中复制出值的那个节点,它必定有少于两个非叶子的儿子。因 为只是复制了一个值,不违反任何性质,这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这 个节点是最初要删除的节点还是我们从中复制出值的那个节点。 在本文余下的部分中,我们只需要讨论删除只有一个儿子的节点(如果它两个儿子都为空,即均为叶子,我们任 意将其中一个看作它的儿子)。如果我们删除一个红色节点(此时该节点的儿子将都为叶子节点),它的父亲和 儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它,并不会破坏性质3和性质4。通过被删除节点的 所有路径只是少了一个红色节点,这样可以继续保证性质5。另一种简单情况是在被删除节点是黑色而它的儿子是 红色的时候。如果只是去除这个黑色节点,用它的红色儿子顶替上来的话,会破坏性质5,但是如果我们重绘它的 儿子为黑色,则曾经通过它的所有路径将通过它的黑色儿子,这样可以继续保持性质5。 需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候,这是一种复杂的情况。我们首先把要删除 的节点替换为它的儿子。出于方便,称呼这个儿子为N(在新的位置上),称呼它的兄弟(它父亲的另一个儿 子)为S。在下面的示意图中,我们还是使用P称呼N的父亲,SL称呼S的左儿子,SR称呼S的右儿子。我们将使用 下述函数找到兄弟节点 struct node h sibling(struct node *n if(n==n→ parent>eft) return n->parent->right; else return n->parent->left 我们可以使用下列代码进行上述的概要步骤,这里的函数 replace_node替换chd到n在树中的位置。出于方 便,在本章节中的代码将假定空叶子被用不是NULL的实际节点对象来表示(在插入章节中的代码可以同任何一种 表示一起工作)。 void delete one child (struct node +n) x Precondition n has at most one non-null child struct node *child =is_leaf(n->right)? n->left: n->right replace noden, child) if(n->color== BLACKR if(child->color== RED) child->color blacK: else delete_case1(child) free(n) 如果N和它初始的父亲是黑色,则删除它的父亲导致通过N的路径都比不通过它的路径少了一个黑色节点。因为这 违反了性质5,树需要被重新平衡。有几种情形需要考虑: 情形1:N是新的根。在这种情形下,我们就做完了。我们从所有路径去除了一个黑色节点,而新根是黑色的,所 以性质都保持着。 delete casel(struct node *n if(n->parent= NULL delete case2(n) 注意:在情形2、5和6下,我们假定N是它父亲的左儿子。如果它是右儿子,则在这些情形下的左和右应当对调。 情形2:S是红色。在这种情形下我们在N的父亲上做左旋转,把红Q 色兄弟转换成N的祖父,我们接着对调N的父亲和祖父的颜色。完 成这两个操作后,尽管所有路径上黑色节点的数目没有改变,但现 在N有了一个黑色的兄弟和一个红色的父亲(它的新兄弟是黑色因 Ag→回自点 为它是红色S的一个儿子),所以我们可以接下去按情形4情形5 或情形6来处理。 (注意:这里的图中没有显示出来,N是删除了黑色节点后替换上来的子节点,所以这个过程中由P>XN变成了 P>N,实际上是少了一个黑色节点,也可以理解为 Parent(B|ack)和 Silting(Red那么他们的孩子黑色节点的数目 肯定不等,让他们做新兄弟肯定是不平衡的,还需后面继续处理。这里看英文版本的[1比较的明了) void delete case 2(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 else rotate_right(n->parent) delete_ case3(n) 情形3:N的父亲、S和s的儿子都是黑色的。在这种情形下,我 们简单的重绘S为红色。结果是通过S的所有路径,它们就是以前( 不通过N的那些路径,都少了一个黑色节点。因为删除N的初始 g自→AgQ 的父亲使通过N的所有路径少了一个黑色节点,这使事情都平衡 了起来。但是,通过P的所有路径现在比不通过P的路径少了一个 A点压点质 黑色节点,所以仍然违反性质5。要修正这个问题,我们要从情 形1开始,在P上做重新平衡处理。 void delete_case3(struct node *n) struct node *s=sibling(n); if((n->parent->color ==BLACK)&& (s->color ==BLACK)&& S->left->color ==BLACK)&& (s->right->color==BLACK))i s→ color=RED; delete_case1(n->parent) e delete case4(n): 情形4:S和S的儿子都是黑色,但是N的父亲是红色。在这种情 形下,我们简单的交换N的兄弟和父亲的颜色。这不影响不通过 N的路径的黑色节点的数目,但是它在通过N的路径上对黑色节 点数目增加了一,添补了在这些路径上删除的黑色节点。 void delete case 4(struct node *n struct node *s= sibling(n): if((n->parent->color== RED)&& S->color = BLACK)&& (s->left->color==bLACK)&& (s->right->color=BLACK))( s->color= RED n→> parent→> color= BLACK; delete case5(n) 情形5:S是黑色,S的左儿子是红色,S的右儿子是黑色,而N是它父亲的 左儿子。在这种情形下我们在S上做右旋转,这样S的左儿子成为S的父亲 和N的新兄弟。我们接着交换S和它的新父亲的颜色。所有路径仍有同样数 目的黑色节点,但是现在N有了一个黑色兄弟,他的右儿子是红色的,所 愿急A 以我们进入了情形6。N和它的父亲都不受这个变换的影响。 void delete case5(struct node *n) struct node *s= sibling(n) if(s->color==BLACK/* this if statement is trivial, due to Case 2(even though Case two changed the sibling to a sibling's child the sibling 's child can 't be red, since no red parent can have a red child). */ // the following statements just force the red to be on the left of the left of the parent, //or right of the right, so case six will rotate correctly if((n==n->parent->left)&& (s->right->color ==BLACK)&& (s->left->color = RED))(//this last test is trivial too due to cases 2-4 s->color= RED s->left->color= bLACK rotate_right(s); I else if((n==n->parent->right)&& (s->left->color==bLACK)&& (s->right->color==RED)V//this last test is trivial too due to cases 2-4 s->color= RED s->right->color= BLACK, rotate_ left(s) delete_case(n) 情形6:S是黑色,S的右儿子是红色,而N是它父亲的左儿子。在 这种情形下我们在N的父亲上做左旋转,这样S成为N的父亲(P) 和S的右儿子的父亲。我们接着交换N的父亲和S的颜色,并使S的 右儿子为黑色。子树在它的根上的仍是同样的颜色,所以性质3没 有被违反。但是,N现在增加了一个黑色祖先:要么N的父亲变成 点意 黑色,要么它是黑色而S被增加为一个黑色祖父。所以,通过N的 路径都增加了一个黑色节点。 此时,如果一个路径不通过N,则有两种可能性 ■它通过N的新兄弟。那么它以前和现在都必定通过S和N的父亲,而它们只是交换了颜色。所以路径保持了同样 数目的黑色节点 它通过N的新叔父,S的右儿子。那么它以前通过S、S的父亲和S的右儿子,但是现在只通过S,它被假定为它 以前的父亲的颜色,和S的右儿子,它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。 在任何情况下,在这些路径上的黑色节点数目都没有改变。所以我们恢复了性质4。在示意图中的白色节点可以 是红色或黑色,但是在变换前后都必须指定相同的颜色。 delete cases(struct node *n struct node *s= sibling(n); s->color=n->parent->color: n->parent->color= BLACK if(n==n->parent->left s->right->color BLACK rotate_left(n->parent helse i s-left→> color= BLACK rotate_right(n->parent): 同样的,函数调用都使用了尾部递归,所以算法是原地算法。此外,在旋转之后不再做递归调用,所以进行了恒 定数目(最多3次)的旋转。 C+示例代码 #define black 1 #define red o using namespace std: class bst i private struct Node i int value bool color. Node *leftTree, *rightTree, *parent Node( i color= RED lefttree= NULL. rightTree= nULl: parent= NULL value=0 Node* grandparent(t f(parent==NULL) return nUlL return parent->parent, Node* uncle(i if(grandparent()==NULL)i return null if(parent= grandparent()->rightTree return grandparent()->leftTree else return grandparent()->rightTree: Node* sibling(t if(parent->left Tree = this return parent->rightTree else return parent->lefttree: void rotate_right(Node *p Node *gp=p->grandparent() Node *fa=p->parent Node y= p->rightTree fa->leftTree =y: if(y l=NIL) y->parent = fa p->rightTree=fa fa→ parent=p; if(root= fa) root p->parent= gp if(gp l=NULL)

...展开详情
试读 17P 关于红黑树的论述,讲得很仔细
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
上传资源赚钱or赚积分
最新推荐
关于红黑树的论述,讲得很仔细 5积分/C币 立即下载
1/17
关于红黑树的论述,讲得很仔细第1页
关于红黑树的论述,讲得很仔细第2页
关于红黑树的论述,讲得很仔细第3页
关于红黑树的论述,讲得很仔细第4页

试读结束, 可继续读2页

5积分/C币 立即下载