STL - 25 (hash_map - 6)

1. map의 자료구조

• map의 자료구조는 '트리(tree)'이다.
  (정확하게 말하면 트리 자료구조 중의 하나인 '레드-블랙트리(Red-Black-tree)'이다.
• 트리는 한글로 '나무이다. 나무는 뿌리에서 시작하여 여러 갈래의 가지가 있고, 가지의 끝에는 나무 잎이 있다. 트리 자료구조도 이와 같은 형태를 가지고 있어서 루트(root), 리프(leaf)라는 용어를 사용한다.
  
  

2. 트리 자료구조의 특징

• 트리는 노드를 균형 있게 가지는 것이 성능에 유리하기 때문에 기본 트리에서 변형된 B-트리, B+트리, R-트리, 레드 블랙 트리, AVL트리 등 다양한 종류의 트리 자료구조가 있다.
• 균형을 이룬 트리는 정해진 방식에 따라서 분류하여 저장하기 때문에 시퀀스(일렬로)하게 자료를 저장하는 연결리스트에 비해서 검색이 빠르다. 그렇지만 정해진 규칙에 따라서 자료를 삽입, 삭제 해야 되기 때문에 삽입과 삭제가 간단하지 않으며 구현이 복잡하다.
  
  

3. map을 언제사용해야 할까?

• map은 많은 자료를 정렬하여 저장하고 있고 빠른 검색을 필요로 할 때 자주 사용한다. 많은 자료를 빠르게 검색한다고 하는 부분은 앞 글에서 설명한 hash_map과 비슷하다. 그러나 hash_map과 크게 다른 부분이 있다. map은 자료를 저장할 때 내부에서 자동으로 정렬을 하고, hash_map은 정렬하지 않는다는 것이다. 정렬이 필요하지 않는 곳에서 map을 사용하는 것은 불필요한 낭비이다.
  
  

map은 다음 조건일 때 사용하는 것이 좋다!

1. 정렬해야 한다.
2. 많은 자료를 저장하고, 검색이 빨라야 한다.
3. 빈번하게 삽입, 삭제하지 않는다.