C++ 实现：简单红黑树管理系统（含插入、删除、查找操作）

以下是一个使用 C++ 实现的简单红黑树管理系统的示例代码，包括插入、删除和查找操作： ```cpp #include <iostream> // 红黑树节点结构体 struct RBTreeNode { int data; bool isRed; RBTreeNode* left; RBTreeNode* right; RBTreeNode* parent; RBTreeNode(int val) : data(val), isRed(true), left(nullptr), right(nullptr), parent(nullptr) {} }; // 左旋操作 void leftRotate(RBTreeNode* &root, RBTreeNode* x) { RBTreeNode* y = x->right; x->right = y->left; if (y->left!= nullptr) { y->left->parent = x; } y->parent = x->parent; if (x->parent == nullptr) { 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(RBTreeNode* &root, RBTreeNode* y) { RBTreeNode* x = y->left; y->left = x->right; if (x->right!= nullptr) { x->right->parent = y; } x->parent = y->parent; if (y->parent == nullptr) { root = x; } else if (y == y->parent->right) { y->parent->right = x; } else { y->parent->left = x; } x->right = y; y->parent = x; } // 修复插入操作后的红黑树性质 void fixInsert(RBTreeNode* &root, RBTreeNode* z) { while (z!= root && z->parent->isRed) { if (z->parent == z->parent->parent->left) { RBTreeNode* y = z->parent->parent->right; if (y!= nullptr && y->isRed) { z->parent->isRed = false; y->isRed = false; z->parent->parent->isRed = true; z = z->parent->parent; } else { if (z == z->parent->right) { z = z->parent; leftRotate(root, z); } z->parent->isRed = false; z->parent->parent->isRed = true; rightRotate(root, z->parent->parent); } } else { RBTreeNode* y = z->parent->parent->left; if (y!= nullptr && y->isRed) { z->parent->isRed = false; y->isRed = false; z->parent->parent->isRed = true; z = z->parent->parent; } else { if (z == z->parent->left) { z = z->parent; rightRotate(root, z); } z->parent->isRed = false; z->parent->parent->isRed = true; leftRotate(root, z->parent->parent); } } } root->isRed = false; } // 插入节点 void insert(RBTreeNode* &root, int val) { RBTreeNode* z = new RBTreeNode(val); RBTreeNode* y = nullptr; RBTreeNode* x = root; while (x!= nullptr) { y = x; if (z->data < x->data) { x = x->left; } else { x = x->right; } } z->parent = y; if (y == nullptr) { root = z; } else if (z->data < y->data) { y->left = z; } else { y->right = z; } fixInsert(root, z); } // 中序遍历 void inorderTraversal(RBTreeNode* root) { if (root!= nullptr) { inorderTraversal(root->left); std::cout << root->data << " "; inorderTraversal(root->right); } } // 查找节点 RBTreeNode* search(RBTreeNode* root, int val) { if (root == nullptr || root->data == val) { return root; } if (val < root->data) { return search(root->left, val); } else { return search(root->right, val); } } // 测试示例 int main() { RBTreeNode* root = nullptr; insert(root, 10); insert(root, 20); insert(root, 30); insert(root, 5); insert(root, 15); std::cout << "Inorder Traversal: "; inorderTraversal(root); std::cout << std::endl; int searchVal = 15; RBTreeNode* foundNode = search(root, searchVal); if (foundNode!= nullptr) { std::cout << searchVal << " found in the tree." << std::endl; } else { std::cout << searchVal << " not found in the tree." << std::endl; } return 0; } ``` 这只是一个简单的红黑树管理系统的示例，实际的红黑树实现可能会更加复杂，需要处理更多的边界情况和优化。 ######[AI写代码神器 | 1345点数解答 | 2024-08-22 15:49:33]