红黑树是一种自平衡的二叉搜索树，红黑树的特殊请参考上文。
红黑树的插入
红黑树插入操作中有2个需要注意的地方，一个是着色，另一个就是旋转。插入一个节点和二叉搜索树的插入一样需要找到要插入的地方，此时生成一个红色节点插入树中，如果节点颜色冲突，此时可以通过旋转和改变节点颜色让整个树保持基本平衡。
以下插入3,21,32,15为例，红黑树的插入过程。
1、创建一个红色节点3，因为根节点为空，需要设置颜色为黑色并设置为根节点。
2、插入节点21，因为节点21大于3，此时在节点21为节点3的右孩子。
3、插入节点32，因为32大于21，节点32为21的右孩子，此时节点32为红色，他的父节点21也是红色节点，违背了红色节点的孩子只能是黑色节点的特征，此时需要左旋转，转换后把节点21设置为黑色根节点，节点3设置为红色。
4、插入节点15，此时为节点3的右子红色节点，节点3和节点15都是红色节点违背红黑树的特征，需要转换节点15的父节点3和叔节点32为红色，此时祖父节点21应该设为红色，因为节点21为根节点，此时需要设为黑色。
总结插入的情况
1、如果插入的节点X，父节点P为红色，叔叔节点U为红色，那么就要把父节点和叔叔节换成黑色，祖父节点G换成红色（但如果是根节点换成黑色）。此时还需要往上检查节点的情况。
2、LL型：如果插入的节点X，父节点P为红色，叔叔节点U为黑色，节点X为父节点的左孩子，那么就要把父节点换成黑色，祖父节点G换成红色，并且按照节点G右旋转。
3、LR型：如果插入的节点X，父节点P为红色，叔叔节点U为黑色，节点X为父节点的右孩子，先按照节点P左旋转，再把节点G换成红色，节点X换成黑色，并且按照节点G右旋转。
4、RR型：如果插入的节点X，父节点P为红色，叔叔节点U为黑色，节点X为父节点的右孩子，那么就要把父节点换成黑成，祖父节点G换成红色，并且按照节点G左旋转。
5、RL型：LL型：如果插入的节点X，父节点P为红色，叔叔节点U为黑色，节点X为父节点的左孩子，先按照P右旋，再把父节点G换成红色，节点X换成黑色，并且按照节点G左旋转。
历史文章：
理解数据结构之红黑树简介
理解数据结构之平衡二叉树的删除操作
理解数据结构之二叉平衡树（AVL）
理解数据结构之二叉搜索树的插入和删除
理解数据结构之树（一）