Java TreeSet 이진 트리 구조

Java TreeSet 이진 트리 구조

결과

결과

코드

package pk;

import java.util.Iterator;
import java.util.NavigableSet;
import java.util.TreeSet;

public class Test {

	public static void main(String[] args) {
		TreeSet<Integer> ts = new TreeSet<Integer>();
		
		ts.add(8); ts.add(8); ts.add(3);
		ts.add(6); ts.add(7); ts.add(2);
		ts.add(9); ts.add(1); ts.add(5);
		
		// 이진 트리 : 부모보다 작은것은 왼쪽, 큰 것은 오른쪽에 저장 
		System.out.println("가장 작음 : " + ts.first());	// 가장 왼쪽
		System.out.println("가장 큼 : " + ts.last());	// 가장 오른쪽
		System.out.println("10이하 가장 가까움 : " + ts.floor(10));	// 미만은 lower 메소드
		System.out.println("10이상 가장 가까움 : " + ts.ceiling(10)); // 초과는 higher 메소드
		
		System.out.println("가장 작은 값 삭제 : " + ts.pollFirst());
		System.out.println("가장 큰 값 삭제 : " + ts.pollLast());
		
		
		Iterator<Integer> it = ts.iterator();
		System.out.print("\n오름차순 정렬 : ");
		while(it.hasNext()) System.out.print(it.next() + " ");
		
		it = ts.descendingIterator();
		System.out.print("\n내림차순 정렬 : ");
		while(it.hasNext()) System.out.print(it.next() + " ");
		
		
		System.out.print("\n\n=== 특정 범위 값들 가져오기 ===");
		NavigableSet<Integer> nav = ts.headSet(5, true); // true : 이하, false : 미만
		it = nav.iterator();
		System.out.print("\n5 이하 값들 : ");
		while(it.hasNext()) System.out.print(it.next() + " ");
		
		
		nav = ts.tailSet(5, false); // true : 이상, false : 초과
		it = nav.iterator();
		System.out.print("\n5 초과 값들 : ");
		while(it.hasNext()) System.out.print(it.next() + " ");
		
		
		nav = ts.subSet(3, true, 7, true); // true : 범위값도 포함, false = 미포함
		it = nav.iterator();
		System.out.print("\n3이상 7이하 값들 : ");
		while(it.hasNext()) System.out.print(it.next() + " ");
	}

}

TreeSet : 이진 트리 구조를 갖는다.

(부모 노드보다 작으면 왼쪽, 크면 오른쪽 자식 노드의 위치)

ㄴ 따라서 [왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 ] 순으로 값을 읽기만 하여도 오름차순으로 정렬된 값들을 얻어올 수 있게 된다.

이와 같은 구조 때문에 검색을 빠르게 할 수 있다.

ㄴ TreeSet은 Set이 들어가 있어 알수 있듯이 이진 트리 구조의 Set 컬렉션으로 중복된 값을 가질 수 없다.

---

메소드

삽입, 삭제 등 : Set 컬렉션으로 동일한 메소드를 사용한다.

링크

[JAVA/심화] - Java HashSet - 집합 삽입, 삭제, 탐색

E first() : 가장 작은 값

- 가장 작은 값, 즉 이진트리에서 가장 왼쪽의 값이다.

E last() : 가장 큰 값

- 가장 큰 값, 즉 이진트리에서 가장 오른쪽 값이다.

E floor(E e) : 인수보다 이하의 객체(값)

- 인수의 해당하는 값이 없다면 그보다 이하의 값들 중 가장 가까운 값을 리턴한다.

- 미만의 값을 구하고자 한다면 lower() 메소드를 사용하면 된다.

E ceiling(E e) : 인수보다 이상의 객체(값)

- 인수의 해당하는 값이 없다면 그보다 이상의 값들 중 가장 가까운 값을 리턴한다.

- 단, 존재하지 않을 경우 null을 리턴한다.

- 초과의 값을 구하고자 한다면 higher() 메소드를 사용하면 된다.

E pollFirst() / E pollLast = First 값 제거 / Last 값 제거

- 해당하는 값을 리턴해준 후 제거한다.

---

정렬

- 오름차순 : 이진 트리 구조상 이미 정렬이 되어져 있으므로 iterator() 메소드로 가져오면 오름차순으로 정렬되어 있다.

- 내림차순 : descendingIterator() 메소드를 사용하여서 Iterator<E>의 가져오면 내림차순으로 정렬된다.

---

범위 검색

NavigableSet<E> headSet(E e, boolean b) : 인수 값보다 작은 값들 검색

- 위 예시에서는 5를 주어서 5이하의 값들을 검색하였다.

- 2번 째 인자인 b가 

true일 경우 e 이하를 검색

false일 경우 e 미만을 검색

한다.

NavigableSet<E> tailSet(E e, boolean b) : 인수 값보다 큰 값들 검색

- 위 예시에서는 5와, false를 주어서 5를 초과하는 값들을 검색하였다.

- 2번 째 인자인 b가 

true일 경우 e 이상을 검색

false일 경우 e 초과를 검색

한다.

NavigableSet<E> subSet(E start, boolean b, E end, boolean b2) 

- 시작 값과 끝 값을 인수로 주어 그 사이 범위의 값들을 리턴한다.

- 2, 4번 째 인자는 동일하게 true면 해당값도 포함이며 false면 미포함이다.