[ 알고리즘 / Java ] TreeMap

TreeMap 이란 ?

 TreeMap 은 이진트리를 기반으로 한 Map 컬렉션이다. 정렬 순서는 기본적으로 부모 키 값과 비교해서 작은 것은 왼쪽 자식 노드에, 큰 것은 오른쪽 자식 노드에 객체를 저장한다. Map으로써의 성능이 HashMap보다 떨어지지만, 정렬된 상태로 Map유지해야 하거나 정렬된 테이터를 조회해야하는 범위 검색이 필요한 경우에는 효율성이 좋다. 

 

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

 

TreeMap은 레드 - 블랙 트리로 이루어져 있다. 일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 필요하다. 만약 데이터가 입력될 때, 값이 한쪽으로 편향되게 들어올 경우 크게 치우쳐진 트리가 되어서 굉장히 비효율적이다. 이러한 문제를 보완하기 위한 것이 Red - Black Tree