자바의 정석 - TreeSet

TreeSet

• 이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리
• 이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖음
  -> 각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)

---

이진 탐색 트리(binary search tree)

• 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장
• 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림 (비교 횟수 증가)

---

TreeSet의 데이터 저장 과정

• boolean add(Object o) - (Object o)는 저장할 객체
• ex) 7 4 9 1 5의 순서로 데이터를 저장하면 과정은 아래와 같음
  (루트부터 트리를 따라 내려가면 값을 비교, 작으면 왼쪽, 크면 오른쪽에 저장)
• 7 저장 - 비교(4 < 7) - 4저장(왼쪽) - 비교(9 > 7) - 9저장(오른쪽) - 비교(1 < 7) - 비교(1 < 4) - 1저장(4의 왼쪽) - 비교(5 < 7) - 비교(5 > 4) - 5저장(4의 오른쪽)

---

TreeSet의 주요 생성자와 메서드

• TreeSet() - 기본 생성자
• TreeSet(Collection c) - 주어진 컬렉션을 저장
• TreeSet(Comparator comp) - 주어진 정렬기준으로 정렬
• Object first() - 정렬된 순서에서 첫 번째 객체 반환
• Object last() - 정렬된 순서에서 마지막 객체 반환
• Object ceiling(Object o) - 올림
• Object floor(Object o) - 내림
• Object higher(Object o) - 지정된 객체보다 큰 값 출력
• Object lower(Object o) - 지정된 객체보다 작은 값 출력
• SortedSet subSet(Object from, Object to) - from ~ to까지 출력 (끝 범위 제외)
• SortedSet headSet(Object to) - 지정된 객체보다 작은 값의 객체들을 반환
• SortedSet tailSet(Object to) - 지정된 객체보다 큰 값의 객체들을 반환

---

예제

class Ex1 {
	public static void main(String[] args) {
		Set set = new TreeSet(); // 범위검색, 정렬. 정렬 필요없음
//		Set set = new HashSet(); // 정렬 필요
		
		for(int i=0; set.size()<6; i++) {
			int num = (int)(Math.random()*45)+1;
			set.add(num);
		}
		System.out.println(set);
	}
}

---

트리 순회

• 이진 트리의 모든 노드를 한 번씩 읽는 것을 트리 순회라고 한다.
• 전위, 중위, 후위 순회법이 있으며 중위 순회하면 오름차순으로 정렬된다.