[Java] TreeSet

이진 트리

링크드 리스트 처럼 여러개의 노드가 서로 연결된 구조이며, 모든 노드가 최대 2개의 하위 노드를 갖는 트리

이진 트리의 노드 구성 예시)

class TreeNode {
    TreeNode left;
    Object element;
    TreeNode right;
}

이진 탐색 트리

• 이진 트리의 한 종류
• 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장하는 방식으로 동작
• 검색과 정렬에 유리
• 데이터가 많아질수록, 추가/삭제 시간이 더 오래 걸림

TreeSet

Set 인터페이스를 구현한 컬렉션
Set 인터페이스를 구현했기 때문에, 순서를 유지하지 않고, 중복을 허용하지 않는다.

TreeSet은 이진 탐색 트리(binary search tree)로 구현이 되어 있어, 범위 탐색과 정렬에 유리하다.

사용예시

Set set = new TreeSet();

// Set에 랜덤 수를 담는다. (중복 허용 x / 순서 유지)
for (int i=0; set.size()<6; i++) {
    int num = (int)(Math.random()*45) +1;
    set.add(num);
}

System.out.println(list);

• TreeSet은 저장할 때 정렬하기 때문에, HashSet과 다르게 따로 정렬할 필요가 없다.

주의할 점

TreeSet은 저장과 동시에 정렬을 하기 때문에, 참조형을 저장할 때는 해당 참조형이 Comparable을 구현하고 있던지, 아니면 Comparator를 제공해서 해당 참조형들을 비교할 방법을 알려줘야 한다.