RED BLACK TREE

RED BLACK TREE가 등장한 이유

#pragma once

#include <assert.h>
#include <functional>

enum NODE_COLOR
{
   NC_RED,
   NC_BLACK
};

template <typename Key, typename Value>
struct _tagRBBPair
{
   Key      first;
   Value   second;
};

template <typename Key, typename Value>
class CRBBTreeNode
{
   template <typename Key, typename Value>
   friend class CRBBTree;
   template <typename Key, typename Value>
   friend class CRBBTreeIterator;

private:
   CRBBTreeNode()
   {
      m_pParent = m_pLeft = m_pRight = nullptr;
      m_pNext = m_pPrev = nullptr;
      m_eColor = NC_RED;
   }

   ~CRBBTreeNode()
   {
   }

private:
   CRBBTreeNode<Key, Value>*   m_pParent;
   CRBBTreeNode<Key, Value>*   m_pLeft;
   CRBBTreeNode<Key, Value>*   m_pRight;
   CRBBTreeNode<Key, Value>*   m_pNext;
   CRBBTreeNode<Key, Value>*   m_pPrev;

public:
   Key      first;
   Value   second;
   NODE_COLOR   m_eColor;
};


template <typename Key, typename Value>
class CRBBTreeIterator
{
   template <typename Key, typename Value>
   friend class CRBBTree;

public:
   CRBBTreeIterator()
   {
      m_pNode = nullptr;
   }

   ~CRBBTreeIterator()
   {
   }

private:
   CRBBTreeNode<Key, Value>*   m_pNode;

public:
   bool operator == (const CRBBTreeIterator<Key, Value>& iter)
   {
      return m_pNode == iter.m_pNode;
   }

   bool operator != (const CRBBTreeIterator<Key, Value>& iter)
   {
      return m_pNode != iter.m_pNode;
   }

   CRBBTreeIterator<Key, Value>& operator ++ ()
   {
      m_pNode = m_pNode->m_pNext;
      return *this;
   }

   CRBBTreeIterator<Key, Value> operator ++ (int)
   {
      m_pNode = m_pNode->m_pNext;
      return *this;
   }

   CRBBTreeIterator<Key, Value>& operator -- ()
   {
      m_pNode = m_pNode->m_pPrev;
      return *this;
   }

   CRBBTreeIterator<Key, Value> operator -- (int)
   {
      m_pNode = m_pNode->m_pPrev;
      return *this;
   }

   CRBBTreeNode<Key, Value>* operator -> ()
   {
      return m_pNode;
   }
};

template <typename Key, typename Value>
class CRBBTree
{
public:
   CRBBTree()
   {
      m_pRoot = nullptr;
      m_pBegin = new NODE;
      m_pEnd = new NODE;

      m_pBegin->m_pNext = m_pEnd;
      m_pEnd->m_pParent = m_pBegin;
      m_iSize = 0;

      Nil = new NODE;
      Nil->m_eColor = NC_BLACK;
   }

   ~CRBBTree()
   {
      clear();
      delete   m_pBegin;
      delete   m_pEnd;
      delete   Nil;
   }

private:
   typedef CRBBTreeNode<Key, Value>   NODE;
   typedef CRBBTreeNode<Key, Value>*   PNODE;

public:
   typedef _tagRBBPair<Key, Value>   Pair;
   typedef CRBBTreeIterator<Key, Value>   iterator;

private:
   PNODE   m_pRoot;
   PNODE   m_pBegin;
   PNODE   m_pEnd;
   PNODE   Nil;
   int      m_iSize;
   function<void(const Key&, const Value&, NODE_COLOR)>   m_OutputFunc;

public:
   void SetOutputFunc(void(*pFunc)(const Key&, const Value&, NODE_COLOR))
   {
      m_OutputFunc = bind(pFunc, placeholders::_1, placeholders::_2, placeholders::_3);
   }

   template <typename T>
   void SetOutputFunc(T* pObj, void(T::*pFunc)(const Key&, const Value&, NODE_COLOR))
   {
      m_OutputFunc = bind(pFunc, pObj, placeholders::_1, placeholders::_2, placeholders::_3);
   }

public:
   void insert(const Pair& pair)
   {
      if (!m_pRoot)
      {
         m_pRoot = new NODE;

         m_pRoot->first = pair.first;
         m_pRoot->second = pair.second;

         m_pBegin->m_pNext = m_pRoot;
         m_pRoot->m_pPrev = m_pBegin;

         m_pRoot->m_pNext = m_pEnd;
         m_pEnd->m_pPrev = m_pRoot;

         // 2번 규칙 : 루트노드는 검은색이어야 한다. 그렇기 때문에 검은색으로 칠하면 끝난다.
         m_pRoot->m_eColor = NC_BLACK;

         m_pRoot->m_pLeft = Nil;
         m_pRoot->m_pRight = Nil;
      }

      else
      {
         PNODE pNewNode = insert(pair, m_pRoot);

         insertBalance(pNewNode);
      }

      m_pRoot->m_eColor = NC_BLACK;

      ++m_iSize;
   }

   int size()   const
   {
      return m_iSize;
   }

   bool empty()   const
   {
      return m_iSize == 0;
   }

   iterator begin()   const
   {
      iterator   iter;
      iter.m_pNode = m_pBegin->m_pNext;
      return iter;
   }

   iterator end()   const
   {
      iterator   iter;
      iter.m_pNode = m_pEnd;
      return iter;
   }

   iterator find(const Key& key)   const
   {
      if (empty())
         return end();

      PNODE   pNode = find(key, m_pRoot);

      if (!pNode)
         return end();

      iterator   iter;
      iter.m_pNode = pNode;

      return iter;
   }

   iterator erase(iterator& iter)
   {
      if (empty() || iter == end())
         return end();

      // 리프노드일 경우 그냥 지우면 된다.
      if (iter.m_pNode->m_pLeft == Nil && iter.m_pNode->m_pRight == Nil)
      {
         // 리프노드의 부모가 없다는 것은 Root 노드임을 의미한다.
         if (!iter.m_pNode->m_pParent)
         {
            m_pRoot = nullptr;
            delete   iter.m_pNode;
            --m_iSize;
            return end();
         }

         else
         {
            // 이 노드의 부모로부터 연결을 끊어준다.
            if (iter.m_pNode->m_pParent->m_pLeft == iter.m_pNode)
            {
               iter.m_pNode->m_pParent->m_pLeft = Nil;
            }

            else
            {
               iter.m_pNode->m_pParent->m_pRight = Nil;
            }

            PNODE   pNext = iter.m_pNode->m_pNext;
            PNODE   pPrev = iter.m_pNode->m_pPrev;

            pNext->m_pPrev = pPrev;
            pPrev->m_pNext = pNext;

            delete   iter.m_pNode;
            --m_iSize;
            iter.m_pNode = pNext;
            return iter;
         }
      }

      // 아래 bool 변수를 이용해서 지울 노드를 왼쪽 노드에서 찾아왔는지 오른쪽 노드에서 찾아왔는지를
      // 알 수 있다.
      bool   bLeft = false;
      PNODE   pDeleteNode = nullptr;
      
      // 왼쪽 노드가 있을 경우 왼쪽 노드의 가장 큰 노드를 얻어온다.
      if (iter.m_pNode->m_pLeft != Nil)
      {
         bLeft = true;
         pDeleteNode = FindLeftMax(iter.m_pNode->m_pLeft);
      }

      else
         pDeleteNode = FindRightMin(iter.m_pNode->m_pRight);

      // 현재 지울 노드의 Color를 미리 받아둔다.
      NODE_COLOR   eDeleteColor = iter.m_pNode->m_eColor;

      // 현재 노드의 값을 지울 노드로 대체한다.
      iter.m_pNode->first = pDeleteNode->first;
      iter.m_pNode->second = pDeleteNode->second;
      // 색상을 변경한다.
      iter.m_pNode->m_eColor = pDeleteNode->m_eColor;

      iterator   iter1;
      iter1.m_pNode = iter.m_pNode;

      // 왼쪽에서 얻어왔을 경우 next를 받아와서 지울 노드의 다음 노드를 가진 iterator를 리턴해주어야 한다.
      if (bLeft)
         iter1.m_pNode = iter.m_pNode->m_pNext;

      // 왼쪽에서 가장 큰 노드를 얻어온 경우 지울 노드의 왼쪽 자식이 있을 수도 있고
      // 오른쪽에서 가장 작은 노드를 얻어온 경우 지울 노드의 오른쪽 자식이 있을 수도 있다.
      // 그렇기 때문에 자식이 있는지를 판단하여 얻어오도록 한다.
      PNODE   pDeleteChild = nullptr;

      if (pDeleteNode->m_pLeft != Nil)
         pDeleteChild = pDeleteNode->m_pLeft;

      else
         pDeleteChild = pDeleteNode->m_pRight;

      // 지울 노드의 자식의 부모를 지울노드의 부모로 지정한다.
      pDeleteChild->m_pParent = pDeleteNode->m_pParent;

      // 지울 노드가 부모의 왼쪽인지 오른쪽인지 판단하여 자식을 붙여준다.
      if (pDeleteNode == pDeleteNode->m_pParent->m_pLeft)
         pDeleteNode->m_pParent->m_pLeft = pDeleteChild;

      else
         pDeleteNode->m_pParent->m_pRight = pDeleteChild;

      // 삭제할 노드가 검은 색일 경우 이중흑색노드가 된다.
      if (eDeleteColor == NC_BLACK)
         erase(iter.m_pNode);

      PNODE   pPrev = pDeleteNode->m_pPrev;
      PNODE   pNext = pDeleteNode->m_pNext;

      pPrev->m_pNext = pNext;
      pNext->m_pPrev = pPrev;

      delete   pDeleteNode;
      --m_iSize;

      return iter1;
   }

   void clear()
   {
      clear(m_pRoot);

      m_pRoot = nullptr;
      m_iSize = 0;
      m_pBegin->m_pNext = m_pEnd;
      m_pEnd->m_pPrev = m_pBegin;
   }

   void PreOrder()
   {
      _PreOrder(m_pRoot);
   }

   void InOrder()
   {
      _InOrder(m_pRoot);
   }

   void PostOrder()
   {
      _PostOrder(m_pRoot);
   }

private:
   void _PreOrder(PNODE pNode)
   {
      if (pNode == nullptr || pNode == Nil)
         return;

      m_OutputFunc(pNode->first, pNode->second, pNode->m_eColor);
      _PreOrder(pNode->m_pLeft);
      _PreOrder(pNode->m_pRight);
   }

   void _InOrder(PNODE pNode)
   {
      if (pNode == nullptr || pNode == Nil)
         return;

      _InOrder(pNode->m_pLeft);
      m_OutputFunc(pNode->first, pNode->second, pNode->m_eColor);
      _InOrder(pNode->m_pRight);
   }

   void _PostOrder(PNODE pNode)
   {
      if (pNode == nullptr || pNode == Nil)
         return;

      _PostOrder(pNode->m_pLeft);
      _PostOrder(pNode->m_pRight);
      m_OutputFunc(pNode->first, pNode->second, pNode->m_eColor);
   }

private:
   PNODE insert(const Pair& pair, PNODE pNode)
   {
      if (!pNode || pNode == Nil)
         return nullptr;

      // 현재 노드의 키보다 추가할 키가 더 작을 경우 왼쪽을 찾아봐야 한다.
      if (pNode->first > pair.first)
      {
         // 왼쪽 자식노드가 없을때는 왼쪽에 추가한다.
         if (!pNode->m_pLeft || pNode->m_pLeft == Nil)
         {
            PNODE   pNewNode = new NODE;
            pNewNode->first = pair.first;
            pNewNode->second = pair.second;

            pNewNode->m_pParent = pNode;
            pNode->m_pLeft = pNewNode;

            PNODE   pPrev = pNode->m_pPrev;

            pPrev->m_pNext = pNewNode;
            pNewNode->m_pPrev = pPrev;

            pNewNode->m_pNext = pNode;
            pNode->m_pPrev = pNewNode;

            pNewNode->m_pLeft = Nil;
            pNewNode->m_pRight = Nil;

            return pNewNode;
         }

         else
         {
            return insert(pair, pNode->m_pLeft);
         }
      }

      if (!pNode->m_pRight || pNode->m_pRight == Nil)
      {
         PNODE   pNewNode = new NODE;
         pNewNode->first = pair.first;
         pNewNode->second = pair.second;

         pNewNode->m_pParent = pNode;
         pNode->m_pRight = pNewNode;

         PNODE   pNext = pNode->m_pNext;

         pNext->m_pPrev = pNewNode;
         pNewNode->m_pNext = pNext;

         pNewNode->m_pPrev = pNode;
         pNode->m_pNext = pNewNode;

         pNewNode->m_pLeft = Nil;
         pNewNode->m_pRight = Nil;

         return pNewNode;
      }

      return insert(pair, pNode->m_pRight);
   }

   PNODE find(const Key& key, PNODE pNode)   const
   {
      if (!pNode || pNode == Nil)
         return nullptr;

      if (pNode->first == key)
         return pNode;

      else if (pNode->first > key)
         return find(key, pNode->m_pLeft);

      return find(key, pNode->m_pRight);
   }
   
   PNODE FindLeftMax(PNODE pNode)   const
   {
      if (!pNode->m_pRight || pNode->m_pLeft == Nil)
         return pNode;

      return FindLeftMax(pNode->m_pRight);
   }

   PNODE FindRightMin(PNODE pNode)   const
   {
      if (!pNode->m_pLeft || pNode->m_pLeft == Nil)
         return pNode;

      return FindRightMin(pNode->m_pLeft);
   }

   void clear(PNODE pNode)
   {
      if (!pNode || pNode == Nil)
         return;

      clear(pNode->m_pLeft);
      clear(pNode->m_pRight);
      delete   pNode;
   }

   // 회전 함수.
   void RotationLeft(PNODE pNode)
   {
      // 현재 노드의 오른쪽 노드를 얻어온다.
      PNODE   pRight = pNode->m_pRight;

      // 오른쪽 노드의 왼쪽 노드를 얻어온다.
      PNODE   pLeftChild = pRight->m_pLeft;

      // 현재 노드의 부모를 얻어온다.
      PNODE   pParent = pNode->m_pParent;

      // 만약 부모가 있을 경우
      if (pParent)
      {
         // 현재 노드가 부모의 왼쪽 자식인지 오른쪽 자식인지를 판단한다.
         if (pParent->m_pLeft == pNode)
         {
            // 부모의 왼쪽 자식으로 현재 노드의 오른쪽 자식을 준다.
            // 좌회전을 해야 하기 때문에 오른쪽 자식이 현재 노드가 있는 곳으로
            // 올라오기 때문이다.
            pParent->m_pLeft = pRight;
            pRight->m_pParent = pParent;
         }

         else
         {
            // 오른쪽에 연결한다.
            pParent->m_pRight = pRight;
            pRight->m_pParent = pParent;
         }
      }

      else
      {
         // 만약 현재 노드의 부모가 없다면 루트노드라는 의미이다.
         // 루트노드를 교체해 주어야 한다.
         m_pRoot = pRight;
         pRight->m_pParent = nullptr;
      }

      // 현재 노드의 오른쪽 자식의 왼쪽 자식을 현재 노드의 오른쪽 자식으로 붙여준다.
      pNode->m_pRight = pLeftChild;

      // pLeftChild가 있을 경우 부모를 pNode로 지정한다.
      if (pLeftChild && pLeftChild != Nil)
         pLeftChild->m_pParent = pNode;

      // 마지막으로 오른쪽노드의 왼쪽 자식으로 현재 노드를 붙여준다.
      pRight->m_pLeft = pNode;
      pNode->m_pParent = pRight;
   }

   void RotationRight(PNODE pNode)
   {
      // 현재 노드의 왼쪽 노드를 얻어온다.
      PNODE   pLeft = pNode->m_pLeft;

      // 왼쪽 노드의 오른쪽 노드를 얻어온다.
      PNODE   pRightChild = pLeft->m_pRight;

      // 현재 노드의 부모를 얻어온다.
      PNODE   pParent = pNode->m_pParent;

      // 만약 부모가 있을 경우
      if (pParent)
      {
         // 현재 노드가 부모의 왼쪽 자식인지 오른쪽 자식인지를 판단한다.
         if (pParent->m_pLeft == pNode)
         {
            // 부모의 왼쪽 자식으로 현재 노드의 오른쪽 자식을 준다.
            // 좌회전을 해야 하기 때문에 오른쪽 자식이 현재 노드가 있는 곳으로
            // 올라오기 때문이다.
            pParent->m_pLeft = pLeft;
            pLeft->m_pParent = pParent;
         }

         else
         {
            // 오른쪽에 연결한다.
            pParent->m_pRight = pLeft;
            pLeft->m_pParent = pParent;
         }
      }

      else
      {
         // 만약 현재 노드의 부모가 없다면 루트노드라는 의미이다.
         // 루트노드를 교체해 주어야 한다.
         m_pRoot = pLeft;
         pLeft->m_pParent = nullptr;
      }

      // 현재 노드의 왼쪽 자식의 오른쪽 자식을 현재 노드의 왼쪽 자식으로 붙여준다.
      pNode->m_pLeft = pRightChild;

      // pRightChild가 있을 경우 부모를 pNode로 지정한다.
      if (pRightChild && pRightChild != Nil)
         pRightChild->m_pParent = pNode;

      // 마지막으로 왼쪽노드의 오른쪽 자식S으로 현재 노드를 붙여준다.
      pLeft->m_pRight = pNode;
      pNode->m_pParent = pLeft;
   }

   // 삽입처리에서 균형을 맞추기 위한 함수이다.
   void insertBalance(PNODE pNode)
   {
      if (!pNode || pNode == Nil || pNode == m_pRoot || !pNode->m_pParent->m_pParent ||
         !pNode->m_pParent)
         return;

      // 부모가 빨간색일 경우 현재 노드도 빨간색이기 때문에 규칙에 위배된다.
      else if (pNode->m_pParent->m_eColor == NC_BLACK)
         return;

      // 부모노드가 조부노드의 왼쪽일 경우
      if (pNode->m_pParent == pNode->m_pParent->m_pParent->m_pLeft)
      {
         PNODE   pUncle = nullptr;

         // 부모가 조부의 왼쪽 자식일 경우 삼촌은 조부의 오른쪽 자식이 된다.
         if (pNode->m_pParent == pNode->m_pParent->m_pParent->m_pLeft)
            pUncle = pNode->m_pParent->m_pParent->m_pRight;

         else
            pUncle = pNode->m_pParent->m_pParent->m_pLeft;

         // 1. 삼촌이 빨간색일 경우
         if (pUncle->m_eColor == NC_RED)
         {
            // 부모노드와 삼촌노드를 검은색으로 칠한다.
            pNode->m_pParent->m_eColor = NC_BLACK;
            pUncle->m_eColor = NC_BLACK;
            pNode->m_pParent->m_pParent->m_eColor = NC_RED;

            // 조부노드를 넣어주어서 부모로 가면서 규칙이 안맞는 경우를 찾아서 규칙을 맞춰준다.
            insertBalance(pNode->m_pParent->m_pParent);
         }

         // 2. 삼촌이 검은색일 경우
         else
         {
            // 현재 노드가 부모의 오른쪽 자식일 경우
            if (pNode == pNode->m_pParent->m_pRight)
            {
               // 부모노드를 좌회전하여 빨간색 노드가 왼쪽 자식이 되도록 변환한다.
               RotationLeft(pNode->m_pParent);

               // 현재 노드의 왼쪽 자식이 이제 기준노드가 된다.
               pNode = pNode->m_pLeft;
            }

            // 부모의 왼쪽 자식일 경우
            // 부모를 검은색, 조부를 빨간색으로 칠한다.
            pNode->m_pParent->m_eColor = NC_BLACK;
            pNode->m_pParent->m_pParent->m_eColor = NC_RED;
            // 조부노드를 오른쪽으로 회전한다.
            RotationRight(pNode->m_pParent->m_pParent);
         }
      }

      // 부모노드가 조부노드의 오른쪽 노드일 경우
      else
      {
         PNODE   pUncle = nullptr;

         // 부모가 조부의 왼쪽 자식일 경우 삼촌은 조부의 오른쪽 자식이 된다.
         if (pNode->m_pParent == pNode->m_pParent->m_pParent->m_pLeft)
            pUncle = pNode->m_pParent->m_pParent->m_pRight;

         else
            pUncle = pNode->m_pParent->m_pParent->m_pLeft;

         // 1. 삼촌이 빨간색일 경우
         if (pUncle->m_eColor == NC_RED)
         {
            // 부모노드와 삼촌노드를 검은색으로 칠한다.
            pNode->m_pParent->m_eColor = NC_BLACK;
            pUncle->m_eColor = NC_BLACK;
            pNode->m_pParent->m_pParent->m_eColor = NC_RED;

            // 조부노드를 넣어주어서 부모로 가면서 규칙이 안맞는 경우를 찾아서 규칙을 맞춰준다.
            insertBalance(pNode->m_pParent->m_pParent);
         }

         // 2. 삼촌이 검은색일 경우
         else
         {
            // 현재 노드가 부모의 왼쪽 자식일 경우
            if (pNode == pNode->m_pParent->m_pLeft)
            {
               // 부모노드를 우회전하여 빨간색 노드가 오른쪽 자식이 되도록 변환한다.
               RotationRight(pNode->m_pParent);

               // 현재 노드의 왼쪽 자식이 이제 기준노드가 된다.
               pNode = pNode->m_pRight;
            }

            // 부모의 오른쪽 자식일 경우
            // 부모를 검은색, 조부를 빨간색으로 칠한다.
            pNode->m_pParent->m_eColor = NC_BLACK;
            pNode->m_pParent->m_pParent->m_eColor = NC_RED;
            // 조부노드를 왼쪽으로 회전한다.
            RotationLeft(pNode->m_pParent->m_pParent);
         }
      }
   }

   void erase(PNODE pNode)
   {
      PNODE   pSibling = nullptr;

      // Root노드일 경우 탐색을 종료한다. 노드가 빨간색이어도 탐색을 종료한다.
      while (pNode != m_pRoot && pNode->m_eColor == NC_BLACK)
      {
         // 이중 흑색노드가 부모의 왼쪽 자식일 경우
         if (pNode == pNode->m_pParent->m_pLeft)
         {
            // 이중흑색노드의 형제가 RED인 경우
            // 형제를 검은색, 부모를 빨간색으로 칠한다.
            // 부모노드를 기준으로 좌회전한다.
            // 형제노드(부모의 오른쪽 자식)을 얻어온다.
            pSibling = pNode->m_pParent->m_pRight;

            // 1. 이중흑색노드의 형제가 RED인 경우
            if (pSibling->m_eColor == NC_RED)
            {
               // 형제를 검은색, 부모를 빨간색으로 칠한다.
               pSibling->m_eColor = NC_BLACK;
               pNode->m_pParent->m_eColor = NC_RED;

               // 부모를 기준으로 좌회전한다.
               RotationLeft(pNode->m_pParent);

               // 형제가 바뀌므로 부모의 오른쪽 자식을
               // 다시 얻어온다.
               pSibling = pNode->m_pParent->m_pRight;
            }

            // 형제가 RED인 경우에는 위에서 case change를 통해
            // 형제가 BLACK인 경우로 바꾼 후에 아래의 case들에
            // 따라 처리한다.
            // 2. 이중흑색노드의 형제가 BLACK이고 형제의 양쪽자식
            // 모두 BLACK인 경우
            if (pSibling->m_pLeft->m_eColor == NC_BLACK &&
               pSibling->m_pRight->m_eColor == NC_BLACK)
            {
               // 형제를 빨간색으로 칠한다.
               if (pSibling != Nil)
                  pSibling->m_eColor = NC_RED;

               // 이중흑색노드의 검은색 1개를 부모에게 전달한다.
               // 만약 부모가 빨간색이라면 검은색으로 칠하고 끝난다.
               // 하지만 부모가 검은색이라면 이중흑색노드 체크를 해야한다.
               if (pNode->m_pParent->m_eColor == NC_RED)
               {
                  pNode->m_pParent->m_eColor = NC_BLACK;
                  break;
               }

               // 부모가 검은색일 경우 부모를 기준으로 다시
               // 체크를 시작한다.
               pNode = pNode->m_pParent;
               continue;
            }

            // 3. 이중흑색노드의 형제가 검은색이고 형제의 왼쪽자식
            // 이 빨간색인 경우
            else if (pSibling->m_pLeft->m_eColor == NC_RED)
            {
               // 형제를 빨간색으로 칠한다.
               if (pSibling != Nil)
                  pSibling->m_eColor = NC_RED;

               // 형제의 왼쪽 자식을 검은색으로 칠한다.
               pSibling->m_pLeft->m_eColor = NC_BLACK;

               // 형제노드를 기준으로 우회전한다.
               RotationRight(pSibling);
            }

            // 이중흑색노드의 형제가 검은색이고 형제의 오른쪽 자식이
            // 빨간색일 경우
            else if (pSibling->m_pRight->m_eColor == NC_RED)
            {
               // 부모의 색을 형제에게 넘긴다.
               if (pSibling != Nil)
                  pSibling->m_eColor = pNode->m_pParent->m_eColor;

               // 부모노드와 형제노드의 오른쪽 자식을 검은색으로
               // 칠한다.
               pNode->m_pParent->m_eColor = NC_BLACK;
               pSibling->m_pRight->m_eColor = NC_BLACK;

               // 부모노드 기준으로 좌회전한다.
               RotationLeft(pNode->m_pParent);
            }

            break;
         }

         // 이중 흑색노드가 부모의 오른쪽 자식일 경우
         else
         {
            // 형제노드(부모의 왼쪽 자식)을 얻어온다.
            pSibling = pNode->m_pParent->m_pLeft;

            // 1. 이중흑색노드의 형제가 RED인 경우
            if (pSibling->m_eColor == NC_RED)
            {
               // 형제를 검은색, 부모를 빨간색으로 칠한다.
               pSibling->m_eColor = NC_BLACK;
               pNode->m_pParent->m_eColor = NC_RED;

               // 부모를 기준으로 우회전한다.
               RotationRight(pNode->m_pParent);

               // 형제가 바뀌므로 부모의 왼쪽 자식을 다시 얻어온다.
               pSibling = pNode->m_pParent->m_pLeft;
            }

            // 형제가 RED인 경우에는 위에서 case change를 통해
            // 형제가 BLACK인 경우로 바꾼 후에 아래의 case들에
            // 따라 처리한다.
            // 2. 이중흑색노드의 형제가 BLACK이고 형제의 양쪽자식
            // 모두 BLACK인 경우
            if (pSibling->m_pLeft->m_eColor == NC_BLACK &&
               pSibling->m_pRight->m_eColor == NC_BLACK)
            {
               // 형제를 빨간색으로 칠한다.
               if (pSibling != Nil)
                  pSibling->m_eColor = NC_RED;

               // 이중흑색노드의 검은색 1개를 부모에게 전달한다.
               // 만약 부모가 빨간색이라면 검은색으로 칠하고 끝난다.
               // 하지만 부모가 검은색이라면 이중흑색노드 체크를 해야한다.
               if (pNode->m_pParent->m_eColor == NC_RED)
               {
                  pNode->m_pParent->m_eColor = NC_BLACK;
                  break;
               }

               // 부모가 검은색일 경우 부모를 기준으로 다시
               // 체크를 시작한다.
               pNode = pNode->m_pParent;
               continue;
            }

            // 3. 이중흑색노드의 형제가 검은색이고 형제의 오른쪽자식
            // 이 빨간색인 경우
            else if (pSibling->m_pRight->m_eColor == NC_RED)
            {
               // 형제를 빨간색으로 칠한다.
               if (pSibling != Nil)
                  pSibling->m_eColor = NC_RED;

               // 형제의 오른쪽 자식을 검은색으로 칠한다.
               pSibling->m_pRight->m_eColor = NC_BLACK;

               // 형제노드를 기준으로 좌회전한다.
               RotationLeft(pSibling);
            }

            // 이중흑색노드의 형제가 검은색이고 형제의 왼쪽 자식이
            // 빨간색일 경우
            else if (pSibling->m_pLeft->m_eColor == NC_RED)
            {
               // 부모의 색을 형제에게 넘긴다.
               if (pSibling != Nil)
                  pSibling->m_eColor = pNode->m_pParent->m_eColor;

               // 부모노드와 형제노드의 왼쪽 자식을 검은색으로
               // 칠한다.
               pNode->m_pParent->m_eColor = NC_BLACK;
               pSibling->m_pLeft->m_eColor = NC_BLACK;

               // 부모노드 기준으로 좌회전한다.
               RotationRight(pNode->m_pParent);
            }

            break;
         }
      }
   }

public:
   static Pair make_pair(const Key& key, const Value& value)
   {
      Pair   pair;
      pair.first = key;
      pair.second = value;
      return pair;
   }
};