AVL-tree之外，另一个颇具历史并被广泛运用的平衡二叉搜索树是RB-tree（红黑树）。所谓RB-tree，不仅是一颗二叉搜索树，而且必须满足一下规则：
1：每个节点不是红色就是黑色
2：根节点为黑色
3：若节点为红，其子节点必须为黑
4：任意节点至NULL的任何路径，所含黑节点数必须相同。
根据规则4，新增节点必须为红；根据规则3，新增节点之父节点必须为黑。当新节点根据二叉搜索树的规则到达其插入点，却未能符合上述条件时，就必须调整颜色并旋转树形。
插入节点
假设红黑树起始状态如下
在该树的情况下，如果此时加入节点为3,58,75,75则会出现在红色节点中新增新的红色节点的情况，如下图所示：
针对以上插入的四种情况都需要对红黑树进行调整；便于对不通情况进行区分，以及后续讨论方便，我们给一些特定的节点定义一些代名。后续讨论会沿用这些代名。假设新加入节点为X，其父节点为P，祖父节点为G，伯父节点为S，曾祖父节点为GG。现在根据二叉搜索树的规则，新节点X必为叶子结点。根据红黑树规则4，X必为红。若P为红（这就违反了规则3，必须调整树形）则G必为黑（因为原RB-tree，必须遵循规则3）。于是根据X插入位置，及外围节点S和GG的颜色，分为一下四种情况。
情况1：S为黑且X为外侧插入
。如下图所示
此时针对PG进行一次单旋，并修改P和G的颜色，变成如下所示：
注意此时，如果S不为null，则会出现X及G子树高度相差为2的情况，所以RB-tree不足以满足AVL-tree的特性。
情况2：S为黑且X为内侧插入
。如下图所示：
先针对XP做一次单旋，并修改X及G的颜色：得到如下图所示的图形：
再针对该树形的XG做一次单旋如下图所示：
情况3：S为红，且X为外侧插入
如下图所示情况：
对此情况，先对PG做一次单旋，并改变X的颜色。如下图所示
此时如果GG为黑，则搞定了，如果GG为红，则见状况4。
状况4：S为红且X为外侧插入
此时将PG进行单旋，并将X节点被为黑色，转换为下图：
根据前文描述的红黑树树形，
此时将40为根节点的子树，当做新插入的节点X，60当做P，70为G，此时有变回了状态3；针对PG进行单旋，并修改X节点40的颜色为黑色，转换后，图形如下：
至此将红黑树四种旋转的情况都描述完了；
参考文档《STL源码剖析--侯捷》
