#include <iostream>#include <mutex>#include <thread>#include <chrono>#include <random>#include <condition_variable>enum Color { RED, BLACK};template <typename T>class Node {public: T key; Node<T>* left; Node<T>* right; Node<T>* parent; Color color; Node(T key) : key(key), left(nullptr), right(nullptr), parent(nullptr), color(RED) {}};template <typename T>class RedBlackTree {private: Node<T>* root; std::mutex m;public: RedBlackTree() : root(nullptr) {} void insert(T key) { std::lock_guard<std::mutex> lock(m); Node<T>* newNode = new Node<T>(key); if (root == nullptr) { root = newNode; root->color = BLACK; return; } Node<T>* current = root; Node<T>* parent = nullptr; while (current != nullptr) { parent = current; if (key < current->key) { current = current->left; } else { current = current->right; } } newNode->parent = parent; if (key < parent->key) { parent->left = newNode; } else { parent->right = newNode; } fixViolation(newNode); } void printInOrder() { std::lock_guard<std::mutex> lock(m); printInOrderHelper(root); std::cout << std::endl; }private: void fixViolation(Node<T>* newNode) { Node<T>* parent = nullptr; Node<T>* grandparent = nullptr; while (newNode != root && newNode->color != BLACK && newNode->parent->color == RED) { parent = newNode->parent; grandparent = parent->parent; if (parent == grandparent->left) { Node<T>* uncle = grandparent->right; if (uncle != nullptr && uncle->color == RED) { grandparent->color = RED; parent->color = BLACK; uncle->color = BLACK; newNode = grandparent; } else { if (newNode == parent->right) { rotateLeft(parent); newNode = parent; parent = newNode->parent; } rotateRight(grandparent); std::swap(parent->color, grandparent->color); newNode = parent; } } else { Node<T>* uncle = grandparent->left; if (uncle != nullptr && uncle->color == RED) { grandparent->color = RED; parent->color = BLACK; uncle->color = BLACK; newNode = grandparent; } else { if (newNode == parent->left) { rotateRight(parent); newNode = parent; parent = newNode->parent; } rotateLeft(grandparent); std::swap(parent->color, grandparent->color); newNode = parent; } } } root->color = BLACK; } void rotateLeft(Node<T>* newNode) { Node<T>* rightChild = newNode->right; newNode->right = rightChild->left; if (newNode->right != nullptr) { newNode->right->parent = newNode; } rightChild->parent = newNode->parent; if (newNode->parent == nullptr) { root = rightChild; } else if (newNode == newNode->parent->left) { newNode->parent->left = rightChild; } else { newNode->parent->right = rightChild; } rightChild->left = newNode; newNode->parent = rightChild; } void rotateRight(Node<T>* newNode) { Node<T>* leftChild = newNode->left; newNode->left = leftChild->right; if (newNode->left != nullptr) { newNode->left->parent = newNode; } leftChild->parent = newNode->parent; if (newNode->parent == nullptr) { root = leftChild; } else if (newNode == newNode->parent->left) { newNode->parent->left = leftChild; } else { newNode->parent->right = leftChild; } leftChild->right = newNode; newNode->parent = leftChild; } void printInOrderHelper(Node<T>* current) { if (current == nullptr) { return; } printInOrderHelper(current->left); std::cout << current->key << " "; printInOrderHelper(current->right); }};int main() { RedBlackTree<int> tree; std::vector<std::thread> threads; for (int i = 0;
