[JAVA] TreeMap

TreeMap

• 레드-블랙 트리 기반으로한 Map 컬렉션
• 내부 값들을 Key값을 기준으로 정렬하여 가지고 있음
• HashMap보다 추가 삭제시 오래걸리나, 정렬된 데이터를 조회해야하는 범위 검색이 필요한 경우에는 효율적임

레드-블랙 트리

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

• 이진탐색트리의 문제점을 보완한 자료구조
• 이진탐색트리 같은 경우 한쪽으로 데이터의 값이 편향되게 들어갈 경우 굉장히 비효율적인 퍼포먼스를 냄
• 레드와 블랙으로 노드 색깔을 칠하고 부모노드보다 작은 값을 왼쪽, 큰 값을 가지면 오른쪽으로 배치하여 데이터 삽입과 삭제시 한쪽으로 치우치지 않도록 재배치와 다시칠하기 과정을 통해 균형을 맞춰줌

TreeMap 예제

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "value");
map.put(7, "value");
map.put(8, "value");
map.put(9, "value");
map.put(50, "value");
map.put(11, "value");
map.put(5, "value");
map.put(76, "value");
map.put(100, "value");
map.put(99, "value");

// 결과 : [3, 5, 7, 8, 9, 11, 50, 76, 99, 100]
System.out.println(map.keySet());