红黑树操作及实现

        红黑树是广泛应用的平衡二叉搜索树之一（另外一种常见的平衡二叉搜索树是AVL树）。它是SGI STL唯一实现的一种搜索树；是关联容器的底部机制。

       和AVL树所实现的平衡机制不同，但是同样适用了单旋转和双旋转操作修正树以保证平衡。

       红黑树的性质：

              1. 每个节点都被着上黑色或者红色。

              2. 根节点是黑色。

              3. 如果一个节点为红色，那么其子节点必须都为黑色。

              4. 任一节点到NULL指针的每条路径上必须包含相同数目的黑节点（将NULL视为黑色）。

        根据性质4，新插入的节点必须为红色，否则若新插入节点为黑色，则会使得该节点所在的路径上的黑节点个数增加。

        根据性质3，新插入节点的父节点必须为黑色（因为上面已经证明新插入节点必须为红色）。如果新节点插入后其父节点不为黑色则就要通过改变节点颜色和旋转树来保证红黑树性质。这就是下边插入操作比较麻烦所在。

约定： X为新节点，P为父节点，G为祖父节点，S为叔节点，GG为曾祖父节点。

分以下两种情况（父节点为黑或红）讨论插入操作：

一、 父节点为黑色

         直接插入X，插入操作完成。

二、父节点为红色

在第一部分已经讨论了，当父节点为红色，就会违背红黑树的性质，要调整树、改变节点颜色；此时，根据X插做左孩子还是右孩子和外围节点（S和GG）的颜色，再分以下几种情况讨论：

情况1： S为黑且X为左孩子

         在P和G之间做一次右旋转并改变G和P的颜色，即可。

        注意，旋转后可能会使树的高度相差大于1，例如当图中A、B为空但D或E不为空时。但这没关系，因为红黑树的平衡性本来就比AVL树弱，然而红黑树通常能导致良好的平衡状态。红黑树与AVL树平均效率相当，最坏情况下花费O(logN)。

情况2：S为黑且X为右孩子

        将P和X经过一次左旋转便可以变回情况1的情形；改变G和X的颜色，然后再对G做一次右旋转，即可。从这里的操作可以看出，所谓的双旋转其实就是两次单旋转。

情况3：S为红

       分析此时所存在的问题：当S为红色的时候，如图5-15c所示，此时对P和G做一次旋转并改变X的颜色。此时，如果GG为黑色，那么该操作完成。但是，如果GG为红色，那么，旋转后的G和GG均为红色，不符合红黑树性质。

        解决方法：当遇到这种情况的时候，我们可以采取的方式有两种：上滤和自顶向下。以下分别介绍这两种方法。

上滤法：

自顶向下法：

         该方法是自上而下来保证S不会为红色的过程。在向下的过程中，当遇到一个节点X的两个儿子都是红色，就将X改为红色，而将两个儿子改为黑色。这种翻转只在X的父节点也为红色时才会破坏红黑树的性质，但是可以使用情况1或情况2中的方法做调整。这个过程能够保证不会遇到S节点为红色的情况；因为我们是自上而下调整的，在调整到G节点时，已经将可能存在的、P和S同时为红的情况破坏了。

        例如5-15e中，在寻找35插入的位置的过程中，我们从根节点开始寻找35应该插入的位置，其寻找的路径为图中虚箭头所示的方向，在该向下找过程中，当X为50的时候，X的两个孩子都是红色，此时将X改为红色，而将它的两个孩子改为黑色；然后继续找35应该插入的位置，这样就确保了不会存在S为红色的情况。

的