以前一直想好好看看红黑树，但看着看着认为这种实现的东西直接调别人的包就可以了，我只要知道大概的时间空间复杂度就ok了。好吧，我承认我理解肤浅了，今天没啥事就把红黑树好好复习了一下。
  红黑树(RB-Tree)用途真是太广了，Linux内核，STL中的关联容器，nginx的实现……太多地方用到了。目前的AVL树已经快走入博物馆了，红黑树开始在历史舞台上发挥光和热了。好吧，废话扯多了。move on!

二叉搜索树

  首先回顾一下平衡二叉搜索树的祖先：二叉搜索树。它具有以下性质：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉搜索树。

  它的优点我就不说了，缺点就是可能导致不平衡：某一边的子树高度远远大于另外一边的子树。这样在插入，删除，查找时最坏情况的复杂度达到了O(n)。
  由于它存在的缺点，诞生了平衡二叉搜索树，其实所谓的树形平衡与否，并没有一个绝对的测量标准。“平衡“的大概意义就是：没有任何一个节点过深。目前平衡二叉树有很多版本，比较有名的就是AVL书和红黑树，另外还有一些性能较好的树，但是代码实现复杂度比较高，所以没有流行开来。

AVL树

  来讲讲AVL树：它是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
  节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来.

插入操作

  插入分为以下四种：

• 插入点位于X的左子节点的左子树--左左
• 插入点位于X的左子节点的右子树--左右
• 插入点位于X的右子节点的左子树--右左
• 插入点位于X的右子节点的右子树--右右

  情况1，4彼此对称，称为外侧插入，可以采用单旋转操作调整解决：比如左左采用右旋。情况2，3彼此对称，称为内测插入，可以采用两次旋转操作调整解决：比如左右可以采用先左旋再右旋。

删除操作

  删除分为以下三种：

• 叶子节点删除。如果删除该叶子节点影响高度，进行左右旋转调整，否则直接删除。
• 只有一个儿子节点。直接删除，并将父节点的儿子指针指向该删除节点的儿子。并进行旋转调整。
• 具有两个儿子节点。这种情况稍微复杂一点，寻找当前节点的中序遍历后继节点：即右子树中最小的节点。将该节点替换当前节点，并进行调整。

红黑树

  红黑树的性质如下：

• 每个节点或是红的，或是黑的。
• 根节点为黑的
• 每个叶节点是黑的。
• 如果一个节点是红的，则它的两个儿子都是黑的
• 对每个节点，从该节点到其子孙节点的所有路径包含相同书目的黑节点
  

  红黑树的旋转操作与普通平衡二叉搜索树一致。由于前面5条条件限制，插入，删除节点时都得遵循这些条件。具体算法我就不分析了，大家可以参考《算法导论》或维基百科 。

插入操作

  插入之后，新节点颜色为红，如果违背以上条件则进行调整，调整过程为迭代。

删除操作

  同样删除操作也是，删除之后进行调整，使最后满足以上条件。

算法比较

• 总体上来说，两者在删除和插入的复杂度一致，都为O(log n)。
• AVL树的高度在~1.44log(n)级别，而红黑树的高度在~2log(n)级别。但是在插入之后旋转调整，AVL的复杂度在O(log n),即多次旋转。而红黑树调整的级别在O(1)，因为其能保证在三次旋转之内达到稳定。
• 相比较而言，因为树的高度的关系，红黑树适用于插入删除频繁，AVL树适用于查找频繁。但其实红黑树应用比AVL广很多。