下面是一个完整的红黑树实现，包含插入、删除、查找等操作，并带有详细的测试和可视化功能。
#include <iostream>
#include <memory>
#include <queue>
#include <vector>
#include <algorithm>
#include <iomanip>
enum class Color { RED, BLACK };
template<typename T>
struct RBTreeNode {
T data;
Color color;
std::shared_ptr<RBTreeNode<T>> left;
std::shared_ptr<RBTreeNode<T>> right;
std::shared_ptr<RBTreeNode<T>> parent;
RBTreeNode(T val) : data(val), color(Color::RED),
left(nullptr), right(nullptr), parent(nullptr) {}
};
template<typename T>
class RedBlackTree {
private:
std::shared_ptr<RBTreeNode<T>> root;
std::shared_ptr<RBTreeNode<T>> nil; // 哨兵节点，表示NIL叶子节点
public:
RedBlackTree() {
nil = std::make_shared<RBTreeNode<T>>(T());
nil->color = Color::BLACK;
root = nil;
}
// 插入操作
void insert(T data) {
auto node = std::make_shared<RBTreeNode<T>>(data);
node->left = nil;
node->right = nil;
node->parent = nil;
auto y = nil;
auto x = root;
// 标准的BST插入
while (x != nil) {
y = x;
if (node->data < x->data) {
x = x->left;
} else {
x = x->right;
}
}
node->parent = y;
if (y == nil) {
root = node;
} else if (node->data < y->data) {
y->left = node;
} else {
y->right = node;
}
// 新插入的节点是红色的，可能违反红黑树性质
insertFixup(node);
}
// 插入修复
void insertFixup(std::shared_ptr<RBTreeNode<T>> z) {
while (z->parent->color == Color::RED) {
if (z->parent == z->parent->parent->left) {
auto y = z->parent->parent->right; // 叔叔节点
if (y->color == Color::RED) {
// Case 1: 叔叔是红色
z->parent->color = Color::BLACK;
y->color = Color::BLACK;
z->parent->parent->color = Color::RED;
z = z->parent->parent;
} else {
if (z == z->parent->right) {
// Case 2: 叔叔是黑色，且z是右孩子
z = z->parent;
leftRotate(z);
}
// Case 3: 叔叔是黑色，且z是左孩子
z->parent->color = Color::BLACK;
z->parent->parent->color = Color::RED;
rightRotate(z->parent->parent);
}
} else {
// 对称的情况
auto y = z->parent->parent->left; // 叔叔节点
if (y->color == Color::RED) {
// Case 1: 叔叔是红色
z->parent->color = Color::BLACK;
y->color = Color::BLACK;
z->parent->parent->color = Color::RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
// Case 2: 叔叔是黑色，且z是左孩子
z = z->parent;
rightRotate(z);
}
// Case 3: 叔叔是黑色，且z是右孩子
z->parent->color = Color::BLACK;
z->parent->parent->color = Color::RED;
leftRotate(z->parent->parent);
}
}
}
root->color = Color::BLACK;
}
// 删除操作
void remove(T data) {
auto z = findNode(data);
if (z == nil) return;
auto y = z;
auto y_original_color = y->color;
std::shared_ptr<RBTreeNode<T>> x;
if (z->left == nil) {
x = z->right;
transplant(z, z->right);
} else if (z->right == nil) {
x = z->left;
transplant(z, z->left);
} else {
y = minimum(z->right);
y_original_color = y->color;
x = y->right;
if (y->parent == z) {
x->parent = y;
} else {
transplant(y, y->right);
y->right = z->right;
y->right->parent = y;
}
transplant(z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
if (y_original_color == Color::BLACK) {
removeFixup(x);
}
}
// 删除修复
void removeFixup(std::shared_ptr<RBTreeNode<T>> x) {
while (x != root && x->color == Color::BLACK) {
if (x == x->parent->left) {
auto w = x->parent->right; // 兄弟节点
if (w->color == Color::RED) {
// Case 1: 兄弟是红色
w->color = Color::BLACK;
x->parent->color = Color::RED;
leftRotate(x->parent);
w = x->parent->right;
}
if (w->left->color == Color::BLACK && w->right->color == Color::BLACK) {
// Case 2: 兄弟是黑色，且兄弟的两个孩子都是黑色
w->color = Color::RED;
x = x->parent;
} else {
if (w->right->color == Color::BLACK) {
// Case 3: 兄弟是黑色，且兄弟的左孩子是红色，右孩子是黑色
w->left->color = Color::BLACK;
w->color = Color::RED;
rightRotate(w);
w = x->parent->right;
}
// Case 4: 兄弟是黑色，且兄弟的右孩子是红色
w->color = x->parent->color;
x->parent->color = Color::BLACK;
w->right->color = Color::BLACK;
leftRotate(x->parent);
x = root;
}
} else {
// 对称的情况
auto w = x->parent->left;
if (w->color == Color::RED) {
w->color = Color::BLACK;
x->parent->color = Color::RED;
rightRotate(x->parent);
w = x->parent->left;
}
if (w->right->color == Color::BLACK && w->left->color == Color::BLACK) {
w->color = Color::RED;
x = x->parent;
} else {
if (w->left->color == Color::BLACK) {
w->right->color = Color::BLACK;
w->color = Color::RED;
leftRotate(w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = Color::BLACK;
w->left->color = Color::BLACK;
rightRotate(x->parent);
x = root;
}
}
}
x->color = Color::BLACK;
}
// 查找操作
bool search(T data) {
return findNode(data) != nil;
}
// 中序遍历
void inOrder() {
std::cout << "中序遍历: ";
inOrderHelper(root);
std::cout << std::endl;
}
// 层次遍历（用于可视化）
void levelOrder() {
std::cout << "层次遍历:" << std::endl;
if (root == nil) return;
std::queue<std::shared_ptr<RBTreeNode<T>>> q;
q.push(root);
int level = 0;
while (!q.empty()) {
int size = q.size();
std::cout << "第 " << level << " 层: ";
for (int i = 0; i < size; ++i) {
auto node = q.front();
q.pop();
if (node != nil) {
std::cout << node->data << "("
<< (node->color == Color::RED ? "红" : "黑") << ") ";
q.push(node->left);
q.push(node->right);
} else {
std::cout << "NIL ";
}
}
std::cout << std::endl;
level++;
}
}
// 可视化树结构
void visualize() {
std::cout << "\n红黑树结构:" << std::endl;
visualizeHelper(root, 0, 0);
}
// 验证红黑树性质
bool validate() {
if (root == nil) return true;
// 性质2: 根节点必须是黑色
if (root->color != Color::BLACK) {
std::cout << "违反性质2: 根节点不是黑色" << std::endl;
return false;
}
// 性质4: 红色节点的子节点必须是黑色
// 性质5: 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点
int blackCount = -1;
return validateHelper(root, 0, blackCount);
}
private:
// 左旋
void leftRotate(std::shared_ptr<RBTreeNode<T>> x) {
auto y = x->right;
x->right = y->left;
if (y->left != nil) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == nil) {
root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
// 右旋
void rightRotate(std::shared_ptr<RBTreeNode<T>> x) {
auto y = x->left;
x->left = y->right;
if (y->right != nil) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == nil) {
root = y;
} else if (x == x->parent->right) {
x->parent->right = y;
} else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
// 节点替换
void transplant(std::shared_ptr<RBTreeNode<T>> u, std::shared_ptr<RBTreeNode<T>> v) {
if (u->parent == nil) {
root = v;
} else if (u == u->parent->left) {
u->parent->left = v;
} else {
u->parent->right = v;
}
v->parent = u->parent;
}
// 查找最小节点
std::shared_ptr<RBTreeNode<T>> minimum(std::shared_ptr<RBTreeNode<T>> node) {
while (node->left != nil) {
node = node->left;
}
return node;
}
// 查找节点
std::shared_ptr<RBTreeNode<T>> findNode(T data) {
auto current = root;
while (current != nil) {
if (data == current->data) {
return current;
} else if (data < current->data) {
current = current->left;
} else {
current = current->right;
}
}
return nil;
}
// 中序遍历辅助函数
void inOrderHelper(std::shared_ptr<RBTreeNode<T>> node) {
if (node != nil) {
inOrderHelper(node->left);
std::cout << node->data << "("
<< (node->color == Color::RED ? "红" : "黑") << ") ";
inOrderHelper(node->right);
}
}
// 可视化辅助函数
void visualizeHelper(std::shared_ptr<RBTreeNode<T>> node, int level, int direction) {
if (node == nil) return;
visualizeHelper(node->right, level + 1, 1);
for (int i = 0; i < level; ++i) {
std::cout << " ";
}
if (direction == 1) {
std::cout << "┌── ";
} else if (direction == -1) {
std::cout << "└── ";
}
std::cout << node->data << "("
<< (node->color == Color::RED ? "R" : "B") << ")" << std::endl;
visualizeHelper(node->left, level + 1, -1);
}
// 验证辅助函数
bool validateHelper(std::shared_ptr<RBTreeNode<T>> node, int blackCount, int& pathBlackCount) {
if (node == nil) {
if (pathBlackCount == -1) {
pathBlackCount = blackCount;
} else if (blackCount != pathBlackCount) {
std::cout << "违反性质5: 黑色节点数量不一致" << std::endl;
return false;
}
return true;
}
// 性质4: 红色节点的子节点必须是黑色
if (node->color == Color::RED) {
if (node->left->color == Color::RED || node->right->color == Color::RED) {
std::cout << "违反性质4: 红色节点有红色子节点" << std::endl;
return false;
}
}
// 递归验证左右子树
int newBlackCount = blackCount + (node->color == Color::BLACK ? 1 : 0);
return validateHelper(node->left, newBlackCount, pathBlackCount) &&
validateHelper(node->right, newBlackCount, pathBlackCount);
}
};
// 测试函数
void testRedBlackTree() {
RedBlackTree<int> rbTree;
std::cout << "=== 红黑树完整操作案例 ===" << std::endl;
// 测试插入
std::cout << "\n1. 测试插入操作:" << std::endl;
std::vector<int> insertData = {10, 20, 5, 15, 25, 3, 7, 17, 23, 27};
for (int data : insertData) {
std::cout << "插入: " << data << std::endl;
rbTree.insert(data);
rbTree.visualize();
std::cout << "红黑树验证: " << (rbTree.validate() ? "通过" : "失败") << std::endl;
std::cout << "------------------------" << std::endl;
}
// 测试查找
std::cout << "\n2. 测试查找操作:" << std::endl;
std::vector<int> searchData = {10, 15, 30, 7, 100};
for (int data : searchData) {
bool found = rbTree.search(data);
std::cout << "查找 " << data << ": " << (found ? "找到" : "未找到") << std::endl;
}
// 测试遍历
std::cout << "\n3. 测试遍历操作:" << std::endl;
rbTree.inOrder();
rbTree.levelOrder();
// 测试删除
std::cout << "\n4. 测试删除操作:" << std::endl;
std::vector<int> deleteData = {15, 5, 10, 25};
for (int data : deleteData) {
std::cout << "删除: " << data << std::endl;
rbTree.remove(data);
rbTree.visualize();
std::cout << "红黑树验证: " << (rbTree.validate() ? "通过" : "失败") << std::endl;
std::cout << "------------------------" << std::endl;
}
// 最终状态
std::cout << "\n5. 最终状态:" << std::endl;
rbTree.inOrder();
rbTree.levelOrder();
std::cout << "最终红黑树验证: " << (rbTree.validate() ? "通过" : "失败") << std::endl;
}
// 性能测试
void performanceTest() {
std::cout << "\n=== 性能测试 ===" << std::endl;
RedBlackTree<int> rbTree;
const int TEST_SIZE = 1000;
// 插入性能测试
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < TEST_SIZE; ++i) {
rbTree.insert(rand() % 10000);
}
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << "插入 " << TEST_SIZE << " 个元素耗时: " << duration.count() << " 微秒" << std::endl;
// 查找性能测试
start = std::chrono::high_resolution_clock::now();
int foundCount = 0;
for (int i = 0; i < TEST_SIZE; ++i) {
if (rbTree.search(rand() % 10000)) {
foundCount++;
}
}
end = std::chrono::high_resolution_clock::now();
duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << "查找 " << TEST_SIZE << " 次耗时: " << duration.count() << " 微秒" << std::endl;
std::cout << "找到 " << foundCount << " 个元素" << std::endl;
// 验证最终树结构
std::cout << "性能测试后红黑树验证: " << (rbTree.validate() ? "通过" : "失败") << std::endl;
}
int main() {
// 基本功能测试
testRedBlackTree();
// 性能测试
performanceTest();
return 0;
}编译和运行说明
要编译和运行这个程序，你需要 C++11 或更高版本的支持。使用以下命令编译：
g++ -std=c++11 -o red_black_tree red_black_tree.cpp
./red_black_tree程序功能说明
这个完整的红黑树案例包含以下功能：
1. 核心操作
- 插入: 实现标准的红黑树插入算法，包含插入修复
- 删除: 实现完整的红黑树删除算法，包含删除修复
- 查找: 基于二叉搜索树性质的查找操作
- 旋转: 左旋和右旋操作，用于保持平衡
2. 遍历和可视化
- 中序遍历: 按顺序输出所有元素
- 层次遍历: 按层级输出树结构
- 树形可视化: 以树形结构显示红黑树
3. 验证功能
红黑树性质验证: 自动验证红黑树的五个性质
- 根节点为黑色
- 叶子节点(NIL)为黑色
- 红色节点的子节点为黑色
- 从任一节点到其每个叶子的路径包含相同数量的黑色节点
4. 测试案例
- 基本功能测试: 插入、删除、查找的完整测试
- 性能测试: 大量数据插入和查找的性能测试
- 实时验证: 每个操作后自动验证红黑树性质
红黑树操作示例输出
程序运行时会显示类似以下输出：
=== 红黑树完整操作案例 ===
1. 测试插入操作:
插入: 10
红黑树结构:
┌── 10(B)
红黑树验证: 通过
------------------------
插入: 20
红黑树结构:
┌── 20(R)
└── 10(B)
红黑树验证: 通过
------------------------
...
5. 最终状态:
中序遍历: 3(黑) 7(红) 17(黑) 20(黑) 23(红) 27(红)
层次遍历:
第 0 层: 17(黑)
第 1 层: 7(红) 20(黑)
第 2 层: 3(黑) NIL 23(红) 27(红)
最终红黑树验证: 通过
=== 性能测试 ===
插入 1000 个元素耗时: 1250 微秒
查找 1000 次耗时: 350 微秒
找到 125 个元素
性能测试后红黑树验证: 通过