Set

황상익·2024년 6월 25일

Inflearn JAVA

목록 보기

38/61

자바가 제공하는 Set1

셋은 중복을 허용하지 않고, 순서를 보장하지 않는 자료 구조이다

컬랙션 프레임워크 Set

HashSet

구현 : 해시 자료 구조를 사용해서 요소를 저장
순서 : 요소들은 특정한 순서 없이 저장. 요소를 추가한 순서를 보장 X
시간 복잡도 : 주요 연산(추가, 삭제, 검색)은 평균적으로 O(1) 시간 복잡도를 가진다.

LinkedHashSet

구현 : 연결 리스트를 추가해서 요소들의 순서를 유지한다.
순서 : 요소들은 추가된 순서 유지
시간 복잡도 : : LinkedHashSet 도 HashSet 과 마찬가지로 주요 연산에 대해 평균 O(1) 시간 복잡도를 가진다

LinkedHashSet 은 HashSet 에 연결 링크만 추가한 것이다.
HashSet 에 LinkedList 를 합친 것으로 이해

head 부터 순서대로 링크를 따라가면 입력 순서대로 데이터를 순회 가능
양방향 연결

TreeSet

구현 : TreeSet은 이진 탐색 트리를 개선한 레드 블랙 트리를 내부에서 사용
순서 : 정렬된 순서로 저장, 순서의 기준은 Comparator로 변경 가능
시간 복잡도 : 은 O(log n) 의 시간 복잡도를 가진다. HashSet보다는 느리다.

트리는 부모노드와 자식 노드로 구성
가장 높은 조상을 루트
자식이 2개까지 올 수 있는 트리를 이진 트리
노드의 왼쪽 자손은 더 작은 값을 갖고, 오른쪽 자손은 더 큰 값을 갖는 것

이진 트리 검색

1번: 루트인 20과 35를 비교한다. 35가 더 크므로 오른쪽으로 찾아간다.
2번: 40과 35를 비교한다. 35가 더 작으므로 왼쪽으로 찾아간다.
3번: 30과 35를 비교한다. 35가 더 크므로 오른쪽으로 찾아간다.
4번: 노드에 있는 값을 비교한다. 35와 같으므로 35를 찾는다

이진 탐색 트리 계산의 핵심은 한번에 절반을 날린 다는 점

이진 트리 탐색의 빅오

이진 탐색 트리와 성능
검색 삽입 삭제 평균 성능은 O(log n) 이다. 하지만 트리의 균형이 맞지 않으면 최악의 경우 O(n)의 성능이 나온다.
오른쪽으로 치우치게 되면, 결과적으로 15를 검색 했을 때 데이터의 수인 5만큼 검색을 해야 한다.

이진 탐색 트리 개선
트리의 균형이 너무 깨진 경우 동적으로 균형을 다시 맞추는것이다.AVL 트리, 레드-블랙 트리 같은 균형을 맞추는 다양한 알고리즘이 존재한다.
자바의 TreeSet 은 레드-블랙 트리를 사용해서 균형을 지속해서 유지한다. 따라서 최악의 경우에도 O(logn) 의 성능을 제공한다

이진 탐색 트리 - 순회
데이터의 값을 기준으로 정렬해서 보관서 정렬된 순서로 데이터를 차례로 조회할 수 있다. (순회 할 수 있다.)

중위 순회 순서
자신의 왼쪽의 모든 노드를 처리하고, 자신의 노드를 처리하고, 자신의 오른쪽 모든 노드를 처리하는 방식이다

자바가 제공하는 Set3

public class JavaSetMain {
    public static void main(String[] args) {
        run(new HashSet<>()); //O(1)
        run(new LinkedHashSet<>());// o(1)
        run(new TreeSet<>());//logN
    }

    private static void run(Set<String> set) {
        System.out.println("set.getClass() = " + set.getClass());
        set.add("C");
        set.add("B");
        set.add("A");
        set.add("1");
        set.add("2");

        Iterator<String> iter = set.iterator();
        while (iter.hasNext()){ //다음 데이터가 있는지 확인
            System.out.print(iter.next() + " "); // 다음 데이터 반환
        }
        System.out.println();
    }
}