TreeSet

TreeSet : 범위 탐색, 정렬

• 이진 탐색 트리(binary search tree)로 구현. 범위 탐색(from~to)과 정렬에 유리
• 이진 트리는 모든 노드가 최대 2개(0~2)의 하위 노드를 가짐
  ↳ 각 요소(node)가 나무(tree) 형태로 연결(LinkedList(1개씩 연결)의 변형)
  

class TreeNode {
	TreeNode left;   // 왼쪽 자식 노드
    Object element;  // 저장할 객체
    TreeNode right;  // 오른쪽 자식 노드

이진 탐색 트리(binary search tree) ?

• 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장 (일반 이진트리와 다른 점)
• 단점 : 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림 (비교 횟수 증가)

TreeSet - 데이터 저장 과정

: boolean add(Object o)
→ HashSet은 equals(), hashCode()로 비교하고 TreeSet은 compare()를 호출해서 비교

• TreeSet에 7,4,9,1,5의 순서로 데이터를 저장하면, 아래의 과정을 거친다.
  ( 루트부터 트리를 따라 내려가며 값을 비교. 작으면 왼쪽, 크면 오른쪽에 저장)
  

주요 생성자 & 메소드

↳ 이진 탐색트리로 데이터를 저장해놓으면 범위 검색에 유리하다.(유용한 메소드를 가지고 있음)

참고

• 트리 순회(tree traversal)
  : 이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.
  
  ↳ 중위순회한 것을 쭉 읽으면 오름차순으로 정렬된 결과를 볼 수 있음.

∴ TreeSet

• 장점 : 정렬, 범위검색에 유리
• 단점 : 추가, 삭제에 시간이 오래 걸림

출처

• 자바의 정석 기초편 : ch11- 39~41, 42~45