🏃♂️ 들어가기 앞서..
본 게시물은 스터디 활동 중에 작성한 게시물로 자바의 정석-기초편 교재를 학습하여 정리하는 글입니다.
※ 스터디 Page : 〔투 비 마스터 : 자바〕
＊해당 교재의 목차 순서와 구성을 참고하여 작성하며
각 내용마다 부족할 수 있는 내용이나 개인적으로 궁금한 점은
추가적인 검색을 통해 채워나갈 예정입니다.
🎄 TreeSet
" 범위 검색 " 과 " 정렬 "에 유리한 컬렉션 클래스
( 단, HashSet보다 데이터 추가/삭제 작업에 시간이 더 걸린다. )
" 이진 탐색 트리 ( binary search tree ) " 자료구조의 형태로 저장
( TreeSet은 이 이진탐색트리보다 성능이 향상된 레드-블랙 트리(Red-Black Tree)로 구현되어 있음. )
이 이진 트리(binary tree)는
이전에 살펴봤던 LinkedList에서도 사용한 노드(node)를 활용한다.
여러개의 노드가 서로 연결되어 있고
각 노드는 최대 2개의 노드만 연결할 수 있다는 특징이 있으며
" 루트(root) " 라는 하나의 노드로부터 확장되어 나가는 형식이다.
즉, 루트는 트리 확장의 첫 기준의 역할을 수행한다.
구분되게 되면
[ 위-아래 ] 로 연결된 노드들간의 관계를 [ 부모 - 자식 ]관계라고 표현한다.
( 위 : 부모 / 아래 : 자식 → 부모 Node 당 최대 2개의 자식 Node 연결 가능 )
각 노드의 구조는 다음과 같다.
class TreeNode {
TreeNode left ; //첫번째(왼쪽) 자식 노드
Object element ;
TreeNode right ; //두번째(오른쪽) 자식노드
}🔎 이진 탐색 트리 _ binary search tree
부모보다 작은 값 ▶ 왼쪽 에 저장
부모보다 큰 값 ▶ 오른쪽 에 저장
위와 같은 규칙을 가지고 노드들을 저장하는 것이 이진 탐색 트리이다.
이렇게 저장하게되면
『 왼쪽 마지막 값 에서 오른쪽까지의 값 』을
" 왼쪽 ↗ 부모 ↘ 오른쪽 " 순으로 읽어오게 되면 오름차순으로 정렬된 순서를 얻을 수 있게된다.
부모의 부모로 이동하게 되는 것도 마찬가지이다.
이전 단계에선 부모였더라도
이 부모 노드가 위로 올라가게되면
왼쪽에 있던 자식노드로서 이미 읽은 것이기 때문에
곧바로 부모노드를 읽고 이 부모노드의 오른쪽 자식 노드를 읽으면 된다.
TreeSet은 이와 같은 정렬된 상태로 유지되기 때문에
값의 갯수가 증가하더라도 범위가 2갈래로 나눠져서
비교횟수가 크게 늘지 않게되니
" 단일 값 검색 & 범위검색 "이 매우 빠르다.
하지만
저장의 경우엔
순차적이지 않고 " 위치를 찾아서 저장 "해야하기 때문에 느리고
삭제의 경우엔
트리의 일부를 " 재구성 "해야하기 때문에 느리다.
그래서 < 저장&삭제 >의 부분에 있어서는
링크드 리스트( Linked List )가 더 빠르다
※ 저장 과정
boolean add(Object o)- 호출하게 되면 내부적으로compare()를 활용
( HashSet이equals()와hashCode()를 사용하는 것과 차이가 있음. )
- 첫 번째 값 : 루트(root)
- 두 번째 값부터는 루트부터 시작해서 값을 비교하면서 대소관계에 따라 방향을 설정해서 트리를 내려간
후, 저장
＊ TreeSet에 add할 때 " 저장 객체 "에Comparable을 구현하거나 별도의 "Comparator"를 제공함으로서 비교 방법을 제시해야 한다.
( 안하면 저장하려 할 때 예외 발생 )
메서드
add()나remove(),size(),isEmpty(),iterator(),clear(),clone()등 등의 메서드들은
앞서 알아봤던 Collection 인터페이스를 구현했던 컬렉션들의 메서드 기능과 동일하게 사용하면 된다.
※ 생성자
| Method | 설명 |
|---|---|
TreeSet() | 기본 생성자 |
TreeSet( Collection c ) | 주어진 컬렉션 저장하는 TreeSet 생성 |
TreeSet( Comparator comp ) | 주어진 정렬기준으로 정렬하는 TreeSet 생성 없으면 기존 객체의 Comparable 구현된 기본 기준을 이용 |
TreeSet( SortedSet s ) | 주어진 SortedSet 구현 컬렉션을 저장하는 TreeSet 생성 |
※ 요소 반환
| Method | 설명 |
|---|---|
Object first() | (오름차순 정렬된 순서) 첫 번째 객체 반환 |
Object last() | (오름차순 정렬된 순서) 마지막 객체 반환 |
Object pollFirst() | TreeSet의 " 제일 작은 값 "인 첫번째 요소 반환 |
Object pollLast() | TreeSet의 " 제일 큰 값 "인 마지막 번째 요소 반환 |
| [ 이상/이하 & 초과/미만 ] | |
Object ceiling( Object o )같거나 가까운 큰 값 | 지정된 객체와 같은 객체 반환 없으면 큰 값 중 가까운 값의 객체 반환 ( 이마저도 없으면 null ) |
Object floor( Object o )같거나 가까운 작은 값 | 지정된 객체와 같은 객체 반환 없으면 작은 값 중 가까운 값의 객체 반환 ( 이마저도 없으면 null ) |
Object higher( Object o )가까운 큰 값 | 큰 값 중 가까운 값의 객체 반환 ( 없으면 null ) |
Object lower( Object o )가까운 작은 값 | 작은 값 중 가까운 값의 객체 반환 ( 없으면 null ) |
| [ 기능 요소 ] | |
Comparator comparator() | TreeSet의 " 정렬 기준 " 반환 |
Spliterator spliterator() | TreeSet의 " spliterator " 반환 |
| ---------------------------------------------------------------------------------- | ----------------------------------------------------------------------------- |
| 《《 반환 : Set 》》 | |
NavigableSet descendingSet() | TreeSet 저장 요소들을 " 역순 "으로 정렬해서 반환 |
| [ 범위 검색 ] | |
SortedSet headSet( Object toElement ) | 「 ~ toElement 」범위 검색 결과 반환 : " toElement보다 작은 값 ( 끝값 포함 X ) |
NavigableSet headSet( Object toElement, boolean inclusive ) | 「 ~ toElement 」범위 검색 결과 반환 : " toElement보다 작은 값 " ( inclusive - true : 끝값 포함 ) |
SortedSet tailSet( Object fromElement ) | 「 fromElement ~ 」범위 검색 결과 반환 : " toElement보다 큰 값 " |
SortedSet subSet( Object fromElement, Object toElement ) | 「 fromElement ~ toElement 」범위 검색 결과 반환 ( toElement는 포함 X ) |
NavigableSet subSet( Object fromElement, boolean inclusive,Object toElement, boolean inclusive ) | 「 fromElement ~ toElement 」범위 검색 결과 반환 ( 위에서의 inclusive와 같은 기능 : 첫/마지막 포함 여부 ) |
(String 객체들의 경우) " + " 연산자를 통해 문자열을 합쳐 문자열 기준을 수정할 수도 있다ex. .subSet("b", "d" + "zzz") 과 같이 "dzzz"로 toElement 수정 |
◎ 트리 순회 (
tree traversal): 이진 트리의 모든 노드를 한번씩 읽는 것
- 자식 노드를 먼저 읽는 것 : 전위 순회 ( preorder )
- 부모 노드를 먼저 읽는 것 : 후위 순회 ( postorder )
- " 왼쪽 ↗ 부모 ↘ 오른쪽 " 순으로 읽는 것 : 중위 순회 ( inorder ) ▶ 오름차순 정렬
- " 최상위 계층 → 최하단 계층 " 왼쪽 → 오른쪽 순으로 읽는 것 : 레벨 순회
