#include <iostream>

using namespace std;

class Set {

public:

    struct Node {
        int value = 0;
        Node* left = nullptr;
        Node* right = nullptr;
        Node* parent = nullptr;
    };

    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* temp = new Node{ val, nullptr, nullptr, parent };

            parent->value > val ? parent->left = temp : parent->right = temp;
            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);
                if (temp->right) {
                    temp->right->parent = temp->parent;
                }
                temp == temp->parent->right ? temp->parent->right = temp->right : temp->parent->left = temp->right;
                node->value = temp->value;
                delete temp;
            }
            size--;
        }
    }

    void Print() {
        Print(root);
        cout << endl;
    }

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

    int Size() {
        return 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;
    }

    Node* Find(const int& val) {
        Node* node = root;
        while (node != nullptr && node->value != val) {
            node = node->value > val ? node->left : node->right;
        }
        return node;
    }

    int Count(const int& val) {
        return Find(val) == nullptr ? 0 : 1;
    }

    Node* Next(Node* node) {
        if (node) {
            if (node->right) {
                return Min(node->right);
            }
            Node* parent = node->parent;
            while (parent != nullptr && parent->value < node->value) {
                node = parent;
                parent = parent->parent;
            }
            return parent;
        }
    }

private:
    int size = 0;
    Node* root = nullptr;
};


void main() {
    Set tr;
    srand(time(NULL));
    int arr[]{ 45, 30, 50, 27, 39, 90, 30, 15, 70, 93 };
    for (int i = 0; i < 10; i++) {
        //int val = rand() % 100;
        int val = arr[i];
        cout << val << " ";
        tr.Insert(val);
    }
    cout << endl << endl;

    tr.Print();

    //tr.Erase(45);
    tr.Print();

    auto node_ptr = tr.Find(39);
    cout << node_ptr->value << endl;
    auto node_next_ptr = tr.Next(node_ptr);
    cout << node_next_ptr->value << endl;
    cout << tr.Count(50) << endl;
    cout << tr.Count(49) << endl;
}