TreeSet

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

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

위 아래로 연결된 두 노드를 '부모-자식관계'에 있다고 하며, 하나의 부모에 두개의 자식이 연결될 수 있다.
코드로 표현시 ↓

	class TreeNode {
    	TreeNode left;	// 왼쪽 자식 노드
        Object element;	// 객체를 저장하기 위한 참조변수
        TreeNode right;	// 오른쪽 자식 노드
    }

이진 탐색 트리(binary search tree)

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

왼쪽 노드 → 부모 노드 → 오른쪽 노드 순으로 오름차순 정렬이 자동으로 된다.
TreeSet은 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위검색(range search), 예를 들면 3과 7사이의 범위에 있는 값을 검색이 매우 빠르다.

트리는 데이터를 순차적으로 저장하는 것이 아니라 저장위치를 찾아서 저장해야하고, 삭제 하는 경우 트리의 일부를 재구성해야 하므로 링크드 리스트보다 데이터의 추가/삭제시간은 더 걸린다.

이진 탐색 트리(binary search tree)는

• 모든 노드는 최대 두 개의 자식노드를 가질 수 있다.
• 왼쪽 자식노드의 ㄱ밧은 부모노드의 값보다 작고 오른쪽 자식노드의 값은 부모노드의 값보다 커야한다.
• 노드의 추가 삭제에 시간이 걸린다.(반복 비교로 자리를 찾아 저장)
• 검색(범위검색)과 정렬에 유리하다.
• 중복된 값을 저장하지 못한다.

이진 탐색 트리의 저장과정

p431참조, 저장과정에서 컴퓨터는 알아서 값을 비교하지 못하기 때무에 TreeSet에 저장되는 객체가 Comparable을 구현하던가 아니면, Comparator를 제공해서 두 객체를 비교할 방법을 알려줘야 한다.

TreeSet 예제

public class TreeSetExample1 {
    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"));
    }
}

위 코드는 범위 검색을 하는 코드이다. from ~ to 인데 to는 포함되지 않기 때문에 결과로는 bat,car만 나온다. 여기서 d를 포함하고 싶다면 result2와 같이 끝에 "zzz"를 더해주면 되는데 d로 시작하는 단어 중에서 'dzzz'다음에 오는 단어는 없을 것이기에 이 전까지의 d로 시작하는 모든 문자열은 출력되는 것이다.

public class TreeSetExample3 {
    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])); // set.add(score[i]); 도 가능
        }
        System.out.println("50보다 작은 값 : " + set.headSet(new Integer(50)));
        System.out.println("50보다 큰 값 : " + set.tailSet(new Integer(50)));
    }
}

위 코드는 headSet()과 tailSet()을 사용하여 기준 값으로 검색한 것이다.