红黑树的底层原理及 C++ 实现

前言

在之前的讨论中，当二叉搜索树退化成单支时会导致性能降低。AVL 树虽然能保证高度平衡，但每次修改结构时都要保证左右子树高度差不超过 1。对于结构动态变化的场景，红黑树是更优的选择。

一、红黑树的概念

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

二、红黑树的规则

每一棵红黑树都需要满足以下规则：

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

通过上述规则，最长路径不超过最短路径的两倍。假设最短路径长度为 bh（全黑），则最长路径长度约为 2 * bh（一黑一红间隔）。

三、红黑树的效率

1. 红黑树在插入、查找和删除操作上的时间复杂度都为 O(logN)。
2. 与 AVL 树相比，其插入和删除操作上的平衡代价较低，整体性能略优于 AVL 树，且旋转情况少于 AVL 树，这使得红黑树在实际应用中更加高效和稳定。

四、红黑树的实现

1. 基本框架

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

// 默认按 KV 结构进行实现
template<class K, class V>
struct RBTreeNode {
    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) {}
};

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