向红黑二叉树中的节点添加 .size 属性（伪代码）

Question

在我的 CS 课程中，我的任务是向红黑二叉树中的节点添加大小属性。节点的大小是其子树中节点的数量。 当对 RB 树进行更改时，尤其是左旋转算法、插入算法和插入修复算法发生更改时，必须更新此属性。这 3 个算法取自 CLRS，并且是伪代码。

我首先修改了左旋转算法来更新修改节点的大小。 T 是树，x 是要旋转的节点。
LEFT-ROTATE(T,x)

y = x.right
x.right = y.left
if y.left != T.nil:
    y.left.p = x
y.p = x.p
if x.p == T.nil
    T.root = y
else if x == x.p.left
    x.p.left = y
else 
    x.p.right = y
y.left = x
x.p = y

x.size = x.left.size + x.right.size 
y.size = y.left.size + y.right.size 

我自己添加了最后两行，这会更新大小。

接下来是插入，其中 T 是树，z 是要插入的节点： RB-INSERT(T,z)

y = T.nil
x = T.root
while x != T.nil
    y = x
    if z.key < x.key
        x = x.left
    else 
        x = x.right
    y.size++
z.p = y 
if y == T.nil
    T.root = z
else if z.key > y.key
    y.left = z
else y.right = z
z.left = T.nil
z.right = T.nil
z.color = RED
RB-INSERT-FIXUP(T,z)

修复非常简单，我只是在 while 循环的末尾插入 y.size++ ，因为每次我们进一步沿着树向下走时，我们都会更新父级的大小。

现在我当前的问题来了，更新 RB-INSERT-FIXUP 算法中的大小。我还没有添加任何代码，但这里是要修改的算法：

RB-INSERT-FIXUP(T,z)
while z.p.color == RED
    if z.p == z.p.p.left
        y = z.p.p.right
        if y.color = RED
            z.p.color = BLACK
            y.color = BLACK
            z.p.p.color = RED
            z = z.p.p
        else if z == z.p.right
            z = z.p
            LEFT-ROTATE(T,z)
        z.p.color = BLACK
        z.p.p.color = RED
        RIGHT-ROTATE(T,z.p.p)
    else(Same as then clase with "right and "left" exchanged)
T.root.color = BLACK

假设在 INSERT-FIXUP 中，LEFT-ROTATE 和 RIGHT-ROTATE 也更新了它们自己的算法中的大小。

因此，我必须更新在 INSERT-FIXUP 中移动的相关节点的大小。我不知道该怎么做。 据我所知，甚至不需要更新 FIXUP 中的尺寸，因为它对 Left 和 Right 旋转的调用已经更新了尺寸。我的说法正确吗，还是我错过了什么？ 这对我来说听起来很合乎逻辑，但任务告诉我要修改它，以便更新大小字段，所以如果不修改它，答案就是相当混乱。