목표

• Red-Black 트리를 구현한 자바 Collection 자료구조를 알아본다.

treeSet

• Set 인터페이스 구현, 중복 불가, 순서 없음
• Red-Black 트리를 통해 구현
• Red-Black 트리를 통해 구현됐기 때문에 삽입, 삭제 시 균형을 맞추는 연산에 따라 속도가 상대적으로 느리지만 높이가 전부고 속도가 특징인 트리답게 검색과 정렬에 굉장히 빠르다.

treeMap

• abstractMap을 구현, 키와 값을 통해 Map.Entry 객체를 저장
• get, put, remove에 대해 $O(logN)$의 속도를 보장
• 동기화 되지 않는 연산
• 삽입 시 Natural Order에 따라 자동 정렬
  삽입 시 자동 정렬로 인해 HashMap보다 속도가 많이 떨어진다.
  정렬 된 데이터를 Map으로 유지시켜야 하거나, 이미 정렬된 데이터를 key기반 검색이 필요할 때 사용
  • HashMap이 검색 속도가 $O(1)$로 빠르기 때문에 보통 HashMap을 사용한다.

treeMap 값 기준 정렬

• Comparator를 구현하여 정렬

entrySet() vs. keySet

참고

JDK9 TreeMap
JDK9 TreeSet