红黑树的定义
红黑树是一种自平衡二叉查找树。它的统计性能要好于平衡二叉树（AVL树），因此红黑树在很多地方都有应用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。红黑树是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(logn)时间内做查找、插入和删除等操作。
黑树，顾名思义，通过红黑两种颜色域保证树的高度近似平衡。它的每个节点是一个五元组：color（颜色），key（数据），left（左孩子），right（右孩子）和p（父节点）。
红黑树的定义也是它的性质，有以下五条：
性质1. 节点是红色或黑色
性质2. 根是黑色
性质3. 所有叶子都是黑色（叶子是NIL节点）
性质4. 如果一个节点是红的，则它的两个儿子都是黑的
性质5. 从任一节点到其叶子的所有简单路径都包含相同数目的黑色节点。
这五个性质强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。性质4暗示着任何一个简单路径上不能有两个毗连的红色节点，这样，最短的可能路径全是黑色节点，最长的可能路径有交替的红色和黑色节点。同时根据性质5知道：所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。
红黑树的插入操作
因为红黑树也是二叉查找树，因此红黑树上的查找操作与普通二叉查找树上的查找操作相同。然而，红黑树上的插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(logn))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为 O(logn) 次。
在讨论红黑树的插入操作之前必须要明白，任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解，因为插入黑点会增加某条路径上黑结点的数目，从而导致整棵树黑高度的不平衡。但如果新结点父结点为红色时（如图），将会违返红黑树性质：一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。
为了清楚地表示插入操作，以下在结点中：
使用“新”字表示一个新插入的结点；
使用“父”字表示新插入点的父结点；
使用“叔”字表示“父”结点的兄弟结点；
使用“祖”字表示“父”结点的父结点。
插入操作分为以下几种情况：
1、黑父
如图所示，如果新点的父结点为黑色结点，那么插入一个红点将不会影响红黑树的平衡，此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见，从而使红黑树需要旋转的几率相对AVL树来说会少一些。
2．红父
如果新点的父结点为红色，这时就需要进行一系列操作以保证整棵树红黑性质。如图3所示，由于父结点为红色，此时可以判定，祖父结点必定为黑色。这时需要根据叔父结点的颜色来决定做什么样的操作。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作，而每次进行不平衡判断的起始点（我们可将其视为新点）都不一样。所以我们在此使用一个蓝色箭头指向这个起始点，并称之为判定点。
2.1 红叔
当叔父结点为红色时，如图4所示，无需进行旋转操作，只要将父和叔结点变为黑色，将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色，从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上进行平衡操作。
需要注意，无论“父”在“叔”的左边还是右边，无论“新”是“父”的左孩子还是右孩子，它们的操作都完全一样。
2.2 黑叔
当叔父结点为黑色时，需要进行旋转，以下图示了所有的旋转可能
情形1：
情形2：
红黑树的删除操作
红黑树的另一个重要的操作是删除节点，它也可以分为两步：
1、找到要删除的节点，并删除它
2、对树进行调整使得树满足红黑树的要求
从排序树中删除节点的思路是一样的，首先找到要删除的节点，并做如下处理：
1、如果该节点不存在非空子节点，则直接删除它
2、如果该节点存在一个非空子节点，则用其非空子节点替换其位置即可
3、如果该节点有两个非空子节点，则可以找到该节点的前驱或者后继，然后更换两个节点的元素值，再将前驱或者后继当做被删除的节点（由于任意一个节点的前驱或者后继都必定至多只有一个非空子节点，因而删除这样的节点就可以按照前两种情形进行处理）
红黑树也采取了类似的思路，假设要删除的节点为A，则先找到节点A，然后：
1、如果节点A有两个非空子节点，则找到节点A的前驱（也可以是后继），然后记要删除的元素B=A的前驱，否则只要A有一个空子节点，就记要删除的元素B=A
2、记变量X为B的第一个非空子节点（先检查左孩子，后检查右孩子），如果B的两个孩子都为空，则记X为空
3、如果B和A不同，则将B的内容拷贝到A
4、删除节点B
6、如果被删除节点B的颜色为红色，则删除结束，否则从节点X处开始对删除节点后的红黑树进行调整
以下图为例：
如果要删除节点75，则A=75，B=85，X=NULL
如果要删除节点25，则A=25，B=19，X=NULL
如果要删除节点40，则A=B=40，X=NULL
显然，在这种处理方式下，如果B的颜色为红色，则删除它后删除操作即完成了，因为：
1、B是红色的，因而它不是根
2、B是红色的，它的父节点必然是黑色的，因而删除它不会引入两个红色的连续节点
3、B是红色的，而且它至多有一个非空子节点，因而删除它不会导致红黑树的任意路径上的黑节点数目变化
如果B的颜色为黑色，则需要从节点X处开始对删除节点后的红黑树进行调整。
红黑树和平衡二叉树的比较
红黑树和平衡二叉树区别如下：
1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。
2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。
红黑树和之前所讲的AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。自从红黑树出来后，AVL树就被放到了博物馆里，据说是红黑树有更好的效率，更高的统计性能。
红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。AVL树的复杂比起红黑树来说简直是小巫见大巫。红黑树是真正的变态级数据结构。