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源码剖析--侯捷》