#013_자료구조와 알고리즘_Map에 대한 썰

안녕하세요 삽잡이입니다.

오랜만에 포스팅을 하군요.... 

사실... 좀 방황좀 하고 아주 푹~쉬웠던 것 같습니다. 

하하... 뭐 어중간할 바에 바닥 한번 시원하게 찍고 높이 비상하는게 좋지 않겠습니까!?

다시 정신 부여잡고 시작해보도록 하지요! (사실 아직 정신 못잡은건 비밀입니다...)

지난 시간에 map이라는 자료구조를 잠시 알아봤었는데요,

이 시간에는 map이 어떻게 이루어져 있는지 알아보려고 합니다.

자... 우선, map은 'key'와 'value'를 쌍으로 하고 있는 pair를 보관하고있습니다.

pair는 STL에서 제공하는 두개의 형을 하나로 보관할 수 있는 구조체라고 해야하나?

아무튼... pair 형태로 보관하고 있습니다.

이런식으로 생겨먹었지요...

template <typename key,typename value>
struct pair
{
    key first;
    value second;    
    pair()
    {            
    }
    pair(key k,value v)
    {
        first = k;
        second = v;
    }
};    

자... 아무튼... map은 root를 중심으로 본다면,

이전 시간에 배운 이진 탐색 트리의 형태로 되어있고,

head와 tail 시점으로 본다면,

이 또한 이전 시간에 배운 연결리스트형태인 재미있는 구조를 가지고 있습니다.

이와 같이 재미있는 구조의 자료구조를 우리는 쓰레드 이진 탐색 트리라고 합니다.

위에서 언급했듯이, map의 경우 key와 value의 쌍으로 보관되어 있습니다.

또한, 쓰레드 이진 탐색 트리에는 head와 tail의 기능 또한 있습니다.

iterator 기능 또한 있어서, 순차적으로 탐방할 때에 연결리스트를 통해 

각 node들을 헤집고 다닐 수 있지요.

위의 말을 종합해보자면, 아마 map에서 node는 이렇게 생겨먹지 않았을까요?

struct node
{
    pair<key,value> data;
    node *be;
    node *af;
    node *pa;
    node *lc;
    node *rc;
    node(pair<key,value> data)
    {
        this->data = data;
        be = 0;
        af = 0;
        pa = 0;
        lc = 0;
        rc = 0;
    }
};
    
node *head;
node *tail;
node *root;
int msize;    

하지만, node에 대한 접근을 보다 편리하게 하기 위해 제공하는 것이니

전위, 중위, 후위에 대한 개념은 굳이 필요 없습니다.

아무튼... 기존에 그냥 트리의 경우 

중간에 있는 데이터들만 탐색하기 원할때에는 방법이 없다는 사실...

전체 방문은 가능하지만, 중간 특정 부분만 탐방하는 것은 불가능하기에 

탐방을 용이하게 하기 위해 만들어진 자료구조가 쓰레드 이진 탐색 트리입니다.

map은 사용하는 방법이 이전에 배웠던 다른 자료구조들과 매우 비슷합니다.

insert, erase, find와  같은 멤버 메서드 들이 똑같이 있기에 익히시는데는 무리가 없으실 것입니다.

그렇다면, 궁금한건 map이 실제로 어떤 원리에 의해 구현되었냐인데요...

우선 언급드렸듯이 연결리스트와 이진 탐색 트리 두 가지의 특징이 모두 구현되어야할 것입니다.

즉, 매달때에 이진 탐색 트리, 연결리스트 둘 다 node를 매달하야 한다는 것이죠.

연결리스트에서 매달 때에는 특정 키순대로

pair로 묶은 데이터중 key 값을 기준으로 데이터를 매달아야 할 것입니다.

지울 때에도 이진 탐색 트리와 연결리스트 둘 다 제거해야하니

또 해당 구현이 필요하겠구...

하하... 기존에 연결리스트와 트리를 알아야 map을 이해하고

어떻게 해당 메소드들이 구현되었을지 감을 잡을 수 있을 거 같습니다.

오랜만에 키보드에 손가락들을 맡기니 어색하군요...

아무튼... map이 어떻게 구현되었을지에 대해 생각해보니

생각보다 복잡하군요...

다음시간에 뵙겠습니다.

이상 삽잡이였습니다!