在二叉树的学习中，我们会接触到很多不同的树。其中，用得最为普遍的，是二叉搜索树。而为提升二叉树搜索的效率，又引入自平衡二叉树的概念。自平衡二叉搜索树是指通过处理可以实现子树相对平衡，即不极端地偏向一边的二叉搜索树。由于相对平衡的特性，树可以实现查询、插入、删除操作在时间上的优化。

本文处于草稿中。。。

1. 定义：红黑树利用特征标记决定高度的自平衡二叉搜索树，具有额外的数据决定其节点为黑或红节点。每一条从单一节点到叶子结点的路径都有相同数目的黑色节点。利用此特性，保持树高为$O(lg\ n)$。

   pre：平衡树：空树或其左右两个子树高度差相对小的二叉搜索树。

   正确性特性：

   1. 节点是红色或黑色。
   2. 根是黑色。
   3. 所有叶子都是黑色（叶子是NIL节点）。
   4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
   5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。