#include <iostream>
#include <string>

using namespace std;

template <typename T>
class Multiset {

public:

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

    Multiset() : size(0), root(nullptr) {}

    void Insert(const T& val) {
        if (root == nullptr) {
            root = new Node{ val, 1, 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, 1, nullptr, nullptr, parent };
            parent->value > val ? parent->left = temp : parent->right = temp;
        }
        else {
            node->count++;
        }
        size++;
    }

    void Erase(const T& 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) {
            size -= node->count;
            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;
                node->count = temp->count;
                delete temp;
            }
        }
    }

    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;
    }

    void Print(Node* node) {
        if (node != nullptr) {
            Print(node->left);
            for (int i = 0; i < node->count; i++) {
                cout << node->value << " ";
            }
            Print(node->right);
        }
    }

    int Size() {
        return size;
    }

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

};

int main() {
    Multiset<int> ms;

    int arr[]{ 45, 30, 50, 27, 39, 90, 30, 15, 30, 93 };
    for (int i = 0; i < 10; i++) {
        int val = arr[i];
        cout << val << " ";
        ms.Insert(val);
    }
    cout << endl << endl;

    cout << ms.Size() << endl;

    ms.Print();

    cout << ms.Size() << endl;

    ms.Erase(30);

    ms.Print();

    cout << ms.Size() << endl;
}