Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- struct TNode {
- int color; // 0 - black, 1 - red, 2 - double-black;
- bool is_nil; // Is nil?
- int val; // Node's value.
- TNode *left; // Left sub-tree.
- TNode *right; // Right sub-tree.
- TNode *parent; // Parent of the node.
- };
- class RBtree {
- private:
- TNode *root;
- TNode *new_node(int);
- void set_node(TNode *, TNode *);
- void check_nil(TNode *&);
- int get_color(TNode *);
- void set_color(TNode *&, int);
- TNode *_find(TNode *, int);
- TNode *_find_least(TNode *);
- void rotate_left(TNode *);
- void rotate_right(TNode *);
- void _insert(int, TNode *&, TNode *);
- void insert_fix(TNode *);
- void _remove(TNode *&);
- void remove_fix(TNode *);
- public:
- RBtree() {
- root = nullptr;
- }
- TNode *find(int);
- void insert(int);
- void remove(int);
- void print(TNode *root=nullptr, int offset=0);
- };
- // Private functions {
- TNode *RBtree::new_node(int val) {
- TNode *node = new TNode({1, 0, val, nullptr, nullptr, nullptr});
- return node;
- }
- void RBtree::set_node(TNode *node, TNode *new_node) {
- if (new_node != nullptr) {
- new_node->parent = node->parent;
- }
- if (node->parent != nullptr) {
- if (node == node->parent->left) {
- node->parent->left = new_node;
- } else {
- node->parent->right = new_node;
- }
- } else {
- this->root = new_node;
- }
- }
- void RBtree::check_nil(TNode *&node) {
- if (node->is_nil) {
- if (node->parent != nullptr) {
- if (node == node->parent->left) {
- node->parent->left = nullptr;
- } else {
- node->parent->right = nullptr;
- }
- } else {
- this->root = nullptr;
- }
- free(node);
- }
- }
- int RBtree::get_color(TNode *node) {
- if (node == nullptr) {
- return 0;
- }
- return node->color;
- }
- void RBtree::set_color(TNode *&node, int color) {
- if (node != nullptr) {
- node->color = color;
- }
- }
- TNode *RBtree::_find(TNode *root, int val) {
- if (root == nullptr) {
- return nullptr;
- } else if (val == root->val) {
- return root;
- } else if (val < root->val) {
- return _find(root->left, val);
- } else {
- return _find(root->right, val);
- }
- }
- TNode *RBtree::_find_least(TNode *root) {
- while (root->left != nullptr) {
- root = root->left;
- }
- return root;
- }
- void RBtree::rotate_left(TNode *prev_root) {
- TNode *new_root = prev_root->right;
- prev_root->right = new_root->left;
- if (new_root->left != nullptr) {
- new_root->left->parent = prev_root;
- }
- new_root->parent = prev_root->parent;
- if (prev_root->parent == nullptr) {
- this->root = new_root;
- } else if (prev_root == prev_root->parent->left) {
- prev_root->parent->left = new_root;
- } else {
- prev_root->parent->right = new_root;
- }
- new_root->left = prev_root;
- prev_root->parent = new_root;
- }
- void RBtree::rotate_right(TNode *prev_root) {
- TNode *new_root = prev_root->left;
- prev_root->left = new_root->right;
- if (new_root->right != nullptr) {
- new_root->right->parent = prev_root;
- }
- new_root->parent = prev_root->parent;
- if (prev_root->parent == nullptr) {
- this->root = new_root;
- } else if (prev_root == prev_root->parent->left) {
- prev_root->parent->left = new_root;
- } else {
- prev_root->parent->right = new_root;
- }
- new_root->right = prev_root;
- prev_root->parent = new_root;
- }
- void RBtree::_insert(int val, TNode *&root, TNode *parent) {
- if (root == nullptr) {
- root = new_node(val);
- root->parent = parent;
- insert_fix(root);
- return;
- }
- if (val < root->val) {
- _insert(val, root->left, root);
- } else if (val > root->val) {
- _insert(val, root->right, root);
- }
- }
- void RBtree::insert_fix(TNode *root) {
- // Case 0. Root is always black.
- // Case 1. Root's uncle is red.
- // Case 2. Root's uncle is black, triangle.
- // Case 3. Root's uncle is black, line.
- while (root && get_color(root->parent) == 1) { // While parent is RED.
- // Root's parent is on the left side.
- if (root->parent == root->parent->parent->left) {
- TNode *uncle = root->parent->parent->right;
- if (get_color(uncle) == 1) { // Case 1. Uncle is RED.
- set_color(root->parent, 0); // Case 1. Recolor parent.
- set_color(uncle, 0); // Case 1. Recolor uncle.
- set_color(root->parent->parent, 1); // Case 1. Recolor granp.
- // Continue from grandparent, if exists.
- root = root->parent ? root->parent->parent : nullptr;
- } else {
- if (root == root->parent->right) { // Case 2. Triangle.
- root = root->parent; // Case 2.
- rotate_left(root); // Case 2.
- }
- set_color(root->parent, 0); // Case 3. Line.
- set_color(root->parent->parent, 1); // Case 3.
- rotate_right(root->parent->parent); // Case 3. Rotate granp.
- }
- }
- // Root's parent is on the right side.
- else {
- TNode *uncle = root->parent->parent->left;
- if (get_color(uncle) == 1) { // Case 1. Uncle is RED.
- set_color(root->parent, 0); // Case 1. Recolor parent.
- set_color(uncle, 0); // Case 1. Recolor uncle.
- set_color(root->parent->parent, 1); // Case 1. Recolor granp.
- // Continue from grandparent, if exists.
- root = root->parent ? root->parent->parent : nullptr;
- } else {
- if (root == root->parent->left) { // Case 2. Triangle.
- root = root->parent; // Case 2.
- rotate_right(root); // Case 2.
- }
- set_color(root->parent, 0); // Case 3. Line.
- set_color(root->parent->parent, 1); // Case 3.
- rotate_left(root->parent->parent); // Case 3. Rotate granp.
- }
- }
- }
- set_color(this->root, 0);
- }
- void RBtree::_remove(TNode *&root) {
- if (root->left && root->right) { // Both children
- TNode *successor = _find_least(root->right);
- root->val = successor->val;
- _remove(successor);
- }
- else if (!root->left && !root->right) { // Leaf
- if (get_color(root) == 1) { // Root is red
- set_node(root, nullptr);
- free(root);
- } else { // Root is black
- root->is_nil = 1;
- root->color = 2;
- remove_fix(root);
- }
- }
- else if (root->left || root->right) { // One child.
- TNode *child;
- if (root->left) { // Left child.
- child = root->left;
- } else { // Right child.
- child = root->right;
- }
- set_node(root, child);
- // Either root or it's child is red.
- if (get_color(root) == 1 or get_color(child) == 1) {
- set_color(child, 0);
- free(root);
- }
- // Both root and it's child are black.
- else {
- set_color(child, 2);
- remove_fix(child);
- }
- }
- }
- void RBtree::remove_fix(TNode *node) {
- while (true) {
- // Case 0. TERMINAL. Node is tree's root.
- if (node->parent == nullptr) {
- set_color(node, 0);
- check_nil(node);
- break;
- }
- // The node is not root, so we can find it's sibling.
- TNode *sib = nullptr;
- bool node_side = 0;
- if (node == node->parent->left) {
- sib = node->parent->right;
- node_side = 0;
- } else {
- sib = node->parent->left;
- node_side = 1;
- }
- // Case 1. Sibling is red.
- if (get_color(sib) == 1) {
- set_color(node->parent, 1);
- set_color(sib, 0);
- if (node_side == 0) {
- rotate_left(node->parent);
- } else {
- rotate_right(node->parent);
- }
- continue;
- }
- // Case 2. Sibling is black, sib's children are black.
- if (!get_color(sib) &&
- !get_color(sib->left) && !get_color(sib->right)) {
- set_color(sib, 1);
- set_color(node, 0);
- // Parent is red, terminal state.
- if (get_color(node->parent) == 1) {
- set_color(node->parent, 0);
- check_nil(node);
- break;
- }
- // Parent is black. Moving double-black to it.
- else {
- set_color(node->parent, 2);
- check_nil(node);
- node = node->parent;
- }
- continue;
- }
- // Case 3. Sibling is black, sib-inner:red, sib-outer: black.
- // Case 4. Sibling is black, sib-inner:---, sib-outer: red.
- if (get_color(sib) == 0) {
- if (node_side == 0) { // Node is left child, sibling is right.
- // Case 3.
- if (get_color(sib->left) == 1 && get_color(sib->right) == 0) {
- set_color(sib, 1);
- set_color(sib->left, 0);
- rotate_right(sib);
- }
- // Case 4. TERMINAL.
- if (get_color(sib->right) == 1) {
- set_color(sib->right, 0);
- set_color(sib, get_color(sib->parent));
- set_color(sib->parent, 0);
- set_color(node, 0);
- check_nil(node);
- rotate_left(sib->parent);
- break;
- }
- } else { // Node is right child, sibling is left.
- // Case 3.
- if (get_color(sib->right) == 1 && get_color(sib->left) == 0) {
- set_color(sib, 1);
- set_color(sib->right, 0);
- rotate_left(sib);
- }
- // Case 4. TERMINAL.
- if (get_color(sib->left) == 1) {
- set_color(sib->left, 0);
- set_color(sib, get_color(sib->parent));
- set_color(sib->parent, 0);
- set_color(node, 0);
- check_nil(node);
- rotate_right(sib->parent);
- break;
- }
- }
- }
- }
- set_color(this->root, 0);
- }
- // }
- // Public functions {
- TNode *RBtree::find(int val) {
- return _find(this->root, val);
- }
- void RBtree::insert(int val) {
- _insert(val, this->root, nullptr);
- }
- void RBtree::remove(int val) {
- TNode *node = find(val);
- if (node != nullptr) {
- _remove(node);
- }
- }
- void RBtree::print(TNode *root, int offset) {
- if (root == nullptr && offset == 0) {
- root = this->root;
- }
- if (root == nullptr) {
- return;
- }
- this->print(root->right, offset + 1);
- for (int i = 0; i < offset; i++) cout << " ";
- if (root->color == 0) {
- cout << "\033[1;34m";
- } else if (root->color == 1) {
- cout << "\033[1;31m";
- } else if (root->color == 2) {
- cout << "\033[1;30m";
- }
- if (root->is_nil) {
- cout << "N";
- } else {
- cout << root->val;
- }
- cout << "\033[0m\n";
- this->print(root->left, offset + 1);
- }
- // }
- int main() {
- RBtree tree;
- vector<int> v = {8, 15, 23, 17, 2, 16, 7, 21, 22};
- for (auto i : v) {
- tree.insert(i);
- }
- tree.print();
- int t, x;
- while (1) {
- cin >> t >> x;
- if (t == 0) {
- cout << "Inserting " << x << "...\n";
- tree.insert(x);
- } else {
- cout << "Removing " << x << "...\n";
- tree.remove(x);
- }
- cout << "----------------------------------------\n";
- tree.print();
- cout << "----------------------------------------\n\n\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement