数据结构：红黑树

一、红黑树的概念

红黑树是一棵自平衡二叉搜索树，它的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。

与 AVL 树追求'严格平衡'不同，红黑树 允许一定程度的不平衡。AVL 树通过'平衡因子'维持平衡，而红黑树通过给节点 着色（红色或黑色）来确保高效性。在保证增删改查效率没有太大影响的前提下，显著减少了平衡调整（旋转）的次数，从而提升总体效率。红黑树的性质如下：

节点颜色：每个节点要么是红色，要么是黑色。根节点：根节点必须是黑色。叶子节点：所有叶子节点（即 NULL 节点/空指针）均为黑色。红色约束：如果一个节点是红色，则其子节点必须是黑色。**路径上不能有连续的红色节点。**黑色高度：从根节点到任意 NULL 节点的所有路径上，黑色节点的数量都相同。

红黑树最长路径不超过最短路径的两倍

二、红黑树节点的定义

红黑树节点定义如下，采用三叉链结构，并添加一个变量表示节点颜色。

enum Colour { RED, BLACK };
template<class K, class V>
struct RBTreeNode {
    // 三叉链
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    // 存储的键值对
    pair<K, V> _kv;
    // 结点的颜色
    int _col; // 红/黑

    // 构造函数
    RBTreeNode(const pair<K, V>& kv) :_left(nullptr), _right(nullptr), _parent(), _kv(kv), _col(RED) {}
};