1. 정의
내부가 트리구조 (java에서는
RED-BLACK TREE) 로 되어 있는 <Key, Value> Entry 쌍을 저장하는 자료 구조2. 특징
- 삽입, 삭제, 조회 모두 O(logN)의 시간 복잡도를 가진다.
(Java의 경우 Red-black Tree로 되어있는데, 이것은 대표적인 균형 이진 트리로, 트리 높이를 O(logN)으로 제한 할 수 있기 때문)
- HashMap과 다르게 내부 Entry가 Key 값 기준 오름차순 정렬이 되어있다. 따라서 내부 Entry 끼리의 대소 관계 비교 + 범위 탐색이 가능
3. HashMap과의 차이 비교
구분 | HashMap | TreeMap |
내부 구조 | 해시 함수 + 버킷 테이블(배열) | 트리 구조 (java는 red-black balanced Tree) |
삽입,삭제,조회 시간복잡도 | O(1) | O(logN) |
Null Key 허용 여부 | 최대 한 개 허용 | 불가 |
데이터 정렬 | 불가 | 키 기준 오름차순 정렬 |