[Java]자바 트리셋(TreeSet) 완벽한 사용법 & 예제

읽기 전

---

Set을 이해했다는 가정하에 진행됩니다

트리 셋이란

---

"이진 검색 트리"라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다

 

이진 탐색 트리의 특징

• 모든 노드는 최대 2개의 자식 노드를 가질 수 있다
• 왼쪽 자식의 노드의 값은 부모의 노드보다 작고 오른쪽 자식 노드의 값은 부모의 노트보다 값이 커야 된다
• 노드의 추가 삭제에 시간이 걸린다
• 범위 검색과 정렬에 유리하다
• 중복된 값은 저장하지 못한다

노드 설명

---

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

class TreeNode {
    TreeNode left
    Object element;
    TreeNode right
}

이 코드로 이해가 가시면 좋겠지만 이해가 안 가시는 분들은
다음 그림은 보고 제가 설명드리겠습니다

7 5 10의 숫자가 주어졌을 땐
7을 기준으로 판단하여 왼쪽에는 5가 들어있는 객체를 만들고 오른쪽에는 7보다 큰 10이 담긴 객체를 만든다
그런데 여기서 4를 추가하면 5의 left 객체가 생깁니다

 

메서드 & 생성자 설명

---

Set과 겹치는 메서드는 설명하지 않습니다

생성자

• TreeSet()
• TreeSet(Collection c)
• TreeSet(Comparator comp) // 트리 셋은 우리가 만든 객체도 넣을 수 있는데 그 정렬 기준을 만드는 것 (링크 클릭)

메서드

(메서드 : 반환 타입)

first() : Object	정렬된 순서에서 첫번째 객체 반환
last() : Object	정렬된 순서에서 마지막 객체 반환
ceiling(Object o) : Object	지정된 객체와 같은 객체 반환, 없으면 큰값중 가장 가까운 객체반환, 없으면 null
floor(Object o) : Object	지정된 객체와 같은 객체 반환, 없으면 작은값중 가장 가까운 객체반환, 없으면 null
higher(Object o) : Object	지정된 객체중에서 큰값중 제일 가까운값 반환, 없으면 null
lower(Object o) : Object	지정된 객체중에서 작은값중 제일 가까운값 반환, 없으면 null
subSet(Object fromElement, Object toElement) : SortedSet	fromElement 부터 toElement 까지의 객체들을 반환 toElement는 미포함
headSet(Object toElement) : SortedSet	지정된 객체보다 작은 값의 객체들을 반환
tailSet(Object fromElement) : SortedSet	지정된 객체보다 큰값의 객체들을 반환

 

 

TreeSet기본 사용법

---

import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public static void main(String[] args) {
        Set set  = new TreeSet();
        Random ran = new Random();
        for (int i = 0; i < 10; i++) {
			set.add(ran.nextInt(10));
	}
        System.out.println(set);
}

결괏값으로 [0, 1, 3, 6, 7]이 나왔다 계속 돌려봐도 자동으로 정렬을 해주는 것 같다
TreeSet은 값을 입력받았을 때 자동으로 정렬을 한다
ran.nextInt(10)하면 1부터 10 -1 인 Int 값을 반환한다
자동으로 정렬이 되는 이유가 Integer에는 Comparable을 구현하고 있기 때문에 그렇고 우리들이 직접 만들 Comparable구현을 안 했으면 정렬이 되지 않습니다

 

 

주의사항

---

	public static void main(String[] args) {
        Set set  = new TreeSet();
        Random ran = new Random();
        for (int i = 0; i < 1000000; i++) {
			set.add(ran.nextInt(10));
		}
        System.out.println(set);
	}

이걸 돌리면 객체가 만들어질까요?

과연 100000개의 객체가 만들어질까요?
아닙니다

특징을 보시면 중복이 안된다 했습니다
100번을 돌리든 같은 수가 나오면 저장하지 않습니다

 

 

SubSet 이용하여 범위 검색하기

---

SubSet을 몰라도 Set을 알고 있으면 자세하게 몰라도
대략 짐작이 잡힐 겁니다

	public static void main(String[] args) {
        TreeSet<String> set  = new TreeSet<String>();
        String[] name = {"apple", "apple1", "banana", "pineapple"};
        for (String string : name) {
			set.add(string);
		}
        
        System.out.println("Search : a ~ p");
        System.out.println(set.subSet("a", "p"));
        System.out.println("Search : a ~ pzzzz");
        System.out.println(set.subSet("a", "pzzzz"));
	}
    
    
    출력
	Search : a ~ p
	[apple, apple1, banana]
	Search : a ~ pzzzz
	[apple, apple1, banana, pineapple]

 

a부터 p 까지는 pinapple이 출력되지 않습니다
왜냐하면 p 이상의 것들은 출력이 되지 않습니다 그래서 pzzzz까지 늘려줬더니 pzzzz보다 pinapple이 더 작기 때문에 출력이 됩니다.

 

기준값 이상, 이하 객체들 찾기

---

	public static void main(String[] args) {
        TreeSet<Integer> set  = new TreeSet<Integer>();
        int[] num = {3,34,23,34,65,67,68,23,7,8,9,1,7,3,83,192};
        for (int i : num) {
			set.add(i);
		}
        
        System.out.println("30 보다 큰 값"+set.tailSet(30));
        System.out.println("30보다 작은값"+set.headSet(30));
	}
 
 출력
   30 보다 큰 값[34, 65, 67, 68, 83, 192]
   30보다 작은값[1, 3, 7, 8, 9, 23]

이렇게 범위 검색 예제를 조금 변경하여 적어봤습니다