红黑树是一种自平衡二叉查找树。它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除等操作。
红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。在实际的系统中，例如，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。
红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高.
红黑树，顾名思义，通过红黑两种颜色域保证树的高度近似平衡。它的每个结点是一个五元组：color（颜色），key（数据），left（左孩子），right（右孩子）和p（父结点）。 红黑树的定义也是它的性质，有以下五条：
- 结点是红色或黑色
- 根是黑色
- 所有叶子都是黑色（叶子是NIL结点）
- 如果一个结点是红的，则它的两个儿子都是黑的
- 从任一结点到其叶子的所有简单路径都包含相同数目的黑色结点。
这五个性质强制了红黑树的关键性质: **从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。**性质4暗示着任何一个简单路径上不能有两个毗连的红色结点，这样，最短的可能路径全是黑色结点，最长的可能路径有交替的红色和黑色结点。同时根据性质5知道：所有最长的路径都有相同数目的黑色结点，这就表明了没有路径能多于任何其他路径的两倍长。
因为红黑树也是二叉查找树，因此红黑树上的查找操作与普通二叉查找树上的查找操作相同。
然而，红黑树上的插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次。
首先以二叉查找树的方法增加结点并标记它为红色。（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑结点，这个是很难调整的。但是设为红色结点后，可能会导致出现两个连续红色结点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。）下面要进行什么操作取决于其他临近结点的颜色。
设要插入的结点为N，N的父结点标为P，N的叔父结点标为U，N的祖父结点标为G。（即P和U是G的孩子结点）。图中展示的任何颜色要么是由它所处情形这些所作的假定，要么是假定所暗含（imply）的。
情形1. 新结点N位于树的根上，没有父结点。（插入树的第一个结点）
在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑结点数目增加一，性质5符合。
情形2. 父结点P是黑色，则整棵树不必调整便是红黑树。新结点是红色的，所以性质4没有失效。尽管新结点N有两个黑色叶子子结点；但由于新结点N是红色，通过它的每个子结点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色结点，性质5也未受到威胁。
情形3. 父结点P是红色（祖父结点G一定为黑色），叔父结点U也是红色。则我们可以将P，U重绘为黑色并重绘祖父结点G为红色（用来保持性质5）。但是，红色的祖父结点G可能是根结点，这就违反了性质2，也有可能祖父结点G的父结点是红色的，这就违反了性质4。为了解决这个问题，在祖父结点G上递归调整颜色。
（此时新插入结点N做为P的左子结点或右子结点都属于情形3，这里仅显示N做为P左子的情形）
情形4. 父结点P是红色（祖父结点G一定为黑色），叔父结点U是黑色或缺少，并且新结点N是左孩子。则针对祖父结点G进行一次右旋转；在旋转产生的树中，以前的父结点P现在是新结点N和以前的祖父结点G的父结点。以前的祖父结点G是黑色，切换以前的父结点P和祖父结点G的颜色，结果的树满足性质4，5。
（此时P为祖父结点G的左子结点或右子结点都属于情形4，这里仅显示P为G左子的情形）
情形5. 父结点P是红色（祖父结点G一定为黑色），叔父结点U是黑色或缺少，并且新结点N是右孩子。则针对父结点P进行一次左旋转调换新结点N和P的角色，接着按情形4进行处理。
首先以二叉查找树的方法找到要删除的结点，如果需要删除的结点有两个非叶子的孩子结点，那么问题可以转化成删除的结点最多有一个非叶子的孩子结点。（对于二叉查找树，在删除带有两个非叶子儿子的结点的时候，要么找到它的前驱（左子树中的最大元素）、要么找到后继（右子树中的最小元素），并把它的值拷贝到要删除的结点中。接着删除前驱（或后继），注意前驱（后继）的非叶子孩子结点数必定少于2。因为拷贝前驱（后继）值时不违反任何性质，所以上面的问题转化成立）。
如果被删除的结点没有非叶子的孩子，那么直接删除，然后用一个叶子结点代替它的位置，不用作其它树调整。
下面只讨论删除的结点只有一个非叶子结点孩子的情况。如果删除的是一个红色节点，它的父亲和孩子一定是黑色的，所以我们可以简单的用它的黑色儿子替换它，并不会破坏红黑树的性质。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持性质5。
需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候，这是一种复杂的情况。我们首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为N（在新的位置上），称呼它的兄弟（它父亲的另一个儿子）为S。在下面的示意图中，我们使用P称呼N的父亲，SL 称呼S的左儿子，SR 称呼S的右儿子。
情形1. N是新的根。在这种情形下，从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。
情形2. S是红色（N的父亲P是黑色）。在N的父亲P上做左旋转，把 S 转换成N的祖父，接着对调新的父亲P和新的祖父S的颜色。完成这两个操作后，N有了一个黑色的兄弟和一个红色的父亲（它的新兄弟是黑色因为它是红色S的一个儿子），接下去按情形4、情形5或情形6来处理。
情形3. S和S的儿子都是黑色，N的父亲P是黑色。简单的重绘S为红色。结果是通过S的所有路径，都少了一个黑色节点，因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点。但是，通过P的所有路径现在比不通过P的路径少了一个黑色节点，所以仍然违反性质5。要修正这个问题，我们要从情形1开始，在P上做重新平衡处理。
情形4. S和S的儿子都是黑色，N的父亲P是红色。简单的交换N的兄弟和父亲的颜色。这不影响不通过N的路径的黑色节点的数目，但是它在通过N的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点。
情形5. S是黑色，S的左儿子是红色，S的右儿子是黑色。在S上做右旋转，这样S的左儿子成为S的父亲和N的新兄弟。接着交换S和它的新父亲的颜色，所有路径仍有同样数目的黑色节点，但是现在N有了一个黑色兄弟，它的右儿子是红色的，所以我们进入了情形4。
情形6. S是黑色，S的右儿子是红色。在N的父亲上做左旋转，这样S成为N的父亲（P）和S的右儿子的父亲。我们接着交换N的父亲和S的颜色，并使S的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以性质3没有被违反。但是，N现在增加了一个黑色祖先：要么N的父亲变成黑色，要么它是黑色而S被增加为一个黑色祖父。
