红黑树伪code冗余

本文介绍了红黑树伪code冗余的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

在算法导论第三版他们有红黑树删除伪code实现。这是...

In introduction to Algorithms Third Edition they have a pseudocode implementation of red-black tree deletion. Here it is...

RB-DELETE(T, z) y = z y-original-color = y.color if z.left == T.nil x = z.right RB-TRANSPLANT(T, z, z.right) elseif z.right == T.nil x = z.left RB-TRANSPLANT(T, z, z.left) else y = TREE-MINIMUM(z.right) y-original-color = y.color x = y.right if y.p == z x.p = y // <--------- why???? else RB-TRANSPLANT(T, y, y.right) y.right = z.right y.right.p = y RB-TRANSPLANT(T, z, y) y.left = z.left y.left.p = y y.color = z.color if y-original-color == BLACK RB-DELETE-FIXUP(T, x)

树最小只是发现在一棵树的最小值，RB移植需要的第二个参数的父母已经将其指向第三个参数，并有第三个参数的父母是第二个参数的父。

TREE-MINIMUM just finds the smallest value in a tree, RB-TRANSPLANT takes the parent of the second parameter and has it point to the third parameter, and has the third parameter's parent be the second parameter's parent.

通过我的评论，他们测试是否YP为z，如果是一套XP为y。但X是已经y.right，所以这好像是说y.right.p = Y，但y.right.p已经是Y！他们为什么这样做？

By my comment, they test if y.p is z and if so set x.p to y. But x is already y.right, so this is like saying y.right.p = y, but y.right.p is already y! Why are they doing this?

下面是他们的解释......

Here is their explanation...

y的原来的母公司为z，但是，我们不希望XP指向为y原有的母公司，因为我们卸下从树节点。由于节点Y将向上移动采取树Z的位置，设置XP为y在第13行的原因XP指向为y的父的原始位置，甚至如果x == T.nil。

"When y's original parent is z, however, we do not want x.p to point to y's original parent, since we are removing that node from the tree. Because node y will move up to take z's position in the tree, setting x.p to y in line 13 causes x.p to point to the original position of y's parent, even if x == T.nil."

所以，他们希望保持X的父母为y ...它已经是Y ...

So they want to keep x's parent to be y...it already is y...

推荐答案

他们指出在X可以是还无，即当y.right是无文字。这似乎是无本code也重新由节点psented $ P $，他们不想留下悬摆指针。

They state in the text that x can be also Nil, i.e. when y.right is Nil. It seems Nil is in this code also represented by a node, and they don't want to leave a dangling pointer.