(9) TreeSet

1. TreeSet에 대한 기본 개념

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

 

- 이진 검색 트리의 특성상 정렬, 검색, 범위 검색에 높은 성능을 가지고 있으며, TreeSet은 이 자료구조의

성능을 향상시킨 '레드-블랙 트리'로 구현되어 있다.

 

- 구조는 트리이기 때문에 데이터를 순차적으로 저장하는 것이 아닌 저장위치를 찾아서 저장해야 하고,

삭제하는 경우 트리의 일부를 재구성해야하므로 링크드 리스트보다 데이터 추가/삭제하는 것이 느리다.

 

- 그러나 정렬된 상태를 저장하기 때문에 단일 값 검색과 범위 검색이 매우 빠르다.

 

 

- 메서드에 대한 자세한 내용은 자바의 정석 640p를 참고한다.

 

 

( 위 그림은 이진 검색 트리의 구조를 보여주며 맨 위의 노드는 '부모 노드', 왼쪽과 오른쪽에 있는 노드를 '자식 노드'

라고 부른다.

 

( 저장 방식은 부모보다 작다면 왼쪽 노드에 크다면 오른쪽 노드에 저장한다. )

 

 

 

 

1-1. TreeSet을 이해하기 위한 예제(1)

: 6개의 랜덤 값을 생성하는 예제이다.

 

 

( hashSet과는 다르게 이미 정렬돼서 출력된다. )

 

 

 

 

1-2. TreeSet을 이해하기 위한 예제(2)

: TreeSet의 subSet()을 이용하는 예제이다.

 

( set의 출력문을 보면 abc보다 Car가 앞에 있고, dance보다 dZZZZ가 앞에 있다. 왜냐하면 대문자가 소문자보다

더 우선시 하기 때문이다. 그렇기 때문에 가능하면 소문자 또는 대문자를 통일해서 저장해야 한다. )

 

( 만약 섞여있다면, 따로 앞에서 했던 Comparator를 사용하면 된다. )

( 컬렉션 프레임웍(Collections Framework) - (6) - Comparator와 Comparable (tistory.com) 의 예제 (1)을 

참고한다. ) 

 

( 이러한 자바의 문자 순서를 알고 싶다면, 공백 문자 ' ' 이후의 문자를 ++하여 95번만큼 출력하면 된다. )

 

 

 

 

1-3. TreeSet을 이해하기 위한 예제(3)

: TreeSet의 headSet()와 tailSet()을 이용하는 메서드이다.