[Collection] Java의 TreeSet의 특징 및 구조

TreeSet

---

TreeSet은 이진 탐색 트리를 개선한 레드 - 블랙 트리를 내부에서 사용한다.

 

TreeSet의 특징

• 순서 : 요소들은 정렬된 순서로 지정된다. 순서의 기준은 Comparator로 변경할 수 있다.
• 시간 복잡도: 주요 연산들은 O(log n) 의 시간 복잡도를 가진다. 따라서 HashSet 보다는 느리다.
• 용도: 데이터들을 정렬된 순서로 유지하면서 집합의 특성을 유지해야 할 때 사용한다.예를 들어, 범위 검색이나 정렬된 데이터가 필요한 경우에 유용하다. 참고로 입력된 순서가 아니라 데이터 값의 크고 낮음으로 정렬이 된다. 예를 들어 3, 1, 2를 순서대로 입력해도 1,2,3, 순서로 출력된다.

트리의 구조

TreeSet은 내부적으로 트리 구조(정확히는 이진 탐색 트리의 일종인 레드-블랙 트리)를 사용하여 요소들을 정렬한다.
따라서 TreeSet에 요소들을 추가하면 자동으로 오름차순으로 정렬이 된다.

---

트리는 부모 노드와 자식 노드로 구성이 된다.

 

가장 높은 조상을 루트라 한다. 자식이 2개까지 올 수 있는 트리를 이진 트리라 하는데, 여기에 노드의 왼쪽 자손은 더 작은 값을 가지고, 오른쪽 자신은 더 큰 값을 가지는 것을 이진 탐색 트리라한다.

 

TreeSet 은 이진 탐색 트리를 개선한 레드-블랙 트리를 사용한다. 기본 개념은 비슷하므로 이진 탐색 트리의 원리를 살펴보면

왼쪽과 오른쪽 노드를 알고 있으면 된다.

 

이진 탐색 트리의 핵심은 데이터를 입력하는 시점에 정렬해서 보관한다는 점이다.

그리고 작은 값은 왼쪽에, 큰 값은 오른쪽에 저장하면 된다.

public class Main {
    public static void main(String[] args) {
        Set<Integer> tree = new TreeSet<>();
        tree.add(1);
        tree.add(10);
        tree.add(5);
        tree.add(15);
        tree.add(6);
        tree.add(7);
        System.out.println(tree);
    }
}

[1, 5, 6, 7, 10, 15]

오름차순으로 정렬된 것을 볼 수 있다. 정렬이 되면서, ROOT 노드값을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽에 저장된다.

 

이진 탐색 트리 - 검색

---

총 15개의 데이터를 집어넣고, 숫자 35를 검색한다고 가정 시의 모습이다.

데이터가 총 15개인데 4번의 계산으로 필요한 결과를 얻을 수 있었다.
이것은 O(n) 인 리스트의 검색보다는 빠르고,O(1)인 해시의 검색 보다는 느리다.

• 리스트의 경우 O(n)이므로 15번의 연산이 필요하다.
• 해시 검색은 O(1)이므로 1번의 연산이 필요하다.

이진 탐색 트리의 핵심은 한번에 절반을 날린다는 것
이진 탐색 트리의 빅오는 O(log n) 이다.

 

16개의 경우 단 4번의 비교만으로 최종 노드에 도달 할 수 있다.

 

예를 들어 데이터가 점점 증가할 경우에도, 32개의 데이터 -> 2로 5번 나누기, log2(32)=5 , 64개의 데이터 -> 2로 6번 나누기, log2(64)=6, 1024개의 데이터 -> 2로 10번 나누기, log2(1024)=101024개의 데이터를 단 10번의 계산으로 원하는 결과를 찾을 수 있다.

 

데이터의 크기가 늘어나도 늘어난 만큼 한 번의 계산에 절반을 날려버리기 때문에, O(n)과 비교해서 데이터의 크기가 클수록 효과적이다.

 

이진 탐색 트리와 성능

---

이진 탐색 트리의 검색, 삽입, 삭제의 평균 성능은 `O(log n)`이다. 하지만 트리의 균형이 맞지 않으면 최악의 경우O(n)의 성능이 나온다. 만약 데이터를 1, 5, 6, 10, 15 순서로 입력했다고 가정해보자.

이렇게 오른쪽으로 치우치게 되면, 결과적으로 15를 검색 했을 때 데이터의 수인 5만큼 검색을 해야 한다. 따라서 이런 최악의 경우 O(n)이 성능이 나온다.

이런 문제를 해결하기 위해서는 트리의 균형이 너무 깨진 경우 동적으로 균형을 다시 맞추는 것이다.

앞서 중간에 있는 6을 기준으로 다시 정렬한다. 이러한 재정렬하는 다양한 알고리즘이 존재한다.(AVL 트리, 레드-블랙 트리)

 

자바의 TreeSet은 레드-블랙 트리를 사용해서 동적으로 균형을 지속해서 유지한다.

따라서 최악의 경우에도O(logn) 의 성능을 제공한다.

 

이진 탐색 트리 - 순회

---

이진 탐색 트리의 핵심은 입력 순서가 아니라, 데이터의 값을 기준으로 정렬해서 보관한다는 점이다. 따라서 정렬된 순서로 데이터를 차례로 조회를 할 수 있다. 즉 순회할 수 있다.

 

데이터를 차례로 순회하려면 중위 순회라는 방법을 사용하면 된다.

 

중위 순회
왼쪽의 서브트리를 방문한 다음, 현재 노드를 처리하고, 마지막으로 오른쪽 서브트리를 방문한다.
해당 방식은 이진 탐색 트리의 특성상, 노드를 오름차순으로 순회한다.

 

쉽게 이야기하면 자신 왼쪽의 모든 노드를 처리하고, 자신의 노드를 처리하고, 자신의 모든 오른쪽 노드를 처리하는 방식이다.

 

HashSet,LinkedHashSet,TreeSet 비교 예제

---

`HashSet` , `LinkedHashSet` , `TreeSet` 모두 `Set` 인터페이스를 구현하기 때문에 구현체를 변경하면서 실행할 수 있다.

`iterator()`를 호출하면 컬렉션을 반복해서 출력할 수 있다.
`iterator.hasNext()` : 다음 데이터가 있는지 확인한다. 
`iterator.next()` : 다음 데이터를 반환한다.

package collection.set.javaset;

import java.util.*;

public class JavaSetMain {

public static void main(String[] args) {  
    run(new HashSet<>());  
    run(new TreeSet<>());  
    run(new LinkedHashSet<>());  
}  
private static void run(Set<String> set) {  
    System.out.println("Set : " + set.getClass());  
    set.add("C");  
    set.add("B");  
    set.add("A");  
    set.add("1");  
    set.add("2");  

    Iterator<String> iterator = set.iterator();  
    while (iterator.hasNext()) {  
        System.out.print(iterator.next() + " ");  
    }  
    System.out.println();  

}

 

set = class java.util.HashSet 
A 1 B 2 C

set = cl ass java.util.LinkedHashSet 
C B A 1 2

set = class java.util.TreeSet 
1 2 A B C

 

• HashSet은 입력한 순서를 보장하지 않는다.
• LinkedHashSet은 입력한 순서를 정확히 보장한다.
• TreeSet은 데이터 값을 기준으로 정렬한다.

참고 - TreeSet의 정렬 기준
TreeSet을 사용할 때 데이터를 정렬하려면 크다, 작다라는 기준이 필요하다. 1, 2, 3이나 "A", "B", "C" 같은 기본 데이터는 크다 작다라는 기준이 명확하기 때문에 정렬할 수 있다.

 

하지만 우리가 직접 만든 Member 와 같은 객체는 크다 작다는 기준을 어떻게 알 수 있을까? 이런 기준을 제공하려면 Comparable , Comparator 인터페이스를 구현해야 한다.

 

Set의 최적화

---

해시 기반 자료구조를 사용하는 경우 통계적으로 입력한 데이터의 수가 배열의 크기를 보통 75%정도 넘어가면 해시 충돌이 자주 발생한다고한다. 따라서 75%가 넘어가면 성능이 떨어지기 시작한다.

 

해시 충돌로 같은 해시 인덱스에 들어간 데이터를 검색하려면 모두 탐색해야 한다. 따라서 성능이 O(n)으로 좋지 않다.

하지만 데이터가 동적으로 계속 추가되기 때문에 적절한 배열의 크기를 정하는 것은 어렵다.

 

자바의 HashSet은 데이터의 양이 배열 크기의 75%를 넘어가면 배열의 크기를 2배로 늘리고 2배 늘어난 크기를 기준으로 모든 요소에 해시 인덱스를 다시 적용한다. 해시 인덱스를 다시 적용한다는 점에서 시간이 걸리지만, 결과적으로 해시충돌이 줄어든다.

 

데이터의 양이 75%이상이라면 배열의 크기를 2배로 증가하고, 모든 데이터의 해시 인덱스를 커진 배열에 맞추어 다시 계산한다. 해당 과정을 재해싱이라 한다.

 

인덱스 충돌 가능성이 줄어들며, 여기서 데이터가 75%이상 증가하면 다시 2배 증가와 재계산을 반복한다.

 

정리
실무에서는 Set 이 필요한 경우 HashSet 을 가장 많이 사용한다. 그리고 입력 순서 유지, 값 정렬의 필요에 따라서 LinkedHashSet , TreeSet 을 선택하면 된다.

 

그리고 자바의 TreeSet은 레드-블랙 트리를 사용해서 동적으로 균형을 지속해서 유지한다는 점.
입력된 순서를 보장하지 않고 데이터의 값의 크고 작음을 기준으로 정렬한다는점.