#include <iostream>
#include <string>

using namespace std;

template <typename K, typename V>
class Map {

public:

    struct Node {
        K key{};
        V value{};
        Node* left = nullptr;
        Node* right = nullptr;
        Node* parent = nullptr;
    };

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

    Map(const Map& other) : size(other.size), root(Copy(other.root, nullptr)) {}

    Map(Map&& other) : size(other.size), root(other.root) {
        other.size = 0;
        other.root = nullptr;
    }

    Map& operator=(const Map& other) {
        if (this != &other) {
            Clear();
            size = other.size;
            root = Copy(other.root, nullptr);
        }
        return *this;
    }

    Map& operator=(Map&& other) {
        if (this != &other) {
            Clear();
            size = other.size;
            root = other.root;
            other.root = nullptr;
            other.size = 0;
        }
        return *this;
    }

    void Insert(const K& key, const V& value) {
        if (root == nullptr) {
            root = new Node{ key, value, nullptr, nullptr, nullptr };
            size++;
            return;
        }
        Node* parent = nullptr;
        Node* node = root;
        while (node != nullptr && node->key != key) {
            parent = node;
            node = node->key > key ? node->left : node->right;
        }
        if (node == nullptr) {
            Node* temp = new Node{ key, value, nullptr, nullptr, parent };

            parent->key > key ? parent->left = temp : parent->right = temp;
            size++;
        }
    }

    void Erase(const K& key) {
        Node* parent = nullptr;
        Node* node = root;
        while (node != nullptr && node->key != key) {
            parent = node;
            node = node->key > key ? 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->key = temp->key;
                node->value = temp->value;
                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;
    }

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

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

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

    Node* Prev(Node* node) {
        if (node) {
            if (node->left) {
                return Max(node->right);
            }
            Node* parent = node->parent;
            while (parent != nullptr && parent->key > node->key) {
                parent = parent->parent;
            }
            return parent;
        }
    }

    Node* Begin() {
        return Min(root);
    }

    Node* End() {
        return Max(root);
    }

    void Clear() {
        Clear(root);
        root = nullptr;
        size = 0;
    }

    void Clear(Node* node) {
        if (node != nullptr) {
            Clear(node->left);
            Clear(node->right);
            delete node;
        }
    }

    int Size() {
        return size;
    }

    Node* Copy(Node* node, Node* parent) {
        if (node == nullptr) {
            return node;
        }
        Node* temp = new Node{ node->key, node->value, nullptr, nullptr, parent };
        temp->left = Copy(node->left, temp);
        temp->right = Copy(node->right, temp);
        return temp;
    }

    bool Compare(Node* a, Node* b) {
        Node* left = Min(a);
        Node* right = Min(b);
        while (left != nullptr && right != nullptr) {
            if (left->key != right->key) {
                return false;
            }
            left = Next(left);
            right = Next(right);
        }
        if (left == nullptr && right != nullptr || right == nullptr && left != nullptr) {
            return false;
        }
        return true;
    }

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

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

    bool operator==(const Map& other) {
        if (size != other.size) {
            return false;
        }
        return Compare(root, other.root);
    }

    bool operator!=(const Map& other) {
        return !(*this == other);
    }

    ~Map() {
        Clear();
    }

private:
    int size;
    Node* root;
};


int main() {
    Map<string, string> book;
    book.Insert("Gena", "111111");
    book.Insert("Julia", "111122");
    book.Insert("Olya", "111133");
    book.Insert("Ivan", "111144");
    book.Insert("Vasya", "111155");
    book.Print();

    book.Erase("Gena");
    book.Print();

    cout << book.Count("Olya") << endl;
    cout << book.Count("Gena") << endl;

    auto first = book.Begin();
    cout << first->key << ": " << first->value  << endl;

    auto last = book.End();
    cout << last->key << ": " << last->value  << endl;

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

    Map<string, string> book2;
    book2 = book;
    cout << "book2: " << endl;
    book2.Print();

    Map<string, string> book3;
    book3 = move(book2);
    book3.Insert("Egor", "121212");
    cout << "book3: " << endl;
    book3.Print();

    cout << "book2: " << endl;
    book2.Print();

    cout << boolalpha;
    cout << (book == book3) << endl;
    cout << (book != book3) << endl;
}