红黑树依然是二分搜索树，学习红黑树首先要理解2-3树
《算法导论》 中红黑树的定义：
- 每个节点或者是红色的，或者是黑色的
- 根节点是黑色的
- 每一个叶子节点（最后的空节点）是黑色的
- 如果一个节点是红色的，那么他的孩子节点都是黑色的
- 从任意一个节点到叶子节点，经过的黑色节点是一样的
2-3树是满足二分搜索树的绝对平衡树（任意左右子树的高度相同）。但2-3树不是二叉树，它的节点可以存放一个元素或者两个元素。
2-3树中添加节点，新的节点永远不会到一个空的位置，只会和最后找到的叶子节点做融合。如果形成4节点，4节点直接分裂成2节点。
思考：一个空的2-3树依次加入节点 37，18，42，12，6，11，5 是如何形成以下树结构的
tip:通过将新的节点融合进叶子节点，以此保护绝对平衡，如果融合成4节点，再通过分离保持平衡。
12
6 37
5 11 18 42
红黑树处理2-3树3节点的情况，将3节点分离为2节点后），分离下去的叶子节点标记为红色，表示它跟父亲节点之前的3节点关系。例如：6和12的三节点，将6作为12的左孩子节点，并将6标记为红色。
注意：所有红色的节点都是向左倾斜的，这是因为我们选择了3节点向左下拆分的方式。
红黑树是保持黑平衡的二叉树，算法导论的第五条定义到叶子节点经过的黑色节点一致，是因为红色节点回归到3节点状态，就是一个绝对平衡树。
对于查询较多的使用情况，AVL 树很好用。红黑树四牺牲了平衡性（2logn的高度），统计性能更优（综合增删查改所有操作）。