#include <stdio.h>
#include <stdlib.h>// 红黑树节点颜色定义
typedef enum { RED, BLACK } NodeColor;// 红黑树节点结构
typedef struct RBTreeNode {int key; // 节点的键值NodeColor color; // 节点的颜色（红或黑）struct RBTreeNode *left; // 左子节点struct RBTreeNode *right; // 右子节点struct RBTreeNode *parent; // 父节点
} RBTreeNode;// 红黑树结构
typedef struct RBTree {RBTreeNode *root; // 根节点RBTreeNode *nil; // 哨兵节点（所有空节点指向这个）
} RBTree;// 创建一个新节点
RBTreeNode *createNode(RBTree *tree, int key) {RBTreeNode *node = (RBTreeNode *)malloc(sizeof(RBTreeNode));if (node == NULL) {fprintf(stderr, "Memory allocation failed for new node.\n");exit(EXIT_FAILURE);}node->key = key;node->color = RED; // 新插入节点默认为红色node->left = tree->nil;node->right = tree->nil;node->parent = tree->nil;return node;
}// 初始化红黑树
RBTree *createTree() {RBTree *tree = (RBTree *)malloc(sizeof(RBTree));if (tree == NULL) {fprintf(stderr, "Memory allocation failed for tree.\n");exit(EXIT_FAILURE);}// 初始化哨兵节点tree->nil = (RBTreeNode *)malloc(sizeof(RBTreeNode));if (tree->nil == NULL) {fprintf(stderr, "Memory allocation failed for sentinel node.\n");exit(EXIT_FAILURE);}tree->nil->color = BLACK;tree->root = tree->nil;return tree;
}// 左旋转
void leftRotate(RBTree *tree, RBTreeNode *x) {RBTreeNode *y = x->right;x->right = y->left;if (y->left != tree->nil)y->left->parent = x;y->parent = x->parent;if (x->parent == tree->nil)tree->root = y;else if (x == x->parent->left)x->parent->left = y;elsex->parent->right = y;y->left = x;x->parent = y;
}// 右旋转
void rightRotate(RBTree *tree, RBTreeNode *x) {RBTreeNode *y = x->left;x->left = y->right;if (y->right != tree->nil)y->right->parent = x;y->parent = x->parent;if (x->parent == tree->nil)tree->root = y;else if (x == x->parent->right)x->parent->right = y;elsex->parent->left = y;y->right = x;x->parent = y;
}// 插入修复（保持红黑树性质）
void insertFixup(RBTree *tree, RBTreeNode *z) {while (z->parent->color == RED) {if (z->parent == z->parent->parent->left) {RBTreeNode *y = z->parent->parent->right; // 叔叔节点if (y->color == RED) { // Case 1: 叔叔是红色z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;} else {if (z == z->parent->right) { // Case 2: 叔叔是黑色，当前节点是右子节点z = z->parent;leftRotate(tree, z);}z->parent->color = BLACK; // Case 3: 叔叔是黑色，当前节点是左子节点z->parent->parent->color = RED;rightRotate(tree, z->parent->parent);}} else {RBTreeNode *y = z->parent->parent->left; // 叔叔节点if (y->color == RED) { // Case 1: 叔叔是红色z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;} else {if (z == z->parent->left) { // Case 2: 叔叔是黑色，当前节点是左子节点z = z->parent;rightRotate(tree, z);}z->parent->color = BLACK; // Case 3: 叔叔是黑色，当前节点是右子节点z->parent->parent->color = RED;leftRotate(tree, z->parent->parent);}}}tree->root->color = BLACK; // 根节点必须为黑色
}// 插入节点
void rbInsert(RBTree *tree, int key) {RBTreeNode *z = createNode(tree, key);RBTreeNode *y = tree->nil;RBTreeNode *x = tree->root;// 查找插入位置while (x != tree->nil) {y = x;if (z->key < x->key)x = x->left;elsex = x->right;}z->parent = y;// 插入为根节点或子节点if (y == tree->nil)tree->root = z;else if (z->key < y->key)y->left = z;elsey->right = z;z->left = tree->nil;z->right = tree->nil;z->color = RED;// 修复红黑树性质insertFixup(tree, z);
}// 中序遍历（调试用）
void inorderTraversal(RBTree *tree, RBTreeNode *node) {if (node != tree->nil) {inorderTraversal(tree, node->left);printf("%d(%s) ", node->key, node->color == RED ? "R" : "B");inorderTraversal(tree, node->right);}
}// 释放节点
void freeNode(RBTree *tree, RBTreeNode *node) {if (node != tree->nil) {freeNode(tree, node->left);freeNode(tree, node->right);free(node);}
}// 释放红黑树
void freeTree(RBTree *tree) {freeNode(tree, tree->root);free(tree->nil);free(tree);
}// 主函数
int main() {RBTree *tree = createTree();// 插入数据rbInsert(tree, 10);rbInsert(tree, 20);rbInsert(tree, 30);rbInsert(tree, 15);rbInsert(tree, 25);// 中序遍历printf("Inorder Traversal of Red-Black Tree:\n");inorderTraversal(tree, tree->root);printf("\n");// 释放红黑树freeTree(tree);return 0;
}
C语言版本
结构设计：
RBTree包含根节点和哨兵节点。- 哨兵节点用于表示空节点，避免频繁的空指针检查。
关键功能：
createNode()创建一个红色的新节点。leftRotate()和rightRotate()实现红黑树的旋转操作。insertFixup()修复红黑树插入后的平衡性。增强健壮性：
- 内存分配失败时打印错误并终止程序。
- 所有空节点使用哨兵节点，避免空指针操作。
调试功能：
- 中序遍历函数
inorderTraversal()输出红黑树的节点及其颜色，便于调试。内存管理：
- 在程序结束时释放分配的内存，避免内存泄漏。
#include <iostream>
#include <memory> // 用于智能指针
using namespace std;// 红黑树节点颜色定义
enum NodeColor { RED, BLACK };// 红黑树节点类
struct RBTreeNode {int key; // 节点的键值NodeColor color; // 节点的颜色shared_ptr<RBTreeNode> left; // 左子节点shared_ptr<RBTreeNode> right; // 右子节点weak_ptr<RBTreeNode> parent; // 父节点（使用 weak_ptr 避免循环引用）// 构造函数RBTreeNode(int k, NodeColor c): key(k), color(c), left(nullptr), right(nullptr), parent() {}
};// 红黑树类
class RBTree {
private:shared_ptr<RBTreeNode> root; // 根节点shared_ptr<RBTreeNode> nil; // 哨兵节点// 左旋转void leftRotate(shared_ptr<RBTreeNode> x) {auto y = x->right; // y 是 x 的右子节点x->right = y->left; // 将 y 的左子树移动为 x 的右子树if (y->left != nil) {y->left->parent = x;}y->parent = x->parent; // 更新 y 的父节点if (x->parent.lock() == nil) {root = y;} else if (x == x->parent.lock()->left) {x->parent.lock()->left = y;} else {x->parent.lock()->right = y;}y->left = x;x->parent = y;}// 右旋转void rightRotate(shared_ptr<RBTreeNode> x) {auto y = x->left; // y 是 x 的左子节点x->left = y->right; // 将 y 的右子树移动为 x 的左子树if (y->right != nil) {y->right->parent = x;}y->parent = x->parent; // 更新 y 的父节点if (x->parent.lock() == nil) {root = y;} else if (x == x->parent.lock()->right) {x->parent.lock()->right = y;} else {x->parent.lock()->left = y;}y->right = x;x->parent = y;}// 插入修复void insertFixup(shared_ptr<RBTreeNode> z) {while (z->parent.lock()->color == RED) {if (z->parent.lock() == z->parent.lock()->parent.lock()->left) {auto y = z->parent.lock()->parent.lock()->right; // 叔叔节点if (y->color == RED) { // Case 1: 叔叔是红色z->parent.lock()->color = BLACK;y->color = BLACK;z->parent.lock()->parent.lock()->color = RED;z = z->parent.lock()->parent.lock();} else {if (z == z->parent.lock()->right) { // Case 2: 当前节点是右子节点z = z->parent.lock();leftRotate(z);}z->parent.lock()->color = BLACK; // Case 3: 当前节点是左子节点z->parent.lock()->parent.lock()->color = RED;rightRotate(z->parent.lock()->parent.lock());}} else {auto y = z->parent.lock()->parent.lock()->left; // 叔叔节点if (y->color == RED) { // Case 1: 叔叔是红色z->parent.lock()->color = BLACK;y->color = BLACK;z->parent.lock()->parent.lock()->color = RED;z = z->parent.lock()->parent.lock();} else {if (z == z->parent.lock()->left) { // Case 2: 当前节点是左子节点z = z->parent.lock();rightRotate(z);}z->parent.lock()->color = BLACK; // Case 3: 当前节点是右子节点z->parent.lock()->parent.lock()->color = RED;leftRotate(z->parent.lock()->parent.lock());}}}root->color = BLACK; // 根节点必须为黑色}public:// 构造函数RBTree() {nil = make_shared<RBTreeNode>(0, BLACK); // 初始化哨兵节点root = nil;}// 插入节点void rbInsert(int key) {auto z = make_shared<RBTreeNode>(key, RED); // 创建新节点z->left = nil;z->right = nil;auto y = nil;auto x = root;// 查找插入位置while (x != nil) {y = x;if (z->key < x->key) {x = x->left;} else {x = x->right;}}z->parent = y;// 插入为根节点或子节点if (y == nil) {root = z;} else if (z->key < y->key) {y->left = z;} else {y->right = z;}// 修复红黑树性质insertFixup(z);}// 中序遍历（调试用）void inorderTraversal(shared_ptr<RBTreeNode> node) const {if (node != nil) {inorderTraversal(node->left);cout << node->key << "(" << (node->color == RED ? "R" : "B") << ") ";inorderTraversal(node->right);}}// 中序遍历接口void inorderTraversal() const {inorderTraversal(root);cout << endl;}// 释放节点void freeTree() {root = nil; // 自动释放内存}// 析构函数~RBTree() {freeTree();}
};// 主函数
int main() {RBTree tree;// 插入数据tree.rbInsert(10);tree.rbInsert(20);tree.rbInsert(30);tree.rbInsert(15);tree.rbInsert(25);// 中序遍历cout << "Inorder Traversal of Red-Black Tree:" << endl;tree.inorderTraversal();return 0;
}
CPP版本
类设计：
RBTreeNode表示红黑树的节点。- 使用
shared_ptr和weak_ptr管理内存，避免手动释放内存和循环引用问题。RBTree是红黑树的主体类，包含插入、修复和遍历功能。增强健壮性：
- 使用智能指针避免内存泄漏。
nil节点用作哨兵节点，减少空指针判断的复杂性。关键功能：
- 左旋转和右旋转操作用于维护红黑树的平衡。
- 插入修复算法确保红黑树性质不被破坏。
内存管理：
- 使用智能指针 (
shared_ptr和weak_ptr) 自动管理内存。- 在析构函数中清空树，释放资源。
调试功能：
- 提供
inorderTraversal()函数，按中序输出节点的键值和颜色，便于验证红黑树结构。
