[기본 개념] 6 | (1.8) TreeSet

[기본 개념] 6 | (1.8) TreeSet

1 컬렉션 프레임웍의 핵심 인터페이스

2 ArrayList

3 LinkedList

4 Stack과 Queue

5 Iterator, Listlterator, Enumeration

6 Arrays

7 Comparator와 Comparable

8 HashSet

9> TreeSet

10 HashMap과 Hashtable

11 TreeMap

12 Properties

13 Collections

14 컬렉션 클래스 정리 & 요약

9. TreeSet

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

 

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

 

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

 

위 아래로 연결된 두 노드를 '부모-자식관계'에 있다고 한다.

 

		루트 ↙(root)↘
	A   ↙(부모)↘		↘
B   (A의 자식)		C   (A의 자식)

 

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

 

class TreeNode {

        TreeNode left ;            // 왼쪽 자식노드

        Object element ;        // 객체를 저장하기 위한 참조변수

        TreeNode right ;         // 오른쪽 자식노드

}

 

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

 

예를 들어 이진검색트리에 7, 4, 9, 1, 5의 순서로 값을 저장한다고 가정하자.

 

		7   (1. 저장)

  

                                                                           ▼

  

		7   ↙(1. 비교 4 < 7)
	4   (2. 저장)

 

                                                                           ▼

 

		7   ↙(1. 비교 9 > 7)↘
	4		9   (2. 저장)

 

                                                                           ▼

 

		7   ↙(1. 비교 1 < 7)↘
	4   ↙(2. 비교 1 < 4)		9
1   (3. 저장)

 

                                                                           ▼

 

		7   ↙(1. 비교 5 < 7)↘
	4   ↙(2. 비교 5 > 4)↘		9
1		5   (3. 저장)

 

 지정된 기준 값에서 왼쪽노드와 그 아래의 모든 노드는 지정된 기준 값보다 작고,

나머지 노드는 지정된 기준 값보다 같거나 크다.

 

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

 

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

 

 정렬된 상태를 유지하기 때문에 배열이나 링크드 리스트보다 단일 값 검색과 범위검색이 매우 빠르다. 하지만 데이터를 순차적으로 저장하는 것이 아니기 때문에 추가/삭제는 트리의 일부를 제구성해야하므로  링크드 리스트보다 시간이 더 걸린다.

 

이진검색트리(binary search tree)

- 모든 노드는 최대 두 개의 자식노드를 가질 수 있다.

- 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 크다.

- 노드의 추가/삭제에 시간이 걸린다.

- 검색과 정렬에 유리하다.

- 중복된 값을 저장하지 않는다.

 

예제/TreeSetEx1.java

import java.util.*;

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

실행결과

[Car, abc, alien, bat, car, dZZZZ, dance, disc, dzzzz, elephant, elevator, fan, flower]
range search : from b to d
result1 : [bat, car]
result2 : [bat, car, dZZZZ, dance, disc]

 

 subSet( )을 이용해서 범위검색할 때 시작범위는 포함되지만 끝범위는 포함되지 않으므로 result1에는 c로 시작하는 단어까지만 포함되어 있다.

 

 만약 d로 시작하는 단어까지 포함시키고싶으면, 끝범위에 'zzz'를 붙이면 된다. d로 시작하는 단어중에서 'dzzz' 다음에 오는 단어는 없을 것이기 때문이다.

 

 결과를 보면 대문자가 소문자보다 우선하는데 대소문자가 섞여 있어서 의도한 것과 다른 결과를 얻었다. 따라서 가능하면 대문자 또는 소문자로 통일하는 것이 좋다.

 

 

 

 

출처 | Java의 정석 (남궁 성)