前言
前面我们已理解并实现了 AVL 树，不难发现：AVL 树对其自身结构有非常严格的要求，即任意节点的左右子树高度差不能超过 1，所以，又有人提出了红黑树这样的数据结构，但 AVL 树与红黑树都遵循二叉搜索树的规则。
一、什么是红黑树？
1.1、红黑树概念
红黑树是一棵二叉搜索树，它的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出 2 倍，因而是接近平衡的。
1.2、红黑树规则
• 根结点为黑色； • 每个结点不是黑色就是红色； • 如果结点为红色，那么该节点的两个孩子节点为黑色，即任意一条路径上没有连续的红色节点； • 对于任意一个结点，从该结点到其所有 NULL 结点的简单路径上，均包含相同数量的黑色结点。
思考：红黑树如何确保最长路径不超过最短路径的 2 倍的？
答：从根结点开始的一条路径上只有 n 个黑色结点，由红黑树规则，两条路径上黑色结点数相同，且红色结点不连续，则当另一条路径上黑色结点与红色结点相间分布时，有最长长度为 2n，这就保证了最长路径始终不超过最短路径的两倍。
1.3、红黑树的效率
假设 N 是红黑树树中结点数量，h 最短路径的长度，那么 2^h − 1 <= N < 2^(2∗h) − 1 , 由此推出
h ≈ logN ，也就是意味着红黑树增删查改最坏也就是走最长路径 2 ∗ logN，那么时间复杂度还是 O(logN)
二、红黑树的实现
说明：我们以实现一个键值对（key_value）类型的红黑树，且数据不支持冗余。
2.1 红黑树节点结构定义
对于结点，我们需要一个 pair 来存储键值对；left 指针指向左孩子结点；right 指针指向右孩子结点；color 变量存储结点颜色；后面插入结点时，如果需要调整平衡，则要频繁地访问父亲结点，所以还需要一个 parent 指针指向父亲结点（与 AVL 树相同）。
由于结点颜色只有黑或者红，而 enum（枚举类型）可以用于定义固定集合常量，所以可以将结点颜色存储在一个枚举类型中。
节点结构：
2.2、红黑树的结构
template<class K,class V> class RBTree { typedef RBTreeNode<K, V> Node; public: // ... private: Node* _root = nullptr; // 根结点 };
