算法导论中红黑树的伪代码中的坑

2016年02月29日 原创
关键词: C++ 数据结构 算法导论
摘要 算法导论13章红黑树里的RB-INSERT-FIXUP伪代码中的坑。

在算法导论178页的红黑树的RB-INSERT-FIXUP伪代码中,由于伪代码在缩进之后翻页,导致这一段伪代码中有很多坑。

坑一:

elseif 和 else if

其中else if表示的是else { if{..} }

在RB-INSERT-FIXUP的第9行的else if其实并不是经常在编程里用的elseif

坑二:

由于缩进后翻页,导致伪代码不够清晰。

完整的伪代码如下:

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 clause with "right" and "left" exchanged) //这里的else是对应的第2行的if

   T.root.color = BLACK