算法导论中，红黑树删除操作中图 13.7 如何理解？

Question

在《算法导论》第三版红黑树这一章中，红黑树的删除操作，书中给了一个图 13.7 :

但是我发现似乎有一个问题，就是里面的 x 节点，在我自己的理解中，x 要么是一个红节点，要么是一个 NIL 的叶节点，而不是图 13.7 中的内部节点，理由如下：

如果 z 的儿子数小于 2，那么由于其某一个子树为空，所以其黑高度为 1 ，此时另一子树的黑高度也必为 1，所以 x 作为 y 的非空子树，要么为 NIL ，要么为红节点

如果 z 的儿子数等于 2，那么 y 是 z 的后继，而 y 的左子树必为空，所以其右子树的黑高度必为 1，所以 x 作为 y 的右子树，要么为 NIL，要么为红节点

我觉得我的理解应该是没有错的，但是跟书中的图不符合，我不知道是不是我理解错了还是什么地方被我忽略了？

麻烦大家了。

Answer 1

首先，z的儿子数小于等于2的情况是可以那么理解的。但是，为什么z的儿子数九一定小于等于2？

注意到delete操作中有一步：

else
  {
    y=TREE_MINIMUM(z->right);
    y_original_color=y->color;
    //其余部分
    RB_transplant(y,y->right);
    RB_transplant(z,y);
  }

这一步完成了移植，其中，子树的情况很可能是这样的：

这个时候执行transplant之后y就变成内节点了啊~

图中的颜色我随便画的，实际上必须满足红黑树的性质。