本文共 248 字，大约阅读时间需要 1 分钟。

以插入为例描述红黑树旋转：

1.因为红黑树到任意一个叶子节点经过的黑节点数一样，因此新增节点只能是红色。

2.如果插入节点的父节点是黑节点，符合要求。如果是红，需要调整。

下面分类讨论：

3.如果伯父节点也是红，则将祖先节点变红，父节点与伯父节点变黑。

4否则如果伯父节点是黑，如果插入节点是右儿子，进行一次左旋成为情况5

5.这种情况下，左儿子和父节点都是红，祖先节点是黑，那么我们将父节点提为祖先节点，原来的祖先节点从右边下去，然后将新祖先节点改为黑，原来的

祖先节点改为红。

OK，调整结束

转载地址：http://togsi.baihongyu.com/