算法导论中,红黑树删除操作中图 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