#include <iostream>
#include <stack>
#include <queue>
enum Color {
RED,
BLACK
};
struct Node {
int data;
Color color;
Node* left;
Node* right;
Node* parent;
Node(int data, Color color) : data(data), color(color), left(nullptr), right(nullptr), parent(nullptr) {}
};
class RedBlackTree {
private:
Node* root;
public:
RedBlackTree() : root(nullptr) {}
void insert(int data) {
Node* new_node = new Node(data, RED);
if (root == nullptr) {
root = new_node;
root->color = BLACK;
return;
}
Node* current = root;
Node* parent = nullptr;
while (current != nullptr) {
parent = current;
if (data < current->data) {
current = current->left;
} else {
current = current->right;
}
}
new_node->parent = parent;
if (data < parent->data) {
parent->left = new_node;
} else {
parent->right = new_node;
}
fix_insert(new_node);
}
void fix_insert(Node* node) {
while (node != root && node->parent->color == RED) {
if (node->parent == node->parent->parent->left) {
Node* uncle = node->parent->parent->right;
if (uncle != nullptr && uncle->color == RED) {
node->parent->color = BLACK;
uncle->color = BLACK;
node->parent->parent->color = RED;
node = node->parent->parent;
} else {
if (node == node->parent->right) {
node = node->parent;
rotate_left(node);
}
node->parent->color = BLACK;
node->parent->parent->color = RED;
rotate_right(node->parent->parent);
}
} else {
Node* uncle = node->parent->parent->left;
if (uncle != nullptr && uncle->color == RED) {
node->parent->color = BLACK;
uncle->color = BLACK;
node->parent->parent->color = RED;
node = node->parent->parent;
} else {
if (node == node->parent->left) {
node = node->parent;
rotate_right(node);
}
node->parent->color = BLACK;
node->parent->parent->color = RED;
rotate_left(node->parent->parent);
}
}
}
root->color = BLACK;
}
void rotate_left(Node* node) {
Node* right_child = node->right;
node->right = right_child->left;
if (right_child->left != nullptr) {
right_child->left->parent = node;
}
right_child->parent = node->parent;
if (node->parent == nullptr) {
root = right_child;
} else if (node == node->parent->left) {
node->parent->left = right_child;
} else {
node->parent->right = right_child;
}
right_child->left = node;
node->parent = right_child;
}
void rotate_right(Node* node) {
Node* left_child = node->left;
node->left = left_child->right;
if (left_child->right != nullptr) {
left_child->right->parent = node;
}
left_child->parent = node->parent;
if (node->parent == nullptr) {
root = left_child;
} else if (node == node->parent->right) {
node->parent->right = left_child;
} else {
node->parent->left = left_child;
}
left_child->right = node;
node->parent = left_child;
}
void inorder_traversal(Node* node, std::queue<int>& q) {
if (node == nullptr) {
return;
}
inorder_traversal(node->left, q);
q.push(node->data);
inorder_traversal(node->right, q);
}
std::queue<int> inorder() {
std::queue<int> q;
inorder_traversal(root, q);
return q;
}
};
class RedBlackTreeIterator {
private:
std::queue<int> inorder_list;
public:
RedBlackTreeIterator(RedBlackTree& tree) {
inorder_list = tree.inorder();
}
int next() {
int data = inorder_list.front();
inorder_list.pop();
return data;
}
bool hasNext() {
return !inorder_list.empty();
}
};
int main() {
RedBlackTree tree;
tree.insert(10);
tree