[Java] 컬렉션 프레임워크 - TreeSet

TreeSet은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다. 이진 검색 트리는 정렬, 검색, 범위검색(range search)에 높은 성능을 보이는 자료구조이며 TreeSet은 이진 검색 트리의 성능을 향상시킨 '레드-블랙 트리(Red-Black tree)'로 구현되어 있다.

Set인터페이스이므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.

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

위 아래로 연결된 두 노드를 '부모-자식관계'에 있다고 하며 위의 노드를 부모 노드, 아래의 노드를 자식 노드라 한다. 부모-자식관계는 상대적인 거시며 하나의 부모 노드는 최대 두 개의 자식 노드와 연결될 수 있다.

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

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

 

데이터를 저장하기 위한 Object타입의 참조변수 하나와 두 개의 노드를 참조하기 위한 두 개의 참조변수를 선언했다.

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

예를 들어 데이터를 5, 1, 7의 순서로 저장한 이진트리의 구조는 아래와 같이 표현할 수 있다. 

첫 번째로 저장되는 값은 루트가 되고, 두 번째 값은 트리의 루트부터 시작해서 값의 크기를 비교하면서 트리를 따라 내려간다. 작은 값은 왼쪽에 큰 값은 오른쪽에 저장한다. 이렇게 트리를 구성하면, 왼쪽 마지막 레벨이 제일 작은 값이 되고 오른쪽 마지막 레벨의 값이 제일 큰 값이 된다. 앞서 살펴본 것처럼, 컴퓨터는 알아서 값을 비교하지 못한다.

TreeSet에 저장되는 객체가 Comparable을 구현하던가 아니면, TreeSet에게 Comparator를 제공해서 두 객체를 비교할 방법을 알려줘야 한다. 그렇지 않으면, TreeSet에 객체를 저장할 때 예외가 발생한다.

 

왼쪽 마지막 값에서부터 오른쪽 값까지 값을 '왼쪽노드 -> 부모노드 -> 오른쪽노드' 순으로 읽어오면 오름차순으로 정렬된 순서를 얻을 수 있다. TreeSet은 이처럼 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위검색이 매우 빠르다.

저장된 값의 개수에 비례해서 검색시간이 증가하긴 하지만 값의 개수가 10배 증가해도 특정 값을 찾는데 필요한 비교횟수가 3~4번만 증가할 정도로 검색효율이 뛰어난 자료구조이다.

트리는 데이터를 순차적으로 저장하는 것이 아니라 저장위치를 찾아서 저장해야하고, 삭제하는 경우 트리의 일부를 재구성해야하므로 링크드리스트보다 데이터의 추가/삭제 시간은 더 오래 걸린다. 대신 배열이나 링크드리스트에 비해 검색과 정렬기능이 더 뛰어나다.

생성자 또는 메서드	설명
TreeSet()	기본 생성자
TreeSet(Collection c)	주어진 컬렉션을 저장하는 TreeSet을 생성
TreeSet(Comparator comp)	주어진 정렬조건으로 정렬하는 TreeSet을 생성
TreeSet(SortedSet s)	주어진 SortedSet을 구현한 컬렉션을 저장하는 TreeSet을 생성
boolean add(Object o) boolean addAll(Collection c)	지정된 객체(o) 또는 Collection(c)의 객체들을 Collection에 추가
Object ceiling(Object o)	지정된 객체와 같은 객체를 반환, 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null.
void clear()	저장된 모든 객체를 삭제한다.
Object clone()	TreeSet을 복제하여 반환한다.
Comparator comparator()	TreeSet의 정렬기준(Comparator)를 반환한다.
boolean contains(Object o) boolean containsAll(Collection c)	지정된 객체(o) 또는 Collection의 객체들이 포함되어 있는지 확인한다.
NavigableSet descendingSet()	TreeSet에 저장된 요소들을 역순으로 정렬해서 반환
Object first()	정렬된 순서에서 첫 번째 객체를 반환한다.
Object floor(Object o)	지정된 객체와 같은 객체를 반환, 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null.
SortedSet headSet(Object toElement)	지정된 객체보다 작은 값의 객체들을 반환한다.
NavigableSet haedSet(Object toElement, boolean inclusive)	지정된 객체보다 작은 값의 객체들을 반환 inclusive가 true이면, 같은 값의 객체도 포함
Object higher(Object o)	지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null.
boolean isEmpty()	TreeSet이 비어있는지 확인한다.
Iterator iterator()	TreeSet의 Iterator를 반환한다.
Object last()	정렬된 순서에서 마지막 객체를 반환한다.
Object lower(Object o)	지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null.
Object pollFirst()	TreeSet의 첫번째 요소(제일 작은 값의 객체)를 반환.
Object pooLast()	TreeSet의 마지막 요소(제일 큰 값의 객체)를 반환.
boolean remove(Object o)	지정된 객체를 삭제한다.
boolean retainAll(Collection c)	주어진 컬렉션과 공통된 요소만을 남기고 삭제한다.(교집합)
int size()	저장된 객체의 개수를 반환한다.
Spliterator spliterator()	TreeSet의 spliterator를 반환
SortedSet subSet(Object fromElement, Object toElement)	범위검색의 결과를 반환한다.(toElement는 범위에 포함되지 않음)
NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)	범위검색의 결과를 반환한다.(fromInclusize가 true이면 시작값이 포함되고, toInclusive가 true이면 끝값이 포함된다.)
SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값들의 객체들을 반환한다.
Object[] toArray()	저장된 객체를 객체배열로 반환한다.
Object[] toArray(Object[] a)	저장된 객체를 주어진 객체배열에 저장하여 반환한다.

 

// 예제
import java.util.*;

class TreeSetLotto {
    public static void main(String[] args) {
        Set set = new TreeSet();
        
        for(int i=0; set.size() < 6; i++) {
            int num = (int) (Math.reandom() * 45) + 1;
            set.add(num);  // set.add(new Integer(num));
        }
        System.out.println(set);
    }
}

TreeSet에서는 정렬하는 코드가 없는데, 그 이유는 저장할 때 이미 정렬 상태로 저장하기 때문에 읽어올 때 따로 정렬할 필요가 없기 때문이다.

 

import java.util.*;

class TreeSetEx1 {
    public static void main(String[] args) {
        TreeSet set = new TreeSet();
        
        String from = "b";
        String to = "d";
        
        set.add("abc");      set.add("alien");    set.add("bat");
        set.add("car");      set.add("Car");      set.add("disc");
        set.add("dance");    set.add("dZZZZ");    set.add("dzzzz");
        set.add("elephant"); set.add("elevator"); set.add("fan");
        set.add("flower");
        
        System.out.println(set);
        System.out.println("range search : from " + from + " to " + to);
        System.out.println("result1 : " + set.subSet(from, to));
        System.out.println("result2 : " + set.subSet(from, to + "zzz"));
    }
}

subSet()을 이용해서 범위 검색을 할 때 시작 범위는 포함되지만 끝 범위는 포함되지 않으므로 result1에는 c로 시작하는 단어까지만 검색결과에 포함되어 있다. 만일 끝 범위인 d로 시작하는 단어까지 포함시키고자 한다면 result2와 같이 끝 범위에 "zzz"와 같은 문자열을 붙이면 된다.

 

d로 시작하는 단어중에서 "dzzz"다음에 오는 단어는 없을 것이기 때문에 d로 시작하는 모든 단어들이 포함될 것이다. 결과를 보면 "abc"보다 "Car"이 앞에 있고 "dZZZZ"가 "dance"보다 앞에 정렬되어 있는것을 알 수 있다. 대문자가 소문자보다 우선하기 때문에 대소문자가 섞에 있는 경우 의도한 것과는 다른 범위검색결과를 얻을 수 있다. 그래서 가능하면 대문자 또는 소문자로 통일해서 저장하는것이 좋다. 하지만 반드시 대소문자가 섞여 있어야 하거나, 다른 방식으로 정렬해야하는 경우 Comparator를 이용하면 된다.

 

문자열의 경우 정렬순서는 문자의 코드값이 기준이 되므로, 오름차순 정렬의 경우 코드값의 크기가 작은 순서에서 큰 순서, 즉 공백, 숫자, 대문자, 소문자 순으로 정렬되고 내림차순의 경우 그 반대가 된다. 

class AsciiPrint {
    public static void main(String[] args) {
        char ch = ' ';
        // 공백 이후의 문자열들을 출력한다.
        for(int i=0; i<95;i++) 
            System.out.println(ch++);
    }
}

출력된 실행 결과의 첫 번째 문자는 공백문자이다.

 

import java.util.*;

class TreeSetEx2 {
    public static void main(String[] args) {
        TreeSet set = new TreeSet();
        int[] score = {80, 95, 50, 35, 45, 65, 10, 100};
        
        for(int i=0; i<score.length; i++)
            set.add(new Integer(score[i]));
        
        System.out.println("50보다 작은 값 : " + set.headSet(new Integer(50)));
        System.out.println("50보다 큰 값 : " + set.tailSet(new Integer(50)));
    }
}

headSet메서드와 tailSet메서드를 이용하면 TreeSet에 저장된 객체 중 지정된 기준 값보다 작은 값의 객체들과 큰 값의 객체들을 얻을 수 있다.