알고리즘 문제를 풀다가 TreeSet 을 처음 접하게 되어 기록한다.

TreeSet

TreeSet은 정렬된 집합(Set)이다.

내부는 Red-Black Tree 를 사용하여 원소를 정렬 상태로 유지한다.

• add/remove/contains 가 O(log n)
• floor, celling, higher, lower 도 O(log n)

중복은 자동 제거되며, 삽입 순서는 보장하지 않고 정렬 순서만 보장하는 Set 의 성질을 가지고 있다.

Red-Black Tree

TreeSet 은 이진탐색 트리 중 레드-블랙 트리로 구현되어 있다.

이진 탐색 트리의 문제점

이진 탐색 트리는 트리의 높이만큼 시간이 걸린다.
데이터의 값이 트리에 잘 분산되어지면 빠르지만 한쪽으로 치우쳐지면 비효율적이다.
이 문제를 해결하기 위해 "Red-Black Tree"가 등장한다.

동작 방식

Red-Black Tree 는 부모 노드보다 작은 값을 가지는 값은 왼쪽, 큰 값은 오른쪽으로 배치한다.
추가나 삭제 시, 균형을 맞추도록 설계되어 있다.

선언 방식

TreeSet<Integer> treeSet = new TreeSet<Integer>();

• TreeSet 을 생성하기 위해서는 저장할 객체 타입을 파라미터로 표기하고 기본 생성자를 호출하면 된다.
• 생성 시, 크기 선언은 불가능하다.

값 추가

treeSet.add(1);

값 삭제

treeSet.remove(1);

모두 삭제

treeSet.clear();

TreeSet vs HashSet vs LinkedHashSet

Set	정렬	평균 조회	순서
HashSet	없음	O(1)	없음
LinkedHashSet	없음	O(1)	삽입 순서 유지
TreeSet	정렬(오름차순/사용자 정의)	O(log n)	정렬 순서

• 정렬이 필요 없으면 HashSet / LinkedHashSet 이 더 적합
• 정렬 + 범위 / 근접 탐색이 필요하면 TreeSet이 더 적합