红黑树的基本性质

1. 每个结点非黑即红
2. 红结点的子结点必须是黑色
3. 根结点和外结点(nil结点)必须是黑色
4. 每个结点到其子孙结点包含相同数目的黑结点

插入

插入的核心流程如下:首先将要插入的结点着为红色，然后按照普通二叉树方式插入数中，因为被着色于红色，所以除了父结点是红色造成冲突之外，无其他冲突，所以核心问题就是解决和父结点的红色冲突问题。

冲突解决思路如下:

1. 如果父结点是红色，叔父结点也是红色的话，祖父结点肯定是黑色，这里将祖父结点变红，父节点和叔父结点都变黑，这里黑高度无变黑，除了祖父结点变红可能会引起冲突外，无其他冲突，该结点变其祖父结点，这样循环到到不满足这样的条件为止。
2. 到这里的话，现在的情况就是父结点是红色，叔父结点是黑色的了，接下来就要看该结点和父节点以及祖父结点关系了，如果是<或者>形状的话，那么旋转其父节点，使其变成/或者\的形状，父子结点交换了位置，到情况3了。
3. 现在该结点(红)和父节点(红)以及祖父结点(黑)之间的关系是/或者\了，现在旋转其祖父结点成^这样的形状，然后交换父结点和祖父结点的颜色，大功告成。