자바 기초 공부 일지 40. 컬렉션 프레임 워크 (3) TreeSet<E>

3. TreeSet<E>

 

▼ HashSet + 정렬입니다. 

Tree(트리) 자료 구조를 기반으로 하는 인스턴스에 대해서 정렬 상태를 유지하면서 인스턴스가 저장 됩니다. 

TreeSet은 정렬 알고리즘을 가지고 있는 구조 입니다. 

 

public static void main(String[] args) {
   TreeSet<Integer> tree = new TreeSet<Integer>();
   tree.add(3); tree.add(1);
   tree.add(2); tree.add(4);
   System.out.println("인스턴스 수: " + tree.size());

 

Tree 라고 하는 자료 구조는 비선형적인 자료 구조 입니다. 

즉, 출발점을 기준으로 뻗어나가는 형태의 자료 구조예요. 

예를 들어 가계도(족보)를 생각하시면 좋을 것 같아요. 

트리구조.... 이런 거..

트리 구조는 다음과 같이 들어옵니다. 

5, 3, 2, 4, 7 의 순서로 자료가 들어온다면 처음에 입력되는 값은 root인 뿌리 입니다. 

5의 값이 들어간 이후에 다음 값이 입력이 되었을 때

기준이 되는 뿌리의 값보다 작으면 왼쪽으로, 크면 오른쪽으로 정렬이 됩니다. 

그럼 5의 값은 3으로 들어가고, 2가 들어왔을 때엔 5보다 작으므로 5의 왼쪽인 3의 자리로 가고, 

3보다도 작으므로 3의 왼쪽으로 들어갑니다. 

4의 값은 5보다 작으므로 왼쪽 3의 자리로 가고, 3보다는 크기 때문에 오른쪽에 저장됩니다. 

7의 값은 5보다 크기 때문에 5의 오른쪽에 자리합니다. 

 

위 트리 구조를 읽을 때에는 왼쪽 아래로부터 위쪽으로 가는 방향으로 읽습니다.

2 → 3 → 4 → 5 → 7

즉 오름차순을 기준으로 합니다. 

 

Set<E> 인터페이스를 구현하는 코드를 확인해볼게요.

public static void main(String[] args) {
   TreeSet<Integer> tree = new TreeSet<Integer>();
   tree.add(3); tree.add(1);
   tree.add(2); tree.add(4);
   System.out.println("인스턴스 수: " + tree.size());

   // for-each문에 의한 반복
   for(Integer n : tree)
      System.out.print(n.toString() + '\t’);
   System.out.println();

   // Iterator 반복자에 의한 반복
   for(Iterator<Integer> itr = tree.iterator(); itr.hasNext(); )
   System.out.print(itr.next().toString() + '\t');
   System.out.println();
}

 

▼ Tree Set의 값 비교 방법입니다. 

 

interface Comparable    // 어떤 클래스에 비교방법을 추가하는 클래스 

   → int compareTo(Object o)

 

별개의 정렬을 위한 비교의 방법을 제시하고 싶다면 Comparable을 제시해야 합니다. 

Tres Set은 제네릭 기반을 만들어진 것이므로 제네릭 기반의 Comparable을 구현해야 하는 것입니다. 

 

즉, 자체적으로 가지고 있는 정렬 기준의 방법에서는 내가 더 클 때, 양수가 나오면 오름차순 입니다. 

(양의 정수는 오름차순, 음의 정수는 내림차순. )

 

다음은 자체적으로 가지고 있는 비교 방법이에요. 

 

class Person implements Comparable<Person> {

   String name;

   int age;

   . . .

   @Override

   public int compareTo(Person p) {

      return this.age - p.age;

   }

}

 

 

여기에서 별개의 비교 방법을 위해 Comparable을 제시를 한다면 내림차순이 되는 것을 확인할 수 있습니다. 

 

class PersonComparator implements Comparator<Person> {

   public int compare(Person p1, Person p2) {

      return p2.age - p1.age;

   }

}

 

public static void main(String[] args) {

   TreeSet<Person> tree = new TreeSet<>(new PersonComparator());

   tree.add(new Person("YOON", 37));

   tree.add(new Person("HONG", 53));

   tree.add(new Person("PARK", 22));

   for(Person p : tree)

      System.out.println(p);

}

 

즉, Person 클래스에 TreeSet 을 위한 정렬 기준이 있지만, Comparator 구현 인스턴스를 전달해서 새로운 기준을 제공한 것입니다. 

 

정렬 예시를 하나만 더 살펴 볼게요. 

 

class StringComparator implements Comparator<String> {

   public int compare(String s1, String s2) {

      return s1.length() - s2.length();

   }

}

 

public static void main(String[] args) {

   TreeSet<String> tree = new TreeSet<>(new StringComparator());

   tree.add("Box");

   tree.add("Rabbit");

   tree.add("Robot");

   for(String s : tree)

      System.out.print(s.toString() + '\t');

   System.out.println();

}

 

String  클래스의 정렬 기준은 사전 편찬순입니다. 이것을 길이 순으로 바꾸는 것입니다.

 

▼ 리스트를 Hash Set에다가 넣어주면 중복 인스턴스를 삭제할 수 있습니다. 

public static void main(String[] args) {		// 중복을 허용하는 리스트 
   List<String> lst = Arrays.asList("Box", "Toy", "Box", "Toy");
   ArrayList<String> list = new ArrayList<>(lst);

   for(String s : list)
      System.out.print(s.toString() + '\t’);
   System.out.println();

   // 중복된 인스턴스를 걸러 내기 위한 작업
   // 중복을 허용하지 않는 집합 
   HashSet<String> set = new HashSet<>(list);

// 원래대로 ArrayList<String> 인스턴스로 저장물을 옮긴다.
   list = new ArrayList<>(set);

   for(String s : list)
      System.out.print(s.toString() + '\t’);
   System.out.println();
}

 

 

▼다음으로는 TrssSet 메소드를 이용해서 집합을 생성하고 조작하는 예제를 확인해볼게요. 

 

TreeSet<Integer> ts = new TreeSet<Integer>();

 

// add() 메소드를 이용한 요소의 저장

ts.add(30);

ts.add(40);

ts.add(20);

ts.add(10);

 

// Enhanced for 문과 get() 메소드를 이용한 요소의 출력

for (int e : ts) {

    System.out.print(e + " ");

}

 

// remove() 메소드를 이용한 요소의 제거

ts.remove(40);

 

// iterator() 메소드를 이용한 요소의 출력

Iterator<Integer> iter = ts.iterator();

while (iter.hasNext()) {

    System.out.print(iter.next() + " ");

}

 

// size() 메소드를 이용한 요소의 총 개수

System.out.println("이진 검색 트리의 크기 : " + ts.size());

 

// subSet() 메소드를 이용한 부분 집합의 출력

① System.out.println(ts.subSet(10, 20));

② System.out.println(ts.subSet(10, true, 20, true));

 출처 : http://www.tcpschool.com/java/java_collectionFramework_set (TCP School)