public:
    int Size() { return _Size(_root); }    // 用户只需調用 tree.Size()
    int Height() { return _Height(_root); } // 簡單、安全、易用
AI寫代碼
cpp
運行
3.5.2  私有實現：必須傳root
private:
    int _Size(Node* root) {  // 遞歸必須傳當前節點
        if (root == nullptr) return 0;
        return _Size(root->_left) + _Size(root->_right) + 1;  // 遞歸調用
    }
AI寫代碼
cpp
運行
3.5.3  解決方案：雙重接口設計
因此我們的解決方案如下——

3.5.3.1  公共層（面向用户）
// 用户看到的簡單接口
tree.Size();        // 不需要參數
tree.Height();      // 直接使用
tree.IsBalanceTree();
AI寫代碼
cpp
運行
3.5.3.2  私有層（內部遞歸）
// 遞歸實現的輔助函數
_Size(root);        // 需要節點參數
_Height(root);      // 支持遞歸遍歷
_IsBalanceTree(root);
AI寫代碼
cpp
運行
3.5.4  為什麼要設計成雙重接口？
// 方案1：讓用户傳root（不好）
tree.Size(someNode);  // 用户可能傳錯節點，不安全
 
// 方案2：放棄遞歸（不好）
// 用迭代實現Size()，但代碼複雜，性能可能更差
 
// 方案3：暴露_root（很不好）
tree._Size(tree._root);  // 破壞封裝，會很危險，不安全
AI寫代碼
cpp

完整代碼示例與實踐演示
RBTree.h：
#pragma once
#include<iostream>
using namespace std;
#include<assert.h>
 
// 枚舉值表示顏色
// 保障不是黑色就是紅色
enum Color
{
	BLACK,
	RED
};
 
// 這裏我們默認按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;
	Color _col;
 
	// 初始化
	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};
 
template<class K,class V>
struct RBTree
{
	typedef RBTreeNode<K, V> Node; // 重命名節點
public:
	bool Insert(const pair<K, V>& kv) // 紅黑樹的插入
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
 
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
 
		// 插入的是紅色的節點（新增）
		cur = new Node(kv);
		cur->_col = RED;
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
 
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)
			{
				//    g
				//  p   u
				// c     
				Node* uncle = grandfather->_right;
				// 叔叔存在且為黑
				if (uncle && uncle->_col == RED)
				{
					// 變色 + 繼續往上處理
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
 
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					// 叔叔不存在或者叔叔存在且為黑
					//    g
					//  p   u
					//		  c  
					// 單旋 + 變色
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//    g
						//  p   u
						//	  c 
						// 雙旋 + 變色
						RotateL(parent);
						RotateR(grandfather);
 
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
 
					break;
				}
			}
			else
			{
				//   g
				// u   p
				Node* uncle = grandfather->_left;
				// 叔叔存在且為紅->變色即可
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					// 繼續往上處理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					// 情況二：叔叔不存在或者存在且為黑
					// 旋轉 + 變色
					//    g
					//  u   p
					// c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//    g
						//  u   p
						// c
						RotateR(parent);
						RotateL(grandfather);
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK; // 不去判斷，直接變成黑的
 
		return true;
	}
 
	// -------------旋轉----------------
 
	// 右旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
 
		Node* parentParent = parent->_parent;
 
		subL->_right = parent;
		parent->_parent = subL;
 
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}
			subL->_parent = parentParent;
		}
	}
 
	// 左旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
 
		// 處理 subRL 與 parent 的關係
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		
		Node* parentParent = parent->_parent;
 
		// 處理 subR 與 parent 的關係
		subR->_left = parent;
		parent->_parent = subR;
 
		// 處理 subR 與 parentParent 的關係
		if (parentParent == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
	}
 
	// 中序遍歷
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
 
	// 查找
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if(cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
 
		return nullptr;
	}
 
	bool IsBalanceTree()
	{
		if (_root && _root->_col == RED)
			return false;
 
		// 最左路徑黑色節點的數量做參考值，去比較其他路徑
		int left_bn = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				left_bn++;
 
			cur = cur->_left; // 不加上會死循環
		}
 
		return _Checkcolor(_root, 0, left_bn);
	}
 
	int Height()
	{
		return _Height(_root);
	}
 
	int Size()
	{
		return _Size(_root);
	}
 
private:
	// 傳根，不能直接傳，外部調用內部
	int _Size(Node* root)
	{
		if (root == nullptr)
			return 0;
 
		return _Size(root->_left) + _Size(root->_right) + 1;
	}
 
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
 
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
 
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
 
	// root_cur_bn 根節點到當前節點路徑上的黑色節點的數量
	// 前序遞歸
	bool _Checkcolor(Node* root, int root_cur_bn,const int left_bn)
	{
		if (root == nullptr)
		{
			// 檢查每條路徑的黑色節點數量
			if (root_cur_bn != left_bn)
			{
				cout << "黑色節點的數量不相等" << endl;
				return false;
			}
			
			return true;
		}
 
		if (root->_col == BLACK)
		{
			root_cur_bn++;
		}
 
		// 檢查連續的紅色節點
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "存在連續的紅色節點" << endl;
			return false;
		}
		return _Checkcolor(root->_left, root_cur_bn, left_bn) 
			&& _Checkcolor(root->_right, root_cur_bn, left_bn);
	}
 
	int _InOrder(Node* root)
	{
		if (root == nullptr)
			return 0;
 
		_InOrder(root->_left);
		//cout << root->_kv.first << ":" << root->_kv.second << endl;
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
		////cout << root->_kv.first << ":" << root->_kv.second << endl;
	}
 
private:
	Node* _root = nullptr;
};
AI寫代碼
cpp
運行
Tree.cpp：
#define  _CRT_SECURE_NO_WARNINGS  1
#include<iostream>
#include<vector>
using namespace std;
#include"RBTree.h"
 
void TestRBTree1()
{
	RBTree<int, int>t;
	// 常規的測試用例
	int a[] = { 4,2,6,1,3,5,15,7,16,14 };
 
	for (auto e : a)
	{
		if (e == 7)
		{
			int i = 0;
		}
 
		t.Insert({ e,e });
 
		cout << "Insert:" << e << "->";
		t.InOrder();
	}
	t.InOrder();
 
	//cout << t.IsBalanceTree() << endl;
}
 
// 插入一堆隨機值，測試平衡，順便測試一下高度和性能
void TestRBTree2()
{
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
 
	size_t begin2 = clock();
	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.IsBalanceTree() << endl;
 
	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;
	size_t begin1 = clock();
	// 確定在的值
	/*for (auto e : v)
	{
		t.Find(e);
	}*/
 
	// 隨機值
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;
}
 
int main()
{
	//TestRBTree1();
	TestRBTree2();
 
	return 0;
}
AI寫代碼
cpp
運行