Potential error in the algorithm RB-INSERT-FIXUP in CLRS (p.316, 3rd ed.)?# JobHunting - 待字闺中
B*7
1 楼
最近在学CLRS，觉得RB-INSERT-FIXUP有bug。拿出来和大家讨论一下。
The case 1 in the algorithm deals with case that the parent and the uncle of
the newly inserted node are both red nodes. Lines 4-8 repaint the parent
and the uncle into black and the grandparent into red, and then the current
node z moves up to the grandparent as in line 8. However, that shouldn't be
the end of the case. Instead, the routine should recursively call itself, i.
e., there should be statement after line 8 like this:
RB-INSERT-FIXUP(T, z)
Any comments?
The case 1 in the algorithm deals with case that the parent and the uncle of
the newly inserted node are both red nodes. Lines 4-8 repaint the parent
and the uncle into black and the grandparent into red, and then the current
node z moves up to the grandparent as in line 8. However, that shouldn't be
the end of the case. Instead, the routine should recursively call itself, i.
e., there should be statement after line 8 like this:
RB-INSERT-FIXUP(T, z)
Any comments?