map 구현

template<typename T, typename U>
class Pair
{
public:
    Pair(T& t, U& u)
        : frist(t)
        , second(u)
    {

    }

    Pair()
        : frist{}
        , second{}
    {

    }

public:
    T frist;
    U second;
};

template<typename T, typename U>
Pair<T, U> Make_Pair(T& t, U& u)
{
    return Pair<T, U>{t, u};
}

template<typename T, typename U>
class Map
{
public:
    Map()
        : RootNode(nullptr)
    {
    }

    ~Map()
    {
        PostOrderDelete(RootNode);
    }

private:
    class Node
    {
        friend Map;

        Pair<T, U> CurPair;

        Node* Parent = nullptr;
        Node* Left = nullptr;
        Node* Right = nullptr;

    private:
        bool Insert(const Pair<T, U>& _Pair)
        {
            if (_Pair.frist < CurPair.frist)
            {
                if (nullptr == Left)
                {
                    Left = new Node(); 
                    Left->CurPair = _Pair;
                    Left->Parent = this;

                    return true;
                }

                Left->Insert(_Pair);
            }

            else
            {
                if (nullptr == Right)
                {
                    Right = new Node();
                    Right->CurPair = _Pair;
                    Right->Parent = this;

                    return true;
                }

                Right->Insert(_Pair);
            }

            return false;
        }

        U Find(T& _t)
        {
            if (_t == CurPair.frist)
            {
                return CurPair.second;
            }

            if (_t < CurPair.frist)
            {
                if (nullptr == Left)
                {
                    return NULL;
                }

                return Left->Find(_t);
            }
            
            else
            {
                if (nullptr == Right)
                {
                    return NULL;
                }

                return Right->Find(_t);
            }

            return NULL;
        }
    };

public:
    bool Insert(const Pair<T,U>& _Pair)
    {
        if (nullptr == RootNode)
        {
            RootNode = new Node();
            RootNode->CurPair = _Pair;
            return true;
        }
        
        return RootNode->Insert(_Pair);
    }

    U Find(T& _t)
    {
        return RootNode->Find(_t);
    }

    void PrevOrder(Node* _Node)
    {
        if (nullptr != _Node)
        {
            std::cout << _Node->CurPair.frist << std::endl;
            PrevOrder(_Node->Left);
            PrevOrder(_Node->Right);
        }
    }
    void InOrder(Node* _Node)
    {
        if (nullptr != _Node)
        {
            InOrder(_Node->Left);
            std::cout << _Node->CurPair.frist << std::endl;
            InOrder(_Node->Right);
        }

    }
    void PostOrder(Node* _Node)
    {
        if (nullptr != _Node)
        {
            PostOrder(_Node->Left);
            PostOrder(_Node->Right);
            std::cout << _Node->CurPair.frist << std::endl;
        }
    }

    void PostOrderDelete(Node* _Node)
    {
        if (nullptr != _Node)
        {
            PostOrderDelete(_Node->Left);
            PostOrderDelete(_Node->Right);

            delete _Node;
            _Node = nullptr;
        }
    }

public:
    Node* RootNode;
};

int main()
{
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

    int a = 5;
    int b = 10;
    int c = 1;

    std::string str = "abc";
    std::string str1 = "abc1";
    std::string str2 = "abc2";

    Pair<int, std::string> pair = Make_Pair<int, std::string>(a, str);
    Pair<int, std::string> pair1 = Make_Pair<int, std::string>(b, str1);
    Pair<int, std::string> pair2 = Make_Pair<int, std::string>(c, str2);

    Map<int, std::string> map{};
    map.Insert(pair);
    map.Insert(pair1);
    map.Insert(pair2);

    std::string find = map.Find(b);

    map.InOrder(map.RootNode);
}