#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
