关于红黑树的插入

[hongjia]

4.1定义一节中，红黑树满足5条性质，有：

\item 所有叶节点（NIL）为黑色。

这里叶节点是指没有数据的NIL节点。

4.2插入一节中，公式（4.5）后有：

如果树为空，我们为 k 创建一个红色叶子节点；

这里的叶子节点应该是指隐藏NIL节点的红黑树表示中的叶子节点，即实际上创建的是带两个NIL子节点的中间节点。因为，在4.2节第一段中，有：

插入时，我们令新节点为红色。只要它不是根节点，除了第四条外的所有性质都可以满足。

如果新节点是带NIL节点表示中的叶子节点（即它不带NIL为子），由于新插入节点为红色，上述红黑树性质并不满足。

所以，我感觉这里明确一下会更好，能够和图示与算法更好地一致。图4.6“插入后需要修复的四种情况”的示例和公式（4.3）的模式匹配表述中，新插入节点都是带有子节点的。我开始在这里迷惑了很久，去网上查了一些2-3-4树和红黑树的讲解才明白过来。

也就是说，在红黑树中，所有带数据的节点都是中间节点，它必定有两个子，或为子树，或为NIL节点。

[liuxinyu95]

多谢指出，这一处应该写清楚。已修改：25bff64