C++ 模拟实现红黑树 (RBTree)

一、红黑树的概念

红黑树是自平衡二叉搜索树，通过节点颜色（红 / 黑）和严格的规则约束，保证任意根到叶子的路径长度差不超过 2 倍，实现近似平衡，避免普通二叉搜索树退化为链表。

1.1 红黑树的规则（必须牢记）

• 每个节点非红即黑；
• 根节点必须是黑色；
• 红色节点的子节点必须全为黑色（禁止连续红节点）；
• 任意节点到其所有 NULL 叶子节点的路径，黑色节点数量相同（简称'黑高一致'）。

1.2 为什么最长路径不超过最短路径 2 倍？

• 最短路径：全黑节点路径，黑高为 bh；
• 最长路径：黑红交替路径，长度为 2*bh；
• 结论：任意路径长度 bh ≤ h ≤ 2*bh，保证了红黑树的近似平衡。

1.3 红黑树的效率优势

• 时间复杂度：增删查改均为 O(logN)（与 AVL 树同级）；
• 性能优势：插入 / 删除时旋转次数更少（AVL 树要求严格平衡，红黑树仅'近似平衡'），实际工程中（如 STL map/set）更常用。

二、红黑树的实现

2.1 红黑树的结构定义

#include <iostream>
#include <utility>
using namespace std;

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

// 红黑树节点结构
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), _col(RED) {
        
    }
};


< ,  >
  {
     Node = RBTreeNode<K, V>;
:
    
    ;
    
    { _InOrder(_root); cout << endl; }
    
    ;
    
    {  _Size(_root); }
    
    {  _Height(_root); }

:
    
     _InOrder(Node* root);
     _Size(Node* root);
     _Height(Node* root);
    
    ; 
    ; 
    
     _IsValidRBTree(Node* root,  blackCount, & refBlackCount);

:
    Node* _root = ;
};