#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;