TreeSet

tryoo0607·2025년 7월 29일

Java 알고리즘 자료구조

Java - 알고리즘/자료구조

목록 보기

1/10

들어가며

알고리즘 공부 중에 새롭게 알게 된 자료구조인 TreeSet에 대해 정리했습니다.

TreeSet

TreeSet은 기본적으로 Set인 만큼 다음 특징을 가지고 있습니다.

중복을 허용하지 않는다.

순서가 보장되지 않는다.

그러나 HashSet과 다르게 다음 특징을 가집니다.

자동으로 정렬이 된다. (오름차순, 내림차순)

추가와 삭제에 HashSet보다 시간이 걸린다.

정렬, 검색에서 높은 성능을 보인다.

TreeSet이 정렬, 검색에서 높은 성능을 가지는 것은 이진 탐색 트리 구조로 이루어져 있기 때문 이며, 그 중에서도 성능을 향상 시킨 레드-블랙 트리로 구현되어 있기 때문이다.

이진 트리 (Binary Tree)

각 노드가 최대 두개 값을 가지는 트리를 의미합니다.

부모와 자식의 요소가 같더라도 노드 위치가 왼쪽과 오른쪽으로 다르면 두 트리는 다른 트리가 됩니다.

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리는이진 트리 기반의 탐색을 위한 자료구조입니다. 이진 탐색 트리는 이진 트리 중 다음의 특징을 가지고 있는 트리입니다.

노드의 하위 노드 중 왼쪽의 키는 반드시 부모보다 작아야한다.
정확히는 왼쪽의 서브 트리는 반드시 부모 노드보다 작아야한다.
즉, 왼쪽 아래에 위치한 모든 노드는 부모보다 작다.

노드의 하위 노드 중 오른쪽의 키는 반드시 부모보다 커야한다.
정확히는 오른쪽의 서브 트리는 반드시 부모 노드보다 커야한다.
즉, 오른쪽 아래에 위치한 모든 노드는 부모보다 크다.

왼쪽, 오른쪽 하위 트리도 각각 이진 검색 트리여야 함

중복된 키를 허용하지 않는다.

레드-블랙 트리(Red-Black Tree)

TreeSetImage

균형 이진 탐색 트리의 한 종류입니다. 트리의 균형을 유지하면서도 탐색, 삽입, 삭제 등의 연산을 O(log n)의 시간 복잡도를 보장하는 자료구조입니다.

만약 삽입이나 삭제가 특정 방향(왼쪽 또는 오른쪽)으로만 반복되면,
트리가 한쪽으로 편향된 구조가 되면서 탐색 깊이가 깊어지고,
결국 성능이 O(log n)에서 O(n)으로 급격히 저하됩니다.

이런 구조는 사실상 연결 리스트와 유사하며,
값을 탐색할 때 매번 한 방향으로 끝까지 내려가야 하기 때문에 느려집니다.

트리가 편향되는 것을 방지하기 위해, 루트가 고정될 필요는 없으며
삽입 또는 삭제 시 노드의 위치를 재배치하거나
회전(Rotation) 등의 연산을 통해 트리의 높이를 줄이고 좌우 균형을 유지할 수 있습니다. 이게 Red-Black Tree의 핵심 동작입니다.

결과적으로 다음 효과를 얻습니다.

노드 탐색에 필요한 깊이가 줄어들게 된다

트리 전체가 더 평평하고 균형 잡힌 구조가 된다

삽입/삭제/탐색 모두 일관된 O(log n) 성능을 유지하게 된다

TreeSet을 고려해야할 때

1. 정렬된 순서가 필요한 경우

TreeSet은 자동으로 요소를 오름차순으로 정렬합니다.
최소값, 최대값을 자주 조회하거나 정렬된 순서로 순회할 때 유리합니다.

2. 범위 조회(Range Query)가 필요한 경우'

subSet(), headSet(), tailSet() 등으로 특정 범위의 값들을 효율적으로 조회할 수 있습니다.
HashSet에서는 직접 필터링해야 하므로 TreeSet이 훨씬 효율적입니다.

메서드	설명
`subSet(fromElement, toElement)`	`fromElement` 이상, `toElement` 미만 범위의 값들을 반환
`headSet(toElement)`	`toElement` 미만의 모든 값 반환
`tailSet(fromElement)`	`fromElement` 이상의 모든 값 반환

3. 탐색 기반 연산이 필요한 경우

TreeSet은 lower(), higher(), ceiling(), floor() 등의 탐색 메서드를 제공합니다.
이진 탐색 기반으로 빠르게 인접한 값들을 찾을 수 있습니다.

메서드	설명
`lower(E e)`	지정한 값 보다 작은 가장 큰 값 (바로 아래) 반환
`higher(E e)`	지정한 값 보다 큰 가장 작은 값 (바로 위) 반환
`floor(E e)`	지정한 값 이하 중 가장 큰 값 (같거나 아래) 반환
`ceiling(E e)`	지정한 값 이상 중 가장 작은 값 (같거나 위) 반환

4. 안정적인 성능이 필요한 경우

TreeSet은 삽입, 삭제, 탐색 연산에서 항상 O(log n)의 성능을 보장합니다.
HashSet은 평균적으로 O(1)이지만 해시 충돌이 많을 경우 O(n)까지 느려질 수 있습니다.

조건	설명
항상 예측 가능한 성능	TreeSet은 내부적으로 Red-Black Tree(균형 이진 탐색 트리)를 사용함
삽입, 삭제, 탐색 모두 O(log n)	모든 연산이 트리 구조 덕분에 최악의 경우에도 O(log n) 성능 보장
HashSet은 평균 O(1)지만 불안정	해시 충돌이 많아지면 HashSet은 최악의 경우 O(n)까지 느려질 수 있음
일관된 응답 시간	TreeSet은 데이터의 분포나 순서와 상관없이 항상 일정한 시간에 동작함