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


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

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

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

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

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

麻烦大家了。

算法导论 红黑树 数据结构 算法 平衡树

、Cyd. 9 years, 6 months ago

Your Answer