Incorrect if statement condition in Insertion Sort Improvement 2

[po2xel]

Hi @liuxinyu95 ,
Thanks for this open-source algorithm book. I am reading it and find an incorrect if statement condition in Insertion Sort Improvement 2.

\begin{algorithmic}
\Function{Insert}{$L, x$}
  \State $p \gets$ NIL
  \State $H \gets L$
  \While{$L \neq$ NIL $\land $ \Call{Key}{$L$} $<$ \Call{Key}{$x$}}
    \State $p \gets L$
    \State $L \gets $ \Call{Next}{$L$}
  \EndWhile
  \State \Call{Next}{$x$} $\gets L$
  \If{$p \neq$ NIL}                           // It should be \If{$p \eq$ NIL}, right?
    \State $H \gets x$
  \Else
    \State \Call{Next}{$p$} $\gets x$
  \EndIf
  \State \Return $H$
\EndFunction
\end{algorithmic}

Best Regards,

[po2xel]

And the Red-Black tree in Figure 3.4: An example red-black tree is not correct. The leaf (NIL) isn't drawn as black as shown in the wiki page: https://en.wikipedia.org/wiki/File:Red-black_tree_example.svg
It leads to confusion when I read the properties and the example shown in Figure 3.4.

[liuxinyu95]

You are right.
I updated the insertion sort algorithm with this fix:
7d9891c

I'll next check the red-black tree figure issue.

[liuxinyu95]

I added a figure to shown the NIL nodes, then explain the reason why we'll ignore the black NIL nodes in the rest of the book. See the following commit:
8da19de

Here is the sample chapter with this change.
rbtree-en.pdf