39강) HashSet

​오늘은 Set관련 이야기 중 번째 시간으로 "TreeSet(트리셋)"에 대해서 다뤄보려고 합니다.  


 자료구조 TreeSet(트리셋)


 자료구조란?

 자료(Data)를 컴퓨터에서 효율적으로 사용하도록 해주는 알고리즘을 뜻한다.

 (효율적 = 실행시간 최소화, 계산의 간편화 등...)

아마 컴퓨터 공학과를 가셨거나 가시게 되면 자료구조를 배우시게 되는데 이게 무지하게 중요합니다.

또한 각종 자료구조를 직접 만들어보게 될겁니다.


트리셋은 엄청 빠른속도로 데이터에 접근이 가능한 셋입니다.

(HashSet보다는 느립니다.)


 TreeSet의 특징

 1) 저장되는 데이터의 순서를 파악할 수 없다.

 2) HashSet과 마찬가지로 데이터 중복저장이 안된다.


이 트리셋은 다른 자료구조 클래스와 마찬가지로 "제네릭"을 이용하여 저장 데이터를 결정하게 됩니다.


 여기서 잠깐!! TreeSet은 기본적으로 동기화되지 않습니다.

(사진 출처 : Oracle Java Documents)

트리셋은 기본적으로는 동기화하지 않습니다. 그 대신에 동기화를 따로 할 수 있는데요.

"Collections.synchronizedSortedSet" 메소드를 이용하여 "wrapping"해주면 됩니다.



 TreeSet 훑어보기

트리셋도 역시 빠르게 데이터를 검색한다고 했습니다.

그럼 트리셋은 어떻게 데이터를 탐색할까요?


바로 이진 탐색트리(BST)를 이용합니다.


 이진탐색트리(Binary Search Tree)

 이진트리를 사용한 자료구조로 키값에 따라 노드의 위치를 정의한 탐색트리입니다.

 기본적으로 다음과 같은 특징을 갖습니다.

 1) 모든 노드는 유일한 키값을 갖는다.

 2) 왼쪽 노드는 루트의 키보다 작다.

 3) 오른쪽 노드는 루트의 키보다 크다.

 4) 모든 서브 트리도 이진탐색트리이다.

이런구조를 갖죠.



트리셋의 경우에는 "이진트리"에 대한 개념이 필요한 부분입니다.

그래서 꼭 이진트리에 대한 기초지식을 관련글들이나 자료구조 책을 통하여 먼저 익히시기를 바랍니다.



 TreeSet 사용해보기

트리셋을 사용하기 위해서는 TreeSet을 import해줘야 합니다.  

import java.util.TreeSet;

그리고 Wrapper 클래스나 자신의 커스텀 클래스를 제네릭으로 넘겨서 사용하시면 됩니다.

TreeSet<Integer> treeSet = new TreeSet<>();
TreeSet<Point> treeSetPoint = new TreeSet<>();


 

 TreeSet의 주요 메소드

형태

 메소드

 설명

boolean

 add(E e)

 e를 셋에 추가

void

 clear()

 셋의 데이터를 전부 삭제

boolean

 contains(Object o)

 셋에 o가 있다면 true, 없으면 false

E

 first()

 셋에서 가장 값이 낮은 원소를 반환

SortedSet<E>

 headSet(E toElement)

 toElement보다 낮은 요소를 반환

boolean

 isEmpty()

 셋이 비었으면 true, 아니면 false

Iterator<E>

 iterator()

 셋의 iterator를 반환

E

 last()

 셋에서 가장 값이 높은 원소를 반환

boolean

 remove(Object o)

 셋에서 o를 제거

int

 size()

 index 위치의 값을 반환(무한대 가능)

 SortedSet<E>

 subSet(E from, E to)

 from 부터 to 까지 범위에 해당되는 요소를 반환

 SortedSet<E>

 tailSet(E fromElement)

 fromElement보다 큰 요소를 반환

이때 sub​Set의 경우에는 "from 이상 to 미만"입니다.

(예 : subSet(1, 4) → 1, 2, 3)


 

 일반적인 TreeSet 사용(Wrapper)

일반적인 Wrapper 클래스를 사용한 트리셋 예제입니다. 

import java.util.Iterator;
import java.util.TreeSet;
 
public class SetTest {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<>();
 
        if(treeSet.isEmpty())
            System.out.println("트리셋이 비어있음");
 
        final int SIZE_ADD = 7;
        for(int i = 0; i < SIZE_ADD; i++)
            treeSet.add(i + 2);
        printAllElements("ADD 후 트리셋", treeSet);
 
        final int CONTAINS_ELEMENT = 4;
        if(treeSet.contains(CONTAINS_ELEMENT))
            System.out.println(CONTAINS_ELEMENT + "은(는) 트리셋에 포함되어 있음");
        else
            System.out.println(CONTAINS_ELEMENT + "은(는) 트리셋에 없음");
 
        final int REMOVE_ELEMENT = 5;
        if(treeSet.remove(REMOVE_ELEMENT))
            printAllElements(REMOVE_ELEMENT + "제거 후 트리셋", treeSet);
        else
            System.out.println(REMOVE_ELEMENT + "은(는) 없어서 제거 못함");
 
        final int HEADSET_ELEMENT = 4;
        System.out.println(HEADSET_ELEMENT + "보다 작은 요소 : " +
                treeSet.headSet(HEADSET_ELEMENT));
 
        final int SUBSET_ELEMENT_FROM = 2;
        final int SUBSET_ELEMENT_TO = 6;
        System.out.println(SUBSET_ELEMENT_FROM + "부터 " + SUBSET_ELEMENT_TO + "사이의 요소 : " +
                treeSet.subSet(SUBSET_ELEMENT_FROM, SUBSET_ELEMENT_TO));
 
        final int TAIL_ELEMENT = 8;
        System.out.println(TAIL_ELEMENT + "보다 큰 요소 : " +
                treeSet.tailSet(TAIL_ELEMENT));
 
        treeSet.clear();
        System.out.println("트리셋 클리어!");
        if(treeSet.isEmpty())
            System.out.println("트리셋이 비어있음");
    }
    public static <T extends Integer> void printAllElements(final String str, final TreeSet<T> treeSet)
    {
        Iterator<T> iterator = treeSet.iterator();
        System.out.print(str + " : ");
        while(true)
        {
            System.out.print(iterator.next());
            if(iterator.hasNext())
                System.out.print(", ");
            else
                break;
        }
        System.out.println();
    }
}

일반적인 Wrapper 클래스는 그냥 사용하면 됩니다.



 커스텀 클래스을 이용한 TreeSet 사용

우리가 직접 만든 클래스를 제네릭으로 넘길때는 커스텀 클래스가 Comparable 인터페이스를 implements 해야합니다.

그러므로써 내부에 compareTo메소드를 오버라이딩 해야합니다.


 compareTo(E data) 메소드

 Comparable 인터페이스에 선언되어 있는 메소드로 data와 자기자신의 요소를 비교할 때 사용합니다.

 서로 같으면 0을

 자신의 값이 data보다 작으면 0보다 작은값

 자신의 값이 data보다 더 크면 0보다 큰값을 갖도록 선언하면 됩니다.


이때 HashSet처럼 equals 메소드를 오버라이딩해줘도 됩니다.


이제 커스텀 클래스를 이용한 예제를 봅시다.

import java.util.Iterator;
import java.util.TreeSet;
 
class Point implements Comparable<Point>
{
    private int Xpos, Ypos;
    Point(final int Xpos, final int Ypos)
    {
        this.Xpos = Xpos;
        this.Ypos = Ypos;
    }
 
    @Override
    public String toString() {
        return "(" + Xpos + ", " + Ypos + ")";
    }
 
    @Override
    public int compareTo(Point o) {
        if(o.equals(this))
            return 0;
 
        // Point의 비교는 x좌표와 y좌표의 합으로 결정
        if(o.Xpos + o.Ypos > Xpos + Ypos)
            return -1;
        return 1;
    }
 
    @Override
    public boolean equals(Object obj) {
        Point point = (Point)obj;
        if(point.Xpos == Xpos && point.Ypos == Ypos)
            return true;
        else
            return false;
    }
}
 
public class SetTest {
    public static void main(String[] args) {
        TreeSet<Point> treeSetPoint = new TreeSet<>();
 
        if(treeSetPoint.isEmpty())
            System.out.println("트리셋이 비어있음");
 
        final int SIZE_ADD = 7;
        for(int i = 0; i < SIZE_ADD; i++)
            treeSetPoint.add(new Point(i + (3 * i), (4 * i) - i));
        // 중복 추가(8, 6), 하지만 오버라이딩한 hashCode 메소드로 인해 중복 추가되지 않음)
        treeSetPoint.add(new Point(8, 6));
        printAllElements("ADD 후 해시셋", treeSetPoint);
 
        final Point CONTAINS_POINT = new Point(20, 15);
        if(treeSetPoint.contains(CONTAINS_POINT))
            System.out.println(CONTAINS_POINT + "은(는) 해시셋에 포함되어 있음");
        else
            System.out.println(CONTAINS_POINT + "은(는) 해시셋에 없음");
 
        final Point REMOVE_POINT = new Point(12, 8);
        if(treeSetPoint.remove(REMOVE_POINT))
            printAllElements(REMOVE_POINT + " 제거 후 해시셋", treeSetPoint);
        else
            System.out.println(REMOVE_POINT + "은(는) 없어서 제거 못함");
 
        final Point HEADSET_ELEMENT = new Point(10, 10);
        System.out.println(HEADSET_ELEMENT + "보다 작은 요소 : " +
                treeSetPoint.headSet(HEADSET_ELEMENT));
 
        final Point SUBSET_ELEMENT_FROM = new Point(8, 8);
        final Point SUBSET_ELEMENT_TO = new Point(14, 14);
        System.out.println(SUBSET_ELEMENT_FROM + "부터 " + SUBSET_ELEMENT_TO + "사이의 요소 : " +
                treeSetPoint.subSet(SUBSET_ELEMENT_FROM, SUBSET_ELEMENT_TO));
 
        final Point TAIL_ELEMENT = new Point(18, 18);
        System.out.println(TAIL_ELEMENT + "보다 큰 요소 : " +
                treeSetPoint.tailSet(TAIL_ELEMENT));
 
        treeSetPoint.clear();
        System.out.println("해시셋 클리어!");
        if(treeSetPoint.isEmpty())
            System.out.println("해시셋이 비어있음");
    }
    public static <T extends Point> void printAllElements(final String str, final TreeSet<T> treeSet)
    {
        Iterator<T> iterator = treeSet.iterator();
        System.out.print(str + " : ");
        while(true)
        {
            System.out.print(iterator.next());
            if(iterator.hasNext())
                System.out.print(", ");
            else
                break;
        }
        System.out.println();
    }
}

여기서 중요한 것이 있는데 결과를 보면

(8,8) 부터 (14,14)사이의 요소의 결과를 보면 (16, 12)가 포함되어 있는 것을 볼 수 있습니다.


그 이유는

@Override
public int compareTo(Point o) {
    if(o.equals(this))
        return 0;
 
    // Point의 비교는 x좌표와 y좌표의 합으로 결정
    if(o.Xpos + o.Ypos > Xpos + Ypos)
        return -1;
    return 1;
}

x좌표와 y좌표의 합을 기준으로 큰경우에만 -1을 반환하기 때문에 그 이후에 상황에서는 무조건 1을 반환을 합니다.

그래서 좌표의 합이 서로 같을 경우에는 1을 반환하여 출력이 되어버리는 것이죠.


 자바 기초 강의 끝

이로서 자바 기초 강의가 끝이 났습니다.


사실 33강부터는 기초강의에 넣아야 되나 말아야 되나 고민을 조금 했었습니다.

그 이유가 "자료구조" 때문이었습니다.

33강부터는 자료구조를 알아야 잘 이해가 되기 때문이죠.


아무튼 여기까지가 자바의 "기초"라고 보시면 될 것 같습니다.


이 정도를 "완벽"하게 아신다면 대학에서 자바는 어느정도 무리없이 하실 수 있으실 것입니다만

실무에서 쓰려면 더욱 고급(메이븐, 스프링 연동, 네트워킹, 데이터 연동 등..)기술을 익히셔야 할겁니다.


그럼 수고하셨습니다.


저작자 표시 비영리 변경 금지
신고

+ Recent posts