#include <memory>

template<typename Key, typename Value>
struct Node
{
    using NodeType = Node<Key, Value>;
    Key key;
    Value value;

    std::unique_ptr<NodeType> left, right;

    bool operator<(NodeType& other) const noexcept
    {
        return key < other.key;
    }
};

template<typename Key, typename Value>
class Tree
{
private:
    std::unique_ptr<Node<Key, Value>> root;
    using NodeType = Node<Key, Value>;

public:
    // Questi 4 funzionano grazie ad unique_ptr
    Tree() = default;
    Tree(Tree&&) = default;
    Tree& operator=(Tree&&) = default;
    ~Tree() = default;

    // Se vuoi anche i costruttori di copia dovrai definirli tu
    Tree(Tree const &);
    Tree& operator=(Tree const &);


    // Uso 'auto' in quanto il tipo che ritorna una di queste funzioni
    // è molto soggettivo:
    // A) Iteratore
    // B) Reference a *this
    // C) Booleano
    // D) Altro

    auto insert(NodeType const &);
    auto emplace(Key&&, Value&&);

    auto remove(NodeType const &);
    auto remove(Key&&);

    auto find(NodeType const &);
    auto find(Key&&);
};