二叉排序树查找 ：什么是红黑树？(3)

下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色：

????????????????????????????????????????????????

但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色：

????????????????????????????????????????????????

此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色：

????????????????????????????????????????????????

左旋转：

逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。说起来很怪异，大家看下图：

????????????????????????????????????????????????

图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。

右旋转：

顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。大家看下图：

??????????????????????????????????????????????????

图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。二叉排序树查找此为右旋转。

????????????????????????????????????????????????

????????????????????????????????????????????????

我们以刚才插入节点21的情况为例：

????????????????????????????????????????????????

首先，我们需要做的是变色，把节点25及其下方的节点变色：

????????????????????????????????????????????????

此时节点17和节点25是连续的两个红色节点，那么把节点17变成黑色节点？恐怕不合适。这样一来不但打破了规则4，而且根据规则2（根节点是黑色），也不可能把节点13变成红色节点。

变色已无法解决问题，我们把节点13看做X，把节点17看做Y，像刚才的那样进行左旋转：

????????????????????????????????????????????????

????????????????????????????????????????????????????????

????????????????????????????????????????????????

由于根节点必须是黑色节点，所以需要变色，变色结果如下：

????????????????????????????????????????????????

这样就结束了吗？并没有。因为其中两条路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4，其他路径的黑色节点个数是3，不符合规则5。

这时候我们需要把节点13看做X，节点8看做Y，像刚才的那样进行右旋转：

????????????????????????????????????????????????

????????????????????????????????????????????????

????????????????????????????????????????????????

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-87093-3.html