TreeMap

TreeMap

---

TreeMap은 이진트리를 기반으로 한  Map  컬렉션입니다. 같은 Tree 구조로 이루어진 TreeSet 과의 차이점은 TreeSet 은 그냥 값만 저장한다면 TreeMap은 키와 값이 저장된 Map, Entry 를 저장한다는 점입니다. TreeMap 에 객체를 저장하면 자동으로 정렬되는데, 키는 저장과 동시에 자동 오름차순으로 정렬되고 숫자 타입일 경우에는 값으로, 문자열 타입일 경우에는 유니코드로 정렬합니다.

 

 

 

키 값이 숫자형이라 오른차순으로 정렬된 모습

정렬 순서는 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에 키 값이 높은 것은 오른쪽 자식 노드에 Map, Entry 객체를 저장합니다. TreeMap 은 일반적으로 Map으로써의 성능이 HashMap 보다 떨어집니다. TreeMap은 데이터를 저장할때 즉시 정렬하기에 추가나 삭제가 HashMap 보다 오래 걸립니다.

하지만 정렬된 상태로 Map 을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우 TreeMap을 사용하는 것이 효율성면에서 좋습니다 .

 

 

---

레드 - 블랙 트리 (Red-Black Tree)

 

TreeMap 은 이진탐색트리의 문제점으르 보완한 레드-블랙 트리로 이루어져 있습니다. 일반 적인 이진 탐색 트리는 트리의 높이만큼 시간이 필요합니다. 값이 전체 트리에 잘 분산되어 있다면 효율성에 있어 크게 문제가 없으나  데이터가 들어올 때 값이 한쪽으로 편향되게 들어올 경우 한쪽 방면으로 크게 치우쳐진 트리가 되어 굉장히 비효율적인 퍼포먼스를 냅니다. 이 문제를 보완하기 위해 레드 블랙 트리가 등장하였습니다. 레드 블랙 트리는 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어줍닏다.