[JAVA]TreeSet

 

TreeSet
: Set인터페이스 중 탐색과 정렬에 유리한 구현클래스.

이진탐색트리. 뒤집으면 나무 모양 같아서 트리라한다.

• 중복❌
• 이진 탐색 트리Binary search tree로 구현되었다.
  → 장점 : 그래서 빠른 탐색이 빠르다.
  
  
• 이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖는다.
  
  
• 단점 : 데이터가 많아질 수록 추가/삭제에 (비교횟수증가로) 시간이 오래 걸린다.

💡 이진 탐색 트리 Binary search tree

부모보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 저장한다.
따라서 값이 추가/삭제 될 때마다 정렬을 다시 한다.

노드를 이용한다는 점에서 LinkedList와 비슷하다.

2024.11.19 - [☕ 자바 JAVA/☕ 변수와 자료형 Variables & Data Type] - [JAVA]LinkedList와 Queue

LinkedList의 노드는 양옆에 노드를 1개씩 연결하지만 트리셋은 최대 2개까지 가질 수 있다.

• 결론적으로 트리셋은 이진탐색트리 형태로 저장되기에, 추가/삭제가 오래 걸린다.
  정렬된 상태로 유지되기에 검색에는 O(log n)의 시간 복잡도로 빠르다.
  → 중복이 없고 추가/삭제할 일이 별로 없고 검색은 빨라야하는 경우 유용하다.

 

---

 

HashSet과 TreeSet의 차이

TreeSet에 난수를 담았을 경우. 정렬되어 있다.

 

HashSet에 난수를 담았을 경우. 정렬되어 있지 않다.

 

---

 

생성자

• new TreeSet(Comparator comp) 가 원래는 필수있데 만약 없다면, comparable의 compareTo()를 정렬기준으로 한다.
  
  

Test클래스를 Comparable로 형변환 할 수 없다고 에러가 뜬다.

 

❗  정렬기준을 지정하려면 위와 같이

2024.11.23 - [☕ 자바 JAVA/☕ 클래스와 함수 Class & Method] - [JAVA]Comparator와 Comparable

저장하는 객체 또는 set생성자 안에, 정렬 인터페이스 comparator 혹은 comparable을 상속 받아 사용해야 한다.

 

---

 

메서드

2024.11.19 - [☕ 자바 JAVA/☕ 변수와 자료형 Variables & Data Type] - [JAVA]ArraList

add(), size(), remove(), isEmpty() 등은 collection의 메서드로 ArrayList에서 적은 방법과 동일하다.

 

• first() : 정렬된 순서에서 첫번째를 반환.
  
  
• last() : 정렬된 순서에서 마지막을 반환.
  
  
• ceiling(Object o) : 같은 값이 있으면 같은 객체 반환. 없으면 큰 값 중에 가장 가까운 값을 반환. 아예 없으면 null.
  
  
• floor(Object o) : 같은 값이 있으면 같은 객체 반환. 없으면 작은 값 중에 가장 가까운 값을 반환. 아예 없으면 null.
  
  
• higher(Object o) : 지정 객체보다 큰 값 중 제일 가까운 값 반환. 없으면 null.
  
  
• lower(Object o) : 지정 객체보다 작은 값 중 제일 가까운 값 반환. 없으면 null.
  
  
• SortedSet subSet(fromElement, toElement) : 지정된 범위를 SortedSet으로 반환.
  
  
• SortedSet headSet(Object toEement) : 지정한 객체보다 작은 값들을 SortedSet 으로 반환.
  
• SortedSet tailSet(Object fromEement) : 지정한 객체보다 큰 값들을 SortedSet 으로 반환.
  
  

---

sudSet() 예시

출력결과

• set.subSet(from, to);
  → ("b", "d") b에서 d(전)까지 범위를 반환햇다.
  
  
• set.subSet("b", "d" + "zzz");
  → b에서 dzzz까지 범위가 반환되었다.

---

예시2

출력결과

 

---

💡 트리 순회 Tree Traversal
이진 트리의 모든 노드를 한번씩 읽는 것을 말한다.

※ 같은 층에 있는 노드들을 읽는 것을 레벨순회라고 한다.

 

---

참조영상