上篇文章我们主要认识了二叉树搜索树，这篇文章正式介绍红黑树。 红黑树在二叉搜索树的基础上，加了些性质，包含`color`、`key`、`left`、`right`、`p`，颜色取值为红色或者黑色，此外，我们把NIL节点视为特殊的节点，具体而言，视为外部节点，也叫叶子节点，把带有关键字的节点视为内部节点。 ...

红黑树是二叉搜索树中的一种，只不过增加了一个性质“在所有的叶子到根的路径中，没有一条路径会比其他路径长出2倍”，因此，可以保证最坏情况下基本动态集合操作（例如删除节点、插入节点和查找节点）的时间复杂度为`O(lg n)`，本篇是第一部分，二叉搜索树。 ...