[JAVA] 컬렉션프레임워크(CollectionFramework) 4 - TreeSet

Set 구현체

TreeSet

---

TreeSet은 이진검색트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다.

이진검색트리는 정렬, 검색, 범위검색(range search)에 뛰어난 성능을 보이는 자료구조이며, '레드-블랙 트리'로 구현되어 있다.

(이미지 출처)

이진 트리(binary tree)는 링크드리스트처럼 여러 개의 노드가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며 '루트(root)'라고 불리는 하나의 노드에서부터 시작해서 계속 확장해 나간다.

이진트리의 노드를 코드로 표현하면 다음과 같다.

Class TreeNode{
    TreeNode lfet; // 왼쪽 자식노드
    Object element; // 객체를 저장하기 위한 
    TreeNode right; // 오른쪽 자식노드 
}

이진검색트리(binary search tree)는 부모노드의 왼쪽에는 부모노드의 값보다 작은 값의 자식노드, 오른쪽에는 큰 값의 자식노드를 저장하는 이진트리이다.

TreeSet은 정렬된 상태를 유지하기 때문에 단일 검색과 범위검색(range search)에 유리하다.

왼쪽 마지막 값에서부터 '왼쪽노드 -> 부모노드 -> 오른쪽노드' 순으로 읽어오면 오름차순으로 정렬된 순서를 얻을 수 있다. 

이진검색트리 특징

• 모든 노드는 최대 두 개의 자식노드를 가질 수 있다.
• 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽자식 노드의 값은 부모노드의 값보다 커야한다.
• 노드의 추가 삭제에 시간이 걸린다.(순차적으로 저장하지 않으므로)
• 검색과 정렬에 유리하다.

headSet(Object toElement) => 지정된 객체보다 작은 값의 객체들을 반환한다.

subSet(Object from, Object to) => 범위 검색의 결과를 반환한다. (끝 범위인 toElement는 범위에 포함되지 않음)

tailSet(Object fromElement) => 지정된 객체보다 큰 값의 객체들을 반환한다. 

public class TreeSetTest {
       public static void main(String[] args){
              TreeSet<String> set = new TreeSet<>();
              
              String from = "b";
              String to   = "d";
              
              set.add("abc");
              set.add("aff");
              set.add("bar");
              set.add("car");
              set.add("Car");
              set.add("detect");
              set.add("daaaaa");
              set.add("dzzzzz");
              set.add("ear");
              set.add("edd");
              set.add("zzz");
              
              System.out.println(set);
              System.out.println(set.subSet(from, to));
              System.out.println(set.subSet(from, to + "zzzzz"));
       }
}

-- result --

[Car, abc, aff, bar, car, daaaaa, detect, dzzzzz, ear, edd, zzz]

[bar, car]

[bar, car, daaaaa, detect]

subSet을 이용한 범위검색은 시작범위는 포함되지만 끝 범위는 포함되지 않는다.

TreeSet을 만들 때, 문자열 정렬 방식을 다르게 설정하려면 Comparator를 이용하면 된다.

Comparator와 Comparable

---

Comparator와 Comparable은 모두 인터페이스로 객체들을 정렬 또는 이진검색트리를 구성하는데 필요한 메서드들을 정의하고 있다.

Comparable을 구현하고 있는 클래스들은 같은 타입의 인스턴스끼리 서로 비교할 수 있는 클래스들, 주로 Wrapper 클래스(Integer, String), Date, File과 같은 것들이며, 기본적으로 오름차순으로 정렬되도록 구현되어 있다. 

comparable을 구현한 클래스는 정렬이 가능하다는 것을 의미한다.

Comparable을 구현한 내용에 따라 데이터들으 정렬이 되기 때문에, TreeSet에 Comparable이 구현되지 않은 클래스의 인스턴스를 담는다면 실행시 에러가 난다.

Comparable - 기본 정렬기준을 구현하는데 사용

Comparator - 기본 정렬기준 외에 다른 기준으로 정렬하고자할 때 사용

public interface comparable{
    // java.lang 패키지
    public int compareTo(Object o);
}
 
public interface comparator{
    // java.util 패키지
    int compare(Object o1, Object o2);
    boolean equals(Object obj);
}

비교하는 두객체가 같으면 0, 비교하는 값보다 작으면 음수, 크면 양수를 반환한다.

Integer 클래스의 compareTo 구현함수를 살펴보면 아래와 같다.

public final class Integer extends Number implements Comparable{
    ..
    public int compareTo(Integer anotherInteger) {
        return compare(this.value, anotherInteger.value);
    }
 
    public static int compare(int x, int y) {
        return (x < y) ? -1 : ((x == y) ? 0 : 1);
    }
    ...
}

Comparator를 활용하여 treeSet 데이터 삽입시, 정렬순서를 역순(내림차순)으로 설정하기

public class TreeSetTest2 {
    public static void main(String[] args){
        TreeSet<Integer> set1 = new TreeSet<>();
        TreeSet<Integer> set2 = new TreeSet<>(new Descending()); // TreeSet(Comparator c)
        
        Integer[] scores = {30, 50, 10, 20, 40};
        for(int i=0; i<scores.length; i++){
            set1.add(i);
            set2.add(i);
        }
        
        System.out.println("set1 : " + set1);
        System.out.println("set2 : " + set2);
    }
    
}
class Descending implements Comparator<Object>{
    
    @Override
    public int compare(Object o1, Object o2){
        
        if(o1 instanceof Comparable && o2 instanceof Comparable){
            Comparable c1 = (Comparable) o1;
            Comparable c2 = (Comparable) o2;
            return c1.compareTo(c2) * -1;
            // -1을 곱해서 정렬방식의 역으로 변경 또는 c2.compareTo(c1) 으로 변경한다.
        }
        return -1;
    }
}

-- result --

set1 : [0, 1, 2, 3, 4]

set2 : [4, 3, 2, 1, 0]

TreeSet은 데이터를 정렬된 상태로 저장하는데, TreeSet을 생성할 때 Comparator를 지정해주지 않으면 객체(Comparable)에 구현된 정렬방식에 따라 정렬된다. Comparator를 지정해주면 지정된 Comparator에 따라 정렬하게 된다.

Set1은 Integer 기본정렬(Comparable)인 오름차순으로 정렬

Set2는 Descending 클래스에 정의된 정렬방식(Comparator)로 정렬되었다.

오름차순을 내림차순으로 구현하는 방법은 구현된 compareTo() 결과값에 -1을 곱하거나, 비교하는 객체의 위치를 변경하면 된다. 

(출처 : JAVA의 정석)