[Java] TreeMap 정리
1. Java TreeMap
자바에서 쓰이는 TreeMap에 대해서 알아보도록 하겠다. 한마디로 TreeMap은 Tree 구조를 띄고 있는 Map 형태라고 할 수 있다. Map 형태이기 때문에 (key, value)를 함께 저장하고 Tree 구조이기 때문에 이진트리를 기반으로 하고 있다. TreeMap은 Red-Black Tree (레드-블랙 트리)로 이루어져 있다.
2. Red-Black Tree란?
일반적인 이진탐색 트리의 경우에는 값이 전체 트리에 균형있게 분포되어 있다는 보장이 없다. 트리의 왼쪽 자식 노드와 오른쪽 자식 노드가 있을 때 값이 왼쪽으로만 들어가서 트리의 균형이 유지되지 않을 수 있다. 이를 보완하기 위해서 Red-Black Tree에서는 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여서 균형을 맞추도록 한다.
ex) 예를 들어 부모 노드가 7이고 4라는 값을 가지는 노드와 8이라는 값을 가지는 노드를 추가하고 싶다면, 4 노드는 부모 노드의 왼쪽 자식으로, 8 노드는 부모 노드의 오른쪽 자식으로 배치해준다.
이에 추가하여 Red-Black Tree는 다음과 같은 조건을 만족시킨다. (출처 위키피디아)
.png)
- 노드는 레드 혹은 블랙 중의 하나이다.
- 루트 노드는 블랙이다.
- 모든 리프 노드들(NIL)은 블랙이다.
- 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
- 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.
3. TreeMap 사용법
TreeMap<Integer,String> mymap = new TreeMap<Integer,String>();트리맵의 생성은 위와 같이 key와 value 값의 자료형을 <> 안에다 명시해줌으로써 생성할 수 있다.
2. TreeMap 값을 추가하기
mymap.put(1, "안녕");위와 같이 put이라는 메서드를 사용해서 값을 추가할 수 있는데 Map 이기 때문에 key, value 순서대로 값을 추가해주어야 한다.
3. TreeMap 값을 가져오기
System.out.println(mymap.get(1));위와 같은 코드는 key 값이 1인 value 값을 가져와서 출력을 하겠다는 뜻이다. 우리는 1에 대응하는 value 값을 "안녕"이라고 추가해주었으므로 "안녕"이 출력될 것이다.
4. TreeMap의 가장 작은 키/ 가장 큰 키 가져오기
가장 작은 키:
mymap.firstKey();가장 큰 키:
mymap.lastKey();TreeMap은 항상 정렬을 하고 있기 때문에 가장 작은 키/ 큰 키를 바로 가져올 수 있다는 장점이 있다.
5. TreeMap 값을 제거하기
mymap.remove(1);값을 제거할 때는 key값을 기준으로 제거해주게 된다. 즉 위의 코드는 키 값을 1로 가지고 있는 값을 제거하라라는 뜻이다.
6. TreeMap의 모든 값을 제거하기
mymap.clear();모든 (key, value)의 쌍을 제거하고 싶다면, clear() 메서드를 사용해주면 된다.
7. TreeMap의 전체 값을 출력해보기
KeySet()을 활용하면 TreeMap에 저장되어 있는 Key값을 모두 다 가져올 수 있다.
for(Integer i : mymap.keySet()){
System.out.println("[key 값]:" + i + " [Value 값]:" + mymap.get(i));
}이런식으로 KeySet()을 활용하여 key와 value값을 모두 다 출력해줄 수 있다.
entrySet() 을 활용할 수도 있는데 entrySet()을 활용하면 key와 value가 함께 저장되어 있는 Entry 배열을 가져올 수 있다.
for (Entry<Integer, String> entry : mymap.entrySet()) {
System.out.println("[Key 값]:" + entry.getKey() + " [Value 값]:" + entry.getValue());
}
이런식으로 출력해줄 수 있다.