#include <iostream>

#include <map>

using namespace std;

template<typename T, typename S>
class Map {

public:

    struct Node {
        T key;
        S value;
        Node* left;
        Node* right;
        Node* parent;
    };

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

    Map(const Map& other) : root_(copy(other.root_, nullptr)), size_(other.size_) {}

    Map(Map&& other) : root_(other.root_), size_(other.size_) {
        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;
        }
        return *this;
    }

    void insert(const T& key, const S& val) {
        if (root_ == nullptr) {
            root_ = new Node{ key, val, 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 = new Node{ key, val, nullptr, nullptr, parent };
            parent->key > key ? parent->left = node : parent->right = node;
            size_++;
        }
    }

    void erase(const T& 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);
                node->key = temp->key;
                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_;
    }

    void clear() {
        clear(root_);
        root_ = nullptr;
        size_ = 0;
    }

    bool operator==(const Map& other) {
        return size_ == other.size_ ? compare(min(root_), min(other.root_)) : false;
    }

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

    Node* find(const T& key) {
        Node* node = root_;
        while (node != nullptr && node->key != key) {
            node = node->key > key ? node->left : node->right;
        }
        return node;
    }

    S& operator[] (const T& key) {
        return find(key)->value;
    }

    const S& operator[] (const T& key) const {
        return find(key)->value;
    }

    ~Map() {
        clear(root_);
    }

private:

    Node* copy(Node* node, Node* parent) {
        if (node == nullptr) {
            return nullptr;
        }
        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;
    }

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

    Node* next(Node* node) {
        if (node != nullptr) {
            if (node->right != nullptr) {
                return min(node->right);
            }
            Node* temp = node->parent;
            while (temp != nullptr && node->key > temp->key) {
                temp = temp->parent;
            }
            return temp;
        }
        return node;
    }

    Node* prev(Node* node) {
        if (node != nullptr) {
            if (node->left != nullptr) {
                return max(node->left);
            }
            Node* temp = node->parent;
            while (temp != nullptr && node->key < temp->key) {
                temp = temp->parent;
            }
            return temp;
        }
        return node;
    }

    bool compare(Node* a, Node* b) {
        if (a == nullptr && b == nullptr) {
            return true;
        }
        return  a->key == b->key && a->value == b->value && compare(next(a), next(b));
    }

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

    Node* root_;
    int size_;
};


int main() {

    setlocale(LC_ALL, "ru");

    Map<string, string> book;

    book.insert("Оля", "+71111111111");
    book.insert("Гена", "+71111114444");
    book.insert("Вася", "+71111115555");
    book.insert("Аня", "+71111116666");

    book.print();

    Map<string, string> book2(book);

    cout << book2["Гена"] << endl;

    book2["Гена"] = "+71111117777";

    book2.print();

    cout << (book == book2) << endl;

    cout << (book != book2) << endl;

}