자바의 정석을 통해 공부한 내용을 요약하였습니다.

TreeSet

1. 특징

• 이진 검색 트리(binary search tree) 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다.
• 정렬, 검색, 범위 검색에 높은 성능을 보이는 자료구조이다.

1-2. 이진 검색 트리(binary search tree)

• 이진 트리(binary tree)는 Linked List처럼 여러 개의 node가 서로 연결된 구조로 각 node에 최대 2개의 node를 연결할 수 있으며 root라고 불리는 node에서 부터 계속 확장해 나갈 수 있다.

class TreeNode {
	TreeNode left;  //왼쪽 자식 노드
        Object element;  // 객체를 저장하기 위한 참조 변수
        TreeNode right;  // 오른쪽 자식 노드
}

• 코드로 표현하면 위와 같다.

• 이진 검색 트리(binary search tree)는 왼쪽에는 부모노드의 값보다 작은 값의 자식노드를, 오른쪽에는 큰 값의 자식노드를 저장하는 이진 트리이다.
• 위와 같이 트리를 구성하게 되면 왼쪽 마지막 레벨이 제일 작은 값이 되고 오른 쪽 마지막 레벨의 값은 제일 큰 값이 된다.
• 그러나 컴퓨터는 알아서 값을 비교하지 못하기 때문에 기준이 필요하다.
  TreeSet에 저장되는 객체가 Comparable을 구현하거나 TreeSet에게 Comparator를 제공하여 두 객체를 비교할 기준을 알려주어야 한다.
• 저장된 값의 개수에 비례해서 검색시간이 증가하지만 검색 효율이 뛰어난 자료구조이다.
  즉, 노드의 추가 및 삭제에 시간이 걸리지만 검색과 정렬에는 유리하다.
• TreeSet은 값을 저장할 때 이미 정렬이 되어있어 별도의 정렬작업이 필요없다.
  
  
  

2. 메서드

2-1. 생성자

• TreeSet() - 기본 생성자, 주어진 객체의 Comparable 사용
• TreeSet(Comparator comp) - 주어진 정렬조건으로 정렬하는 TreeSet 생성

2-2. TreeSet 고유 메서드

• Object ceiling(Object o) - 지정된 객체와 같은 객체를 반환, 지정된 객체가 없다면 지정된 객체보다 큰 값 중 가장 가까운 값의 객체를 반환, 없으면 null(올림)
• Object floor(Object o) - 지정된 객체와 같은 객체를 반환, 지정된 객체가 없다면 지정된 객체보다 작은 값 중 가장 가까운 값의 객체를 반환, 없으면 null(내림)
• SortedSet headSet(Object toElement) - 지정된 객체보다 작은 값의 객체들을 반환(범위 검색)
• SortedSet tailSet(Object fromElement) - 지정된 객체보다 큰 값의 객체들을 반환(범위 검색)
• SortedSet subSet(Object fromElement, Object toElement) - fromElement와 toElement사이의 결과를 반환(범위 검색)