C++模板实现红黑树：核心原理与完整代码解析

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

// 红黑树节点结构
template
struct RBTreeNode {
	RBTreeNode(const pair& kv = pair(), Colour col = RED)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(col) {}

	RBTreeNode* _left;     // 左孩子
	RBTreeNode* _right;    // 右孩子
	RBTreeNode* _parent;   // 父亲
	pair _kv;        // 键值对
	Colour _col;           // 节点颜色
};

// 红黑树类封装
template
class RBTree {
	typedef RBTreeNode Node;
public:
	RBTree() : _root(nullptr) {}
private:
	Node* _root; // 根节点指针
};

pair Insert(const pair& kv) {
	if (_root == nullptr) {
		_root = new Node(kv, BLACK); // 根节点强制黑色
		return { _root, true };
	}

	// 1. 普通BST查找插入位置
	Node* cur = _root, * parent = nullptr;
	while (cur) {
		parent = cur;
		if (cur->_kv.first < kv.first)
			cur = cur->_right;
		else if (cur->_kv.first > kv.first)
			cur = cur->_left;
		else
			return { cur, false }; // 已存在
	}

	cur = new Node(kv, RED);
	if (parent->_kv.first < kv.first)
		parent->_right = cur;
	else
		parent->_left = cur;
	cur->_parent = parent;

	// 2. 红黑树性质维护循环
	while (parent && parent->_col == RED) {
		Node* grandfather = parent->_parent;
		
		// 情况一：P在G的左边
		if (parent == grandfather->_left) {
			Node* uncle = grandfather->_right;
			
			// 1.1 叔叔存在且为红色：变色处理
			if (uncle && uncle->_col == RED) {
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				// 继续向上检查
				cur = grandfather;
				parent = cur->_parent;
			}
			// 1.2 叔叔不存在或为黑色：旋转处理
			else {
				// 直线情况：P在L，需右单旋
				if (cur == parent->_left) {
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				// 折线情况：P在R，需先左旋再右旋
				else { 
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
		// 情况二：P在G的右边（对称逻辑）
		else {
			Node* uncle = grandfather->_left;
			
			if (uncle && uncle->_col == RED) {
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				cur = grandfather;
				parent = cur->_parent;
			}
			else {
				// 直线情况：左单旋
				if (cur == parent->_right) {
					RotateL(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
				// 折线情况：双旋
				else {
					RotateR(parent); 
					RotateL(grandfather);
					parent->_col = grandfather->_col = RED;
					cur->_col = BLACK;
				}
				break;
			}
		}
	}
	_root->_col = BLACK; // 确保最终根为黑色
	return { cur, true };
}

// Uncle为红时的变色逻辑
Node* uncle = grandfather->_right; 
if (uncle && uncle->_col == RED) {
	parent->_col = BLACK;
	uncle->_col = BLACK;
	grandfather->_col = RED;
	cur = grandfather;
	parent = cur->_parent;
}

// 直线型：右单旋 (Cur -> Parent -> GrandFather)
if (parent->_left == cur) { 
	RotateR(grandfather);
	parent->_col = BLACK;
	grandfather->_col = RED;
}

// 折线型：双旋 (Cur -> Right of Parent -> Left of GrandFather)
else { 
	RotateL(parent); 
	RotateR(grandfather); 
	cur->_col = BLACK;
	grandfather->_col = RED; 
}

void RotateR(Node* parent) { // 右单旋
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	parent->_left = subLR;
	if (subLR) subLR->_parent = parent;

	subL->_right = parent;
	Node* pp = parent->_parent;
	parent->_parent = subL;

	// 更新subL的父级连接
	if (_root == parent) {
		_root = subL;
		subL->_parent = nullptr;
	} else {
		if (pp->_left == parent) pp->_left = subL;
		else pp->_right = subL;
		subL->_parent = pp;
	}
}

void RotateL(Node* parent) { // 左单旋
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	if (subRL) subRL->_parent = parent;

	subR->_left = parent;
	Node* pp = parent->_parent;
	parent->_parent = subR;

	if (_root == parent) {
		_root = subR;
		subR->_parent = nullptr;
	} else {
		if (pp->_left == parent) pp->_left = subR;
		else pp->_right = subR;
		subR->_parent = pp;
	}
}

bool CheckBalance() {
	if (!_root) return true;
	if (_root->_col != BLACK) return false; // 根必须黑

	// 统计根到最左路径的黑高
	int blackCount = 0;
	Node* left = _root;
	while (left) {
		if (left->_col == BLACK) blackCount++;
		left = left->_left;
	}

	return _CheckBalance(_root, blackCount, 0);
}

bool _CheckBalance(Node* root, int isBlackNum, int count) {
	if (!root) {
		if (count != isBlackNum) {
			printf("Path Black Count Mismatch\n");
			return false;
		}
		return true;
	}
	// 检查连续红色
	if (root->_col == RED && root->_parent->_col == RED) {
		printf("Continuous Red Nodes Found\n");
		return false;
	}
	// 累加黑高
	if (root->_col == BLACK) count++;
	
	// 递归检查左右子树
	return _CheckBalance(root->_left, isBlackNum, count) && 
		_CheckBalance(root->_right, isBlackNum, count);
}