#include <iostream>

using namespace std;

class Set {

public:

    struct Node {
        int value;
        Node* left;
        Node* right;
        Node* parent;
    };

    Set() : root_(nullptr), size_(0) {}

    void insert(const int& val) {
        if (root_ == nullptr) {
            root_ = new Node{ val, nullptr, nullptr, nullptr };
            size_++;
            return;
        }
        Node* parent = nullptr;
        Node* node = root_;
        while (node != nullptr && node->value != val) {
            parent = node;
            node = node->value > val ? node->left : node->right;
        }
        if (node == nullptr) {
            node = new Node{ val, nullptr, nullptr, parent };
            parent->value > val ? parent->left = node : parent->right = node;
            size_++;
        }
    }

    void erase(const int& val) {
        Node* parent = nullptr;
        Node* node = root_;
        while (node != nullptr && node->value != val) {
            parent = node;
            node = node->value > val ? node->left : node->right;
        }
        if (node != nullptr) {
            if (node->left == nullptr && node->right == nullptr) {
                if (node == root_) {
                    root_ = nullptr;
                }
                else {
                    node == parent->right ? parent->right = nullptr : parent->left = nullptr;
                }
                delete node;
            }
            else if (node->left == nullptr) {
                node->right->parent = node->parent;
                if (node == root_) {
                    root_ = node->right;
                }
                else {
                    node == parent->right ? parent->right = node->right : parent->left = node->right;
                }
                delete node;
            }
            else if (node->right == nullptr) {
                node->left->parent = node->parent;
                if (node == root_) {
                    root_ = node->left;
                }
                else {
                    node == parent->right ? parent->right = node->left : parent->left = node->left;
                }
                delete node;
            }
            else {
                Node* temp = min(node->right);
                node->value = temp->value;
                if (temp->right != nullptr) {
                    temp->right->parent = temp->parent;
                }
                temp == temp->parent->right ? temp->parent->right = temp->right : temp->parent->left = temp->right;
                delete temp;
            }
            size_--;
        }
    }

    Node* min(Node* node) {
        if (node != nullptr) {
            while (node->left != nullptr) {
                node = node->left;
            }
        }
        return node;
    }

    Node* max(Node* node) {
        if (node != nullptr) {
            while (node->right != nullptr) {
                node = node->right;
            }
        }
        return node;
    }

    void print() {
        print(root_);
        cout << endl;
    }

    int size() const {
        return size_;
    }

private:

    void print(Node* node) {
        if (node != nullptr) {
            print(node->left);
            cout << node->value << " ";
            print(node->right);
        }
    }

    Node* root_;
    int size_;
};


int main() {

    int arr[]{ 45,30,50,27,39,90,15,70,103 };

    Set st;

    for (int i = 0; i < 9; i++) {
        st.insert(arr[i]);
    }

    st.print();
    cout << st.size() << endl;

    st.erase(15);
    st.erase(50);
    st.erase(45);

    st.print();
    cout << st.size() << endl;

}