[JAVA] TreeSet

1. TreeSet

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

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

이진트리(Binary Tree) 는 링크드 리스트처럼 여러 개의 노드가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며 루트라고 불리는 하나의 노드에서부터 시작해 계속 확장해 나갈 수 있다. 위 아래로 연결된 두 노드를 부모-자식관계에 있다고 하면 위의 노드를 부모 노드, 아래의 노드를 자식노드라고 한다.

 

이진 트리의 노드를 코드로 표현하면 다음과 같다. 데이터를 저장하기 위한 Object 타입의 참조변수 하나와 두개의 노드를 참조하기 위한 두 개의 참조변수를 선언한다.

class TreeNode{
	TreeNode left; //왼쪽 자식 노드 
	Object element;  //객체를 저장하기 위한 참조변수 (값이 들어가 있는 주소를 가지고 있는 변수!)
  	TreeNode right; //오른쪽 자식 노드 
}
//참조변수? 실제 값을 가진 변수가 아니라 값이 들어가 있는 주소를 가지고 있는 변수를 말한다.

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

 

 

 

예를들어 이진 검색 트리에 7,4,9,1,5의 순서로 값을 저장한다고 가정하면 밑의 그림과 같은 저장과정을 거친다.

1. 먼저 저장되는 7은 루트가 된다.
2. 두번째 4는 루트와 값을 비교해 트리를 따라 왼쪽에 저장한다.
3. 세번째 9도 루트와 비교해 오른쪽에 저장한다.
4. 네번째 1도 루트와 비교 그리고 밑의 노드와 비교해 더 작은 값이기 때문에 왼쪽에 저장한다.

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

따라서 왼쪽 마지막 값에서부터 오른쪽 값까지 값을 ‘왼쪽 → 부모 → 오른쪽 노드’순으로 읽으면 오름차순으로 정렬된 순서를 얻을 수 있다. 이처럼 TreeSet은 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위검색 예를 들면 3과 7 사이의 범위에 검색이 매우 빠르다.

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

 

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

 

 이진검색트리(Binary search tree)

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

 

생성자 또는 메서드	설명
TreeSet()	기본 생성자
TreeSet(Collection c)	주어진 컬렉션을 저장하는 TreeSet 생성
TreeSet(Comparator comp)	주어진 정렬조건으로 정렬하는 TreeSet 생성
TreeSet(SortedSet s)	주어진 SortedSet을 구현한 컬렉션을 저장하는 TreeSet생성 (SortedSet은 원소들이 정렬되어 있는 set)
boolean add(Object o)
boolean addAll(Collection c)	지정된 객체 또는 Collection의 객체들을 Collection에 추가
Object ceiling(Object o)	지정된 객체와 같은 객체를 반환, 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
void clear()	저장된 모든 객체를 삭제
Object clone()	TreeSet을 복제해 반환
Comparator comparator()	TreeSet의 정렬기준을 반환 (comparator)
boolean contains(Object o), boolean containAll(Collection c)	객체 또는 Collection의 객체들의 포함되어 있는지 확인
NavigableSet descendingSet()	TreeSet에 저장된 요소들을 역순으로 정렬해 반환
Object first()	정렬된 순서에서 첫번째 객체를 반환
Object floor(Object o)	지정된 객체와 같은 객체를 반환. 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
SortedSet headSet(Object toElement)	지정된 객체보다 작은 값의 객체들을 반환
NavigableSet headSet(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 pollLast()	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)	범위 검색의 결과를 반환한다. (True면 시작값또는 끝값이 포함된다.)
SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값의 객체들을 반환
Object[] toArray()	저장된 객체를 객체배열로 반환
Object[] toArray(Object[] a)	저장된 객체를 주어진 객체배열에 저장해 반환

TreeSet<Integer> ts1 = new TreeSet<>(); //객체 생성
ts1.add(1);
ts1.add(2);

TreeSet<Integer> ts2 = new TreeSet<>(ts1);//주어진 컬렉션을 저장하는 TreeSet생성
System.out.println(ts1); //[1,2]
System.out.println(ts2); //[1,2]

TreeSet<Integer> ts3 = new TreeSet<>(Collections.reverseOrder()); //내림차순으로 정렬로 생성
ts3.add(1); 
ts3.add(2);
System.out.println(ts3); //[2,1]

System.out.println(ts3.ceiling(1)); //같은 객체 반환
System.out.println(ts3.comparator()); //정렬기준 반환
System.out.println(ts1.comparator());

System.out.println(ts3.descendingSet());//기존 정렬에서 역순으로 정렬해서 반환
System.out.println(ts1.descendingSet());

• TreeSet 예제 0 : 로또번호 만들기

public class TreeSetLotto {
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();

        for(int i =0; set.size() < 6; i ++){
            int num = (int)(Math.random() * 45) +1; //0.0 ~ 1.0 사이 랜덤숫자 * 45 +1
            set.add(num);
        }
        System.out.println(set);
    }
}

TreeSet은 저장할 때 이미 정렬하기 때문에 읽어올때 따로 정렬할 필요가 없다.

• TreeSet 예제1

public class TreeSetEx1 {
    public static void main(String[] args) {
        TreeSet<String> 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)); //result1 : [bat, car]
        System.out.println("result2 : " + set.subSet(from, to + "zzz")); //result2 : [bat, car, dZZZZ, dance, disc]

				char ch = ' ';// 아스키코드에서 sp 공백을 말함
	      //공백 이후의 문자들을 모두 출력
	      for(int i =0; i < 95; i++){
	          System.out.print(ch++);
	      }
    }
}

subSet()을 이용해 범위검색을 하면 시작범위는 포함되지만 끝 범위(d)는 포함되지 않으므로 result1에는 c로 시하는 단어까지만 검색결과에 포함되어있다. 만약에 끝 범위인 d로 시작하는 단어까지 포함시키고자 한다면 위와 같이 끝 범위에 “zzz” 와 같은 문자열을 붙이면 된다. d로 시작하는 단어 중에서 “dzzz” 다음에 오는 단어는 없을 것이기 때문에 d로 시작하는 모든 단어들이 포함될 것이다.

대문자가 소문자보다 우선하기때문에 대소문자가 섞여 있는 경우 의도한 것과는 다른 범위검색결과를 얻을 수 있다.따라서 가능하면 대소문자를 통일해서 저장하는 것이 좋다. 문자열의 경우 정렬순서는 문자의 코드값이 기준이 되므로, 오름차순 정렬의 경우 코드값의 크기가 작은 순서에서 큰 순서 (공백, 숫자, 대문자, 소문자)로 정렬된다.

• TreeSet 예제 2

public class TreeSetEx2 {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        int[] score = {80,95,50,35,45,6,5,10,100};

        for (int j : score) {
            set.add(j);
        }

        System.out.println("50보다 작은값 :" + set.headSet(50)); //[5, 6, 10, 35, 45]
        System.out.println("50보다 큰값 :" + set.tailSet(50)); //[50, 80, 95, 100]
    }
}

 

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

출처 : 자바의 정석