c++红黑树算法怎么实现

红黑树是一种自平衡的二叉查找树，可以在O(log n)的时间复杂度内进行插入、删除和查找操作。以下是一个简单的C++实现红黑树的算法：

#include <iostream>using namespace std;enum Color { RED, BLACK };struct Node {int data;Color color;Node *left, *right, *parent;Node(int data) : data(data) {parent = left = right = NULL;color = RED;}};class RedBlackTree {private:Node *root;void rotateLeft(Node *x) {Node *y = x->right;x->right = y->left;if (y->left != NULL) {y->left->parent = x;}y->parent = x->parent;if (x->parent == NULL) {root = y;} else if (x == x->parent->left) {x->parent->left = y;} else {x->parent->right = y;}y->left = x;x->parent = y;}void rotateRight(Node *x) {Node *y = x->left;x->left = y->right;if (y->right != NULL) {y->right->parent = x;}y->parent = x->parent;if (x->parent == NULL) {root = y;} else if (x == x->parent->left) {x->parent->left = y;} else {x->parent->right = y;}y->right = x;x->parent = y;}void fixViolation(Node *x) {Node *parent = NULL;Node *grandparent = NULL;while (x != root && x->color == RED && x->parent->color == RED) {parent = x->parent;grandparent = x->parent->parent;if (parent == grandparent->left) {Node *uncle = grandparent->right;if (uncle != NULL && uncle->color == RED) {grandparent->color = RED;parent->color = BLACK;uncle->color = BLACK;x = grandparent;} else {if (x == parent->right) {rotateLeft(parent);x = parent;parent = x->parent;}rotateRight(grandparent);swap(parent->color, grandparent->color);x = parent;}} else {Node *uncle = grandparent->left;if (uncle != NULL && uncle->color == RED) {grandparent->color = RED;parent->color = BLACK;uncle->color = BLACK;x = grandparent;} else {if (x == parent->left) {rotateRight(parent);x = parent;parent = x->parent;}rotateLeft(grandparent);swap(parent->color, grandparent->color);x = parent;}}}root->color = BLACK;}void insertHelper(Node *node) {Node *cur = root;Node *parent = NULL;while (cur != NULL) {parent = cur;if (node->data < cur->data) {cur = cur->left;} else {cur = cur->right;}}node->parent = parent;if (parent == NULL) {root = node;} else if (node->data < parent->data) {parent->left = node;} else {parent->right = node;}fixViolation(node);}void inorderHelper(Node *node) {if (node == NULL) {return;}inorderHelper(node->left);cout << node->data << " ";inorderHelper(node->right);}public:RedBlackTree() : root(NULL) {}void insert(int data) {Node *node = new Node(data);insertHelper(node);}void inorder() {inorderHelper(root);}};int main() {RedBlackTree tree;tree.insert(7);tree.insert(3);tree.insert(18);tree.insert(10);tree.insert(22);tree.insert(8);tree.insert(11);tree.insert(26);cout << "Inorder traversal of the constructed Red-Black tree is: ";tree.inorder();return 0;}

上一篇：qt传递参数的方法是什么

下一篇：pycharm怎么刷新项目文件