C++红黑树实现与STL map底层原理

1. 红黑树的概念

红黑树是一棵二叉搜索树，它的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

1.1 红黑树的规则

1. 每个结点不是红色就是黑色。
2. 根结点是黑色的。
3. 如果一个结点是红色的，则它的两个孩子结点必须是黑色的（即任意一条路径不会有连续的红色结点）。
4. 对于任意一个结点，从该结点到其所有 NULL 结点的简单路径上，均包含相同数量的黑色结点。

说明：《算法导论》等书籍中补充了'每个叶子结点（NIL）都是黑色的'规则。这里所指的叶子结点不是传统意义上的叶子结点，而是我们说的空结点（NIL），也叫外部结点。引入 NIL 是为了准确标识所有路径，但在实现细节中通常忽略 NIL 结点，了解概念即可。

1.2 红黑树如何确保最长路径不超过最短路径的2倍？

• 由规则4可知，从根到 NULL 结点的每条路径都有相同数量的黑色结点。极端场景下，最短路径一定是全为黑色结点的路径，假设最短路径长度为 bh（black height）。
• 由规则2和规则3可知，任意一条路径不会有连续的红色结点。极端场景下，最长路径就是一黑一红间隔组成，那么最长路径的长度为 2 * bh。
• 综合红黑树的4点规则，理论上的全黑最短路径和一黑一红的最长路径并不一定在每棵红黑树中都存在。假设任意一条从根到 NULL 结点的路径长度为 h，那么 bh <= h <= 2 * bh。

1.3 红黑树的效率

假设 N 是红黑树中结点数量，h 是最短路径的长度，那么：

2^h - 1 <= N <= 2^(2*h) - 1

由此推出 h ≈ logN，即红黑树增删查改的最坏情况是走最长路径 2*logN，时间复杂度仍为 O(logN)。

红黑树的表达相对 AVL 树要抽象一些。AVL 树通过高度差直观地控制平衡，而红黑树通过4条规则的颜色约束间接实现了近似平衡。两者效率属于同一档次，但红黑树在插入相同数量的结点时旋转次数更少，因为它对平衡的控制没那么严格。

2. 红黑树的实现

2.1 红黑树的结构

// 枚举值表示颜色
enum Colour { RED, BLACK };

// 这里默认按 key/value 结构实现
template<class K, class V>
struct RBTreeNode {
    // 更新控制平衡需要加入 parent 指针
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Colour _col;

    RBTreeNode(const pair<K, V>& kv)
        :_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr) {}
};

< ,  >
  {
     RBTreeNode<K, V> Node;
:
    
:
    Node* _root = ;
};