关于红黑树的插入

满足下面几个条件的二叉搜索树，称为红黑树：

1.       任何一个节点都被着色――红色或是黑色。

2.       根节点是黑色的。

3.       所有的NIL 节点都看成黑色（NIL 节点是就是一个假想的或是无实在意义的节点，所有应该指向NULL 的 指针，都看成指向了NIL 节点。包括叶节点的子节点指针或是根节点的父指针）。

4.       如果一个节点是红色的，那么它的子节点一定是黑色的。

5.       对于任何一个节点而言，从该节点到它的子孙节点中的NIL 节 点路径中，所包含的黑节点个数相同。

 

黑高度的定义：

从任何一个节点，向下到底部的路径中，包含的黑节点的个数，称为这个节点的黑高度。从红黑树的第５条性质可以看出，黑高度是唯一的、确定 的。

 

只要同时满足红黑树的这些条件，就一定会有“红黑树可以保证任何两条从根部到树叶的路径节点个数相差不超过２倍”这个平衡的性质。

我们可以假设，如果存在两条路径L 和S ，L 比S 长两倍以上（S 路径上有n 个节点，L 上有大于2n 个节点）。可知，S 的黑高度最大只可能是n ，那么根据第５条性质，L 的黑高度也大也只可能是n ，也就是，L 路径上一定有超过n 个红色节点（因为节点不是黑的就必 定是红的）。所以，肯定会有两个以上的红色节点是相邻的。这就与第４个条件矛盾了。所以，红黑树可以保证任何两条从根部到树叶的路径节点个数相差不超过２ 倍。

 

红黑树的高度h<2lg(n+1) （这个在《算法导论》13.1 节中有证明）。也就是说，红黑树的操作的时间复杂度是O(lgn) 的。  

 

二叉搜索树的操作时间复杂度，取决于树高h ，因此，我们当然就希望h 尽量地小以提高操作的效率。 从直观上就可以发现，二叉搜索树各子树的规模越平均，它的高度就会越小。所以在应用中，一般都会将二叉搜索树实现成一种平衡树，以保证最差时间复杂度为O(lgn) 。红黑树就是其中的一种，应用得很广泛（SGI STL 的 set 和 map 就是基于红黑树来实现， Linux 内核中也用到这个数据结构 ）

红黑树是二叉搜索树的一种。它与普通二叉搜索树不同的是，红 黑树的每个节点都附加了另一个属性――颜色，可以是红色，也可以是黑色。通过对于每条路径上节点颜色的规则进行限定，红黑树可以保证任何两条从根部到树叶 的路径节点个数相差不超过２倍。所以，红黑树是一种近似平衡的二叉搜索树。

 

红黑树 的查找、最大值、最小值、前趋、后继等操作，与普通的二叉搜索树没有什么区别。插入和删除操作需要重新实现。仅仅用普通的二叉搜索树的插入和删除动作，可 能会破坏红黑树本身的一些性质，因此，需要进行额外的处理。这些额外的处理主要是改变树节点的颜色，或是改变树的结构。

 

 

 

 

 

 

 

树的旋转

改变树的结构，主要是用旋转。旋转有两种，左旋和右旋，下面 是这两种旋转的：  

这种旋转的操作，是在二叉搜索树的局部对树的结构进行调整的 一种方式，经过旋转之后，二叉搜索树的性质是不会发生改变的。如下图：

 

向红黑树插入节点，先将需要插入的节点着成红色，用普通二叉 搜索树的方法将这个节点插入到树中，然后再想办法把被破坏的红黑性质恢复。（将新插入的节点颜色着成红色，呆以尽量减少对红黑性质的破坏，恢复起来也容 易。因为插入红色节点的话，那么被破坏的部分会在局部，考虑的问题也就比较少，恢复过程也容易形成递归，详细见下文说明）

我们考虑下，如果一个红色节点（下文称用 Z 指向它）被插入到树中，那么有哪些红黑性质可能被破坏呢？只有第 2 条（根节点是黑色的）以及第 4 条（红色节点的子节点一定是黑色节点），其它都不会被破坏。

如果插入的节点的父节点是黑色的，那么不需要做任何调整，这 红黑树是正常的。如果父节点是红色，或没有父节点（也就是插在了树根的位置），那么就要进行调整以保证红黑树是正确的。

首先对第 4 条进行分析，我们知道，插入一个新的节点，这个节点肯定会被放到树的底部成为一个叶节点（参考普通二叉树的插入过程），那么这个红色节点就没有 可能和自己的子节点同色（因为叶节点的子节点是 NIL 节点，都是黑色的），如果第 4 条被破坏的话，肯定是 Z 指向的节点的父节点是红色的。因此，为了使分析和解决更加容易和清晰，我们在对树进行调整以恢复红黑 特性时，始终使得 Z 总是指向相邻红色的节点中的子节点（指针 Z 可能会向上升到树的中部或根部）。基于这个做法，我们可以知道，如果是第 2 条被破坏了的话，也就是 Z 指向根节点了，那么第 4 条肯定就符合了（因为 Z 的父节点是 NIL ，黑色的），因此对第 2 条性质的恢复变得很简单，只需要被根从红色变为黑色即可。这时，所有性质都会被满足了（因为是根节 点，所以根节点被着为黑色时，所有路径都黑高会统一加 1 ，也就是第 5 条不会被破坏，操作之后的红黑树仍然是正确的）。好了，现在只留下第 4 条性质的恢复的问题了。

如果第 4 条被破坏了，也就是说， Z 的父节点是红色的，那么，说明， Z 一定有祖父节点，而且是黑色的（否则插入前原树就有问题，又 或是调整时的方法不正确）。因此可以把问题放到以 Z 的祖父节点为根节点的子树内进行解决，这样可以把调整的范围最 小化，而且这也是有可能的：只要不改变这子树的黑高度，那么就不会对树的其它部分产生影响。我们要做的就是在这个子树范围内把红黑性质调整回来。再看子树 的根是否与其父节点同为红色，是的话，就再次用前面所说的去解决它，一直向上递归到红黑性质被恢复为止。

 

红黑树的节点插入  

 

　　对第 4 条性质的恢复，根据 Z 的父节点是 Z 的祖节点的左子节点还是右子节点，分为两组对称的情况，每组有 3 种情况。下面我们只对其中一组进行说明，以 Z 的父节点是 Z 祖节点的左子节点为例：    

第一种： Z 的“叔父”节点是红色。

 

              

 

如上图所示，在这种情况下，将父、叔节点都着为黑色，再将子树根节点着为红色，那么子树的黑高度没有发生改变，而且 红黑性质得得到了调整。此时，再将 Z 指向子树的根节点，向上递归恢复红黑特性。

 

第二种： Z 的“叔父”节点是黑色的， Z 的父节点的左子节点。

如上图，将 Z 的父节点与祖节点进行一次右旋，并把父节点着黑色，原来的祖节 点着红色。这些子树的红黑特性得到了恢复，而且子树的黑高度没有变化。另外，由于子树根节点已经是黑色了（这个节点不会出现父子同为红色的问题了），所以 不必再向上递归了，此时整个树的红黑特性都已经是正确的了。

 

第三种： Z 的“叔父”节点是黑色的， Z 的父节点的右子节点。

 

 

 

 

 

如上图，将 Z 本身与其父节点进行一次左旋，让 Z 指向原来的父节点，就可以调整为情况二，而情况二已经得到解决。

这样，红黑树的节点插入问题就得到了解决。

 

以上引自：http://liyiwen.iteye.com/blog/345800

注 摘图中第三种情况图可能不对，右边到了左边

另附维基：http://en.wikipedia.org/wiki/Red-black_tree

 

/** From CLR */
    private void fixAfterInsertion(Entry<K,V> x) {
        x.color = RED;

        while (x != null && x != root && x.parent.color == RED) {
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x); //此处虽然提升x为x的父节点，但是左旋后，x又成为字节点
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK); // 因此这里是将x父节点设黑
                    setColor(parentOf(parentOf(x)), RED); // 子树根节点设红
                    rotateRight(parentOf(parentOf(x))); // 按子树根节点右旋
                }
            } else {
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    // 这里是因为新插入节点在右边，与上其实是对称的
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x))); // 这里的左旋是基于根节点的左大旋转，与维基中的case5一致，不过只是镜面对称而已
                }
            }
        }
        root.color = BLACK;
    }

 

以上程序理解的话真的很经典，关键是两个小else，还有对基于节点的左旋和右旋也要理解