红黑树是一种半平衡的二叉搜索树，它放弃了二叉搜索树的绝对平衡，换来了较为简单的可维护性，使得二叉搜索树插入新数据，以及搜索数据时，都具有不错的搜索性能。

之所以说红黑树是一种半平衡的二叉搜索树，是因为红黑树中所有叶子节点的深度相差不会超过一倍。为什么呢？在解答这个问题之前，先来看看红黑树的几条特性：

1. 所有节点要么是红色，要么是黑色
2. 根节点必须是黑色
3. 所有叶子（NULL，or NIL）节点都是黑色的
4. 红色节点的两个子节点必须是黑色（不能有连续的红色节点）
5. 从根节点到任意叶子节点，黑色节点的数目是相等的

只要二叉搜索树符合以上 5 条性质，它就是红黑树。事实上，提出这 5 条性质的目的就是为了获得红黑树的“所有叶子节点的深度相差不会超过一倍”这个特性。请看下图：

叶子节点最浅的路径必定出现在全是黑色节点的路径，最深的路径必定既有黑色节点，又有红色节点。性质5要求所有路径的黑色节点数目相等，所以对比叶子节点的最深路径和最浅路径时，只需考虑最深路径中的红色节点。性质4要求路径中不能出现连续的红色节点，所以最深的路径必定是红黑节点相间的，这就解释了为什么叶子节点最深的路径最多是最浅的路径的 2 倍。

如果插入和删除操作都遵循红黑树的 5 条规则，那么这个树就会始终保持是一个红黑树，即一个半平衡树，也就能维持树的插入和查询时的优异性能。之所以这么费尽心思的维护一个红黑树，是因为实践证明红黑树的这些规则遵循起来是相对简单的。

虽然红黑树的几条规则看来比较容易遵循，但是在使用C语言编程实现时，还是有些繁琐的。向红黑树插入数据时，一般分为两个步骤，首先把红黑树当作一棵普通的二叉搜索树插入数据，然后再进行旋转变换以及重新着色的操作，调整二叉树仍然是一个红黑树。

应该明白，红黑树也是一棵二叉搜索树，所以二叉搜索树的性质红黑树也应遵循。在向红黑树插入数据后的变换和重新着色操作中，着色显然不会影响二叉搜索树的性质，“红黑色”只是节点的一个标记而已，它不影响节点记录的数据，也不影响节点间的相对关系。真正改变树结构的是“旋转”操作，应该尽力避免会破坏二叉搜索树性质的操作，所以人们定义了“树节点的左旋和右旋”，如下图：

树节点的左旋和右旋均不改变二叉搜索树的性质，β始终介于 A、B之间。@Sun_TTTT 的动图更清晰一点，清楚的反应了左旋和右旋的特点：

右旋：