1. 자바가 제공하는 Set
Set 자료 구조
- 셋은 중복을 허용하지 않고, 순서를 보장하지 않는 자료구조
컬렉션 프레임워크 - Set
Collection 인터페이스
Collection인터페이스는java.util패키지의 컬렉션 프레임워크의 핵심 인터페이스 중 하나- 이 인터페이스는 자바에서 다양한 컬렉션, 즉 데이터 그룹을 다루기 위한 메서드를 정의함
- Collection 인터페이스는
List,Set,Queue와 같은 다양한 하위 인터페이스와 함께 사용되며, 이를 통해 데이터를 리스트, 세트, 큐 등의 형태로 관리할 수 있음
Set 인터페이스
- 자바의
Set인터페이스java.util패키지의 컬렉션 프레임워크에 속하는 인터페이스 중 하나 Set인터페이스는 중복을 허용하지 않는 유일한 요소의 집합을 나타냄- 즉, 어떤 요소도 같은
Set내에 두 번 이상 나타날 수 없음
- 즉, 어떤 요소도 같은
Set은 수학적 집합 개념을 구현한 것으로, 순서를 보장하지 않으며, 특정 요소가 집합에 있는지 여부를 확인하는데 최적화되어 있음
Set인터페이스는HashSet,LinkedListSet,TreeSet등의 여러 구현 클래스를 가지고 있으며, 각 클래스는Set인터페이스를 구현하며 각가의 특성을 가지고 있음
Set 인터페이스의 주요 메서드
1) HashSet
-
구현 : 해시 자료 구조를 사용해서 요소를 저장
-
순서 : 요소들은 특정한 순서 없이 저장됨
- 즉, 요소를 추가한 순서를 보장하지 않음
-
시간 복잡도 :
HashSet의 주요 연산(추가, 삭제, 검색)은 평균적으로O(1)시간 복잡도를 가짐 -
용도 : 데이터의 유일성만 중요하고, 순서가 중요하지 않은 경우에 적합함
2) LinkedHashSet
-
구현 :
LinkedHashSet은HashSet에 연결 리스트를 추가해서 요소들의 순서를 유지 -
순서 : 요소들은 추가된 순서대로 유지됨
- 즉, 순서대로 조회 시 요소들이 추가된 순서대로 반환됨
-
시간 복잡도 :
LinkedHashSet도HashSet과 마찬가지로 주요 연산에 대해 평균O(1)시간 복잡도를 가짐 -
용도 : 데이터의 유일성과 함께 삽입 순서를 유지해야 할 때 적합함
-
참고 : 연결 링크를 유지해야 하기 때문에
HashSet보다는 조금 더 무거움
- LinkedHashSet은 HashsSet에 연결 링크만 추가한 것임
- HashSet에 LinkedList를 합친 것으로 이해하면 됨
- 이 연결 링크는 데이터를 입력한 순서대로 연결됨
- head(first)부터 순서대로 링크를 따라가면 입력 순서대로 데이터를 순회할 수 있음
- 양방향으로 연결됨
- 여기서는 1, 2, 5, 8, 14, 99 순서대로 입력됨
3) TreeSet
-
구현 :
TreeSet은 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용함 -
순서 : 요소들은 정렬된 순서로 저장됨
- 순서의 기준은 비교자(
Comparator)로 변경할 수 있음 - 비교자는 뒤에서 다룸
- 순서의 기준은 비교자(
-
시간 복잡도 : 주요 연산들은
O(log n)의 시간 복잡도를 가짐- 따라서
HashSet보다는 느림
- 따라서
-
용도 : 데이터들을 정렬된 순서로 유지하면서 집합의 특성을 유지해야 할 때 사용함
- 예를 들어, 범위 검색이나 정렬된 데이터가 필요한 경우에 유용함
- 참고로 입력된 순서가 아니라 데이터 값의 순서임
- 예를 들어 3, 1, 2를 순서대로 입력해도 1, 2, 3 순서로 출력됨
트리구조
- 트리는 부모 노드와 자식 노드로 구성됨
- 가장 높은 조상을 루트(
root)라 함 - 자식이 2개까지 올 수 있는 트리를 이진 트리라 함
- 여기에 노드의 왼쪽 자손은 더 작은 값을 가지고, 오른쪽 자손은 더 큰 값을 가지는 것을 이진 탐색 트리라 함
TreeSet은 이진 탐색 트리를 개선한 레드-블랙 트리를 사용함
트리 구조의 구현
class Node {
Object item;
Node left;
Node right;
}- 트리 구조는 왼쪽, 오른쪽 노드를 알고 있으면 됨
이진 탐색 트리 - 입력 예시
- 이진 탐색 트리의 핵심은 데이터를 입력하는 시점에 정렬해서 보관한다는 점임
- 그리고 작은 값은 왼쪽에, 큰 값은 오른쪽에 저장하면 됨
- (아래 예시) 데이터를 10, 5, 15, 1, 6, 11, 16 순서대로 입력한다고 가정
- 처음에 10을 입력했다고 가정하고, 다음으로 5, 15를 입력함
- 5는 10보다 작으므로 왼쪽에 저장함
- 15는 10보다 크므로 오른쪽에 저장됨
- 1은 10보다 작아서 왼쪽, 1은 5보다 작아서 왼쪽
- 6은 10보다 작아서 왼쪽, 6은 5보다 커서 오른쪽
- 11은 10보다 크므로 오른쪽, 11은 15보다 작으므로 왼쪽
- 16은 10보다 크므로 오른쪽, 16은 15보다 크므로 오른쪽
이진 탐색 트리 - 검색
-
여기에는 총 15개의 데이터가 들어있음
-
여기서 숫자 35를 검색한다고 가정해보자
- 1번 : 루트인 20과 35를 비교한다. 35가 더 크므로 오른쪽으로 찾아간다.
- 2번 : 40과 35를 비교한다. 35가 더 작으므로 왼쪽으로 찾아간다.
- 3번 : 30과 35를 비교한다. 35가 더 크므로 오른쪽으로 찾아간다.
- 4번 : 노드에 있는 값을 비교한다. 35와 같으므로 35를 찾는다.
- 데이터가 총 15개인데 4번의 계산으로 필요한 결과를 얻을 수 있었음
- 이는
O(n)인 리스트의 검색보다는 빠르고,O(1)인 해시의 검색 보다는 느림- 리스트의 경우
O(n)이므로 15번의 연산이 필요함- 해시 검색은
O(1)이므로 1번의 연산이 필요함
-
이진 탐색 트리 계산의 핵심은 한 번에 절반을 날린다는 점
-
계산을 단순화 하기 위해 16개의 데이터가 있다고 가정
-
16개의 데이터가 있다. 루트에서 처음 비교를 통해 절반의 데이터를 찾지 않아도 된다. 따라서 16 / 2 = 8이 된다.
-
8개의 데이터가 있다. 비교를 통해 절반의 데이터만 남는다. 따라서 8 /2 = 4가 된다.
-
4개의 데이터가 있다. 비교를 통해 절반의 데이터만 남는다. 따라서 4 / 2 = 2가 된다.
-
2개의 데이터가 있다. 비교를 통해 절반의 데이터만 남는다. 따라서 2 / 2 = 1이 된다.
-
1이 남았으므로 이 값이 맞는지 확인하면 된다
-
이진 탐색 트리의 빅오 - O(log n)
-
16개의 경우 단 4번의 비교 만으로 최종 노드에 도달할 수 있음
- 2개의 데이터 2로 1번 나누기,
log₂(2)=1 - 4개의 데이터 2로 2번 나누기,
log₂(4)=2 - 8개의 데이터 2로 3번 나누기,
log₂(8)=3 - 16개의 데이터 2로 4번 나누기,
log₂(16)=4 - 32개의 데이터 2로 5번 나누기,
log₂(32)=5 - 64개의 데이터 2로 6번 나누기,
log₂(64)=6 - 1024개의 데이터 2로 10번 나누기,
log₂(1024)=10
- 2개의 데이터 2로 1번 나누기,
-
1024개의 데이터를 단 10번의 계산으로 원하는 결과를 찾을 수 있음
-
데이터의 크기가 늘어나도 늘어난 만큼 한 번의 계산에 절반을 날려버리기 때문에,
O(n)과 비교해서 데이터의 크기가 클수록 효과적임 -
이것을 수학으로
log₂(n)으로 표현함 -
빅오 표기법으로 나타내면 O(log n)로 표현함
이진 탐색 트리와 성능
- 이진 탐색 트리의 검색, 삽입, 삭제의 평균 성능은
O(log n) - 하지만 트리의 균형이 맞지 않으면 최악의 경우
O(n)의 성능이 나옴 - 만약 데이터를 1, 5, 6, 10, 15 순서로 입력했다고 가정
- 이렇게 오른쪽으로 치우치게 되면, 결과적으로 15를 검색했을 때 데이터의 수인 5만큼 검색을 해야 함
- 따라서 이런 최악의 경우
O(n)이 성능이 나옴
이진 탐색 트리 개선
- 이런 문제를 해결하기 위해선 다양한 해결 방안이 있는데 트리의 균형이 너무 깨진 경우 동적으로 균형을 다시 맞추는 것임
- 앞서 중간에 있는 6을 기준으로 다시 정렬함
- AVL 트리, 레드-블랙 트리 같은 균형을 맞추는 다양한 알고리즘이 존재함
- 자바의
TreeSet은 레드-블랙 트리를 사용해서 균형을 지속해서 유지함 - 따라서 최악의 경우에는
O(log n)의 성능을 제공함
이진 탐색 트리 - 순회
- 이진 탐색 트리의 핵심은 입력 순서가 아니라, 데이터의 값을 기준으로 정렬해서 보관한다는 점
- 따라서 정렬된 순서로 데이터를 차례로 조회할 수 있음(순회 할 수 있음)
- 데이터를 차례로 순회하려면 중위 순회라는 방법을 사용하면 됨
- 왼쪽 서브트리를 방문한 다음, 현재 노드를 처리하고, 마지막으로 오른쪽 서브트리를 방문함
- 이 방식은 이진 탐색 트리의 특성상, 노드를 오름차순(숫자가 점점 커짐)으로 방문함
중위 순회 순서
- 쉽게 이야기해서 자신의 왼쪽의 모든 노드를 처리하고, 자신의 오른쪽 모든 노드를 처리하는 방식
- 순서대로 1, 5, 6, 10, 11, 15, 16이 출력된 것을 확인할 수 있음
예제
package collection.set.javaset;
import java.util.*;
public class JavaSetMain {
public static void main(String[] args) {
run(new HashSet<>());
run(new LinkedHashSet<>());
run(new TreeSet<>());
}
private static void run(Set<String> set) {
System.out.println("set = " + set.getClass());
set.add("C");
set.add("B");
set.add("A");
set.add("1");
set.add("2");
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println();
}
}-
HashSet,LinkedList,TreeSet모두Set인터페이스를 구현하기 때문에 구현체를 변경하면서 실행할 수 있음 -
iterator()를 호출하면 컬렉션을 반복해서 출력할 수 있음iterator.hashNext(): 다음 데이터가 있는지 확인iterator.next(): 다음 데이터를 반환함
실행결과
set = class java.util.HashSet
A 1 B 2 C
set = class java.util.LinkedHashSet
C B A 1 2
set = class java.util.TreeSet
1 2 A B C HashSet: 입력한 순서를 보장하지 않음LinkedHashSet: 입력한 순서를 정확히 보장함TreeSet: 데이터 값을 기준으로 정렬함
