HashSet, TreeSet(binary search tree)

출처 - Java의 정석 기초편 (남궁 성)

 

 

1. HashSet

- Set(집합)인터페이스를 구현: 순서 X, 중복 X

- equals()와 hashCode() 오버라이딩해야 HashSet 바르게 동작

- LinkedHashSet: 저장순서 유지

- TreeSet(from~to): 범위 검색과 정렬에 유리, HashSet 보다 데이터 추가, 삭제에 시간이 더 걸림

 

Object[] objArr = {"1", new Integer(1), "2", "2", "3", "3", "3"};
Set set = new HashSet();

for(int i=0l i < objArr.length; i++) {
    set.add(objArr[i]); // 중복 제거
}
System.out.println(set); // [1,1,2,3] 문자열과 Integer인스턴스 중복 아님

 

HashSet() // 생성자
HashSet(Collection c)
HashSet(int initialCapacity) // 초기용량
HashSet(int initialCapacity, float loadFactor) // load factor 0.8 → 80% 찼을 때 보통 *2
boolean add(Object o) // 객체 추가
boolean addAll(Collection c) // 합집합
void clear()
Object clone()
boolean contains(Object o)
boolean containsAll(Collection c) // 부분집합
boolean isEmpty()
Iterator iterator() // Iterator 반환
boolean remove(Object o)
boolean removeAll(Collection c) // 차집합
boolean retainAll)Collection c) // 교집합
int size() // 저장된 객체 개수 반환
Object[] toArray() // 객체배열로 반환
Object[] toArray(Object[] a)

 

 

2. TreeSet

- Set인터페이스를 구현: 순서 X, 중복 X

- 이진 탐색 트리(binary search tree)로 데이터 저장: 검색(범위 검색), 정렬 유리

- 이진 트리(binary tree): 모든 노드는 최대 2개의 하위노드 갖음(부모-자식 관계)

 

class TreeNode {
    TreeNode left;  // 왼쪽 자식노드
    Object element; // 객체를 저장하기 위한 참조변수
    TreeNode right; // 오른쪽 자식노드
}
// LinkedList 변형

 

 

3. 이진 탐색 트리(binary search tree)

- 모든 노드는 최대 2개의 자식 노드 갖음

- 루트(root)부터 트리를 따라 내려가며 값을 비교→부모보다 작으면 왼쪽, 크면 오른쪽 저장

- 오름차순: 왼쪽 노드→부모 노드→오른쪽 노드

- 장점: 검색(범위 검색), 정렬 유리

- 단점: 노드의 추가 삭제에 시간이 걸림

 

 

4. TreeSet 메서드

- HashSet: 정렬 X → 정렬 필요

- TreeSet: 저장할 때 정렬 → 정렬 필요 X

- TreeSet→HashSet 변경 불가: headSet, tailSet, subSet(TreeSet에만 있는 메서드)

 

TreeSet set = new TreeSet();
int[] score = {80, 95, 50, 35, 45, 65, 10, 100};

for(int i=0l i < score.length; i++)
    set.add(new Integer(score[i])); // set.add(score[i]); 오토박싱 자동변환

System.out.println("50보다 작은 값: " + set.headSet(new Inteher(50))); // [10, 35, 45]
System.out.println("50보다 큰 값: " + set.tailSet(50)); // [50, 65, 80, 95, 100]

 

TreeSet() // Comparable(기본 비교기준)
TreeSet(Collection c)
TreeSet(Comparator comp) // 주어진 정렬조건으로 정렬하는 TreeSet 생성
TreeSet(SortedSet s)
boolean add(Object o)
boolean addAll(Collection c)
Object ceiling(Object o) // 지정된 객체와 같은 객체, 없으면 큰 값 반환
Object floor(Object o) // 지정된 객체와 같은 객체, 없으면 작은 값 반환
void clear()
Object clone()
Comparator comparator() // 정렬기준을 반환
boolean contains(Object o)
boolean containsAll(Collection c)
NavigableSet descendingSet() // 역순 정렬 반환
Object first() // 오름차순 제일 작은 값 반환
Object last() // 오름차순 제일 큰 값 반환
SortedSet headSet(Object toElement) // 지정된 객체보다 작은 값 객체들 반환
SortedSet tailSet(Object fromElement) // 지정된 객체보다 큰 값의 객체들 반환
Object higher(Object o) // 지정된 객체보다 큰 값 반환
Object lower(Object o) // 지정된 객체보다 작은 값 반환
boolean isEmpty()
Iterator iterator()
Object pollFirst() // 제일 작은 값의 객체 반환
Object pollLast() // 제일 큰 값의 객체 반환
boolean remove(Object o)
boolean retainAll(Collection c) // 교집합
int size()
Spliterator spliterator()
SortedSet subSet(Object fromElement, Object toElement) // 범위 검색의 결과 반환
Object[] toArray()
Object[] toArray(Object[] a)

 

 

5. 트리 순회(tree traversal)

- 이진 트리의 모든 노드를 한 번씩 읽는 것

- 전위순회(preorder), 후위순회(postorder), 중위순회(inorder), 레벨순회

- 중위순회하면 오름차순으로 정렬