TreeSet

자바의 정석[기초편]으로 공부한 내용을 정리한 글입니다.

 

TreeSet의 개념과 구조 이해

TreeSet이란?

• TreeSet은 Java에서 제공하는 Set 컬렉션 중 하나로, 정렬된 순서로 데이터를 저장합니다.
• 내부적으로 이진 탐색 트리(Binary Search Tree) 구조를 사용합니다.
  • 이진 탐색 트리는 각 노드가 최대 2개의 자식 노드만 가지며,
    • 왼쪽에는 부모보다 작은 값,
    • 오른쪽에는 부모보다 큰 값을 저장합니다.

이진 탐색 트리(Binary Search Tree)

• 한 노드는 최대 두 개의 자식 노드를 가짐
• 값의 크기를 기준으로 왼쪽 자식(작은 값), 오른쪽 자식(큰 값)에 저장
• 노드 연결은 LinkedList처럼 포인터로 연결되어 있음
  (TreeNode left, TreeNode right)

일반적인 연결 구조와의 차이

일반적인 연결 리스트(LinkedList)는 next를 통해 한 방향으로만 연결되어 있음.

class Node {
    Node next;
    Object obj;
}

 

반면, TreeSet의 트리 노드는 left, right 포인터를 통해 양방향(좌/우) 자식으로 뻗어나가는 구조입니다.

class TreeNode {
    TreeNode left;      // 왼쪽 자식
    Object element;     // 저장된 객체
    TreeNode right;     // 오른쪽 자식
}

 

이진 탐색 트리 구조 시각화

      A
     / \
    B   C

• A가 부모 노드(root),
• B, C는 각각 왼쪽/오른쪽 자식 노드이며,
• 자식은 부모보다 작은 값/큰 값을 기준으로 배치됩니다.

 

TreeSet에 데이터가 저장되는 과정

저장 시 규칙

• 새로운 데이터를 TreeSet에 저장하면,
  • 기존 데이터와 비교(compare) 를 하여,
  • 작으면 왼쪽으로,
  • 크면 오른쪽으로 내려가며 적절한 위치를 찾아 저장합니다.
• 이때 중복된 값은 저장하지 않습니다.

 

예시: 데이터 7, 4, 9, 1, 5를 TreeSet에 순서대로 저장하면?

① 7 저장:

• 트리가 비어 있으므로, 루트 노드에 저장됨.

7

② 4 저장:

• 4 < 7 → 왼쪽 자식으로 저장

 

      7
     /
    4

③ 9 저장:

• 9 > 7 → 오른쪽 자식으로 저장

      7
     / \
    4   9

④ 1 저장:

• 1 < 7 → 왼쪽
• 1 < 4 → 왼쪽 → 1을 4의 왼쪽 자식으로 저장

      7
     / \
    4   9
   /
  1

⑤ 5 저장:

• 5 < 7 → 왼쪽
• 5 > 4 → 오른쪽 → 5를 4의 오른쪽 자식으로 저장

      7
     / \
    4   9
   / \
  1   5

이처럼 TreeSet은 자동으로 정렬되며, 비교 연산을 통해 노드의 위치를 결정합니다.

 

 

 

 

 

TreeSet 주요 생성자 & 메서드

생성자 종류

TreeSet()	기본 생성자 (저장되는 객체는 Comparable을 구현해야 함)
TreeSet(Collection c)	주어진 컬렉션의 요소를 TreeSet에 저장
TreeSet(Comparator comp)	사용자 지정 정렬 기준으로 저장 (기본 비교 기준을 덮어씀)

TreeSet 주요 메서드 요약

add() / remove()	데이터 추가 및 삭제
size() / isEmpty()	크기 확인 / 비어있는지 확인
iterator()	요소 반복 접근용 이터레이터 반환
first() / last()	가장 작은 값 / 가장 큰 값 반환
ceiling(x)	x 이상 중 가장 가까운 값
floor(x)	x 이하 중 가장 가까운 값
higher(x)	x보다 큰 값 중 가장 가까운 값
lower(x)	x보다 작은 값 중 가장 가까운 값
subSet(from, to)	from 이상 to 미만 범위 값 반환
headSet(to)	to 미만의 값 반환
tailSet(from)	from 이상의 값 반환

 

 

범위 검색 메서드 설명

🔹 subSet(from, to)

• from 이상, to 미만의 값들을 반환
• 예: subSet(30, 80) → 30 이상, 80 미만 값만 추출됨

🔹 headSet(to)

• to보다 작은 값들을 반환
• 예: headSet(50) → 50보다 작은 값들만 반환

🔹 tailSet(from)

• from보다 큰 값들 반환
• 예: tailSet(50) → 50 이상 값들 반환

 

Tree Traversal (트리 순회)

TreeSet은 트리 구조를 가지고 있기 때문에, 다양한 순회 방식으로 데이터를 읽을 수 있습니다.

🔹 전위 순회 (Pre-order)

• 루트 → 왼쪽 → 오른쪽
• 노드 생성 순서처럼 방문

🔹 중위 순회 (In-order)

• 왼쪽 → 루트 → 오른쪽
• 값을 오름차순으로 정렬한 결과가 됨 → TreeSet의 특징

🔹 후위 순회 (Post-order)

• 왼쪽 → 오른쪽 → 루트

🔹 레벨 순회 (Level-order)

• 트리의 층을 기준으로 순서대로 읽음

예시 트리의 중위 순회 결과:

[10, 35, 45, 50, 65, 80, 95, 100]

→ TreeSet을 중위 순회하면 정렬된 상태 그대로 값을 얻을 수 있습니다.

 

정리 및 TreeSet 단점

장점

• 자동 정렬
• 범위 검색에 유리 (subSet, headSet, tailSet 등)
• 중복 제거 기능 포함

단점

• 구조상 노드 탐색 비교가 반복되므로
  추가/삭제 시 시간이 많이 걸릴 수 있음
  • 최악의 경우 O(n)
  • 일반적 평균은 O(log n)