자바의 정석 기초편

0. 목차

Chapter11. 컬렉션 프레임웍

Ch11 - 39. TreeSet

Ch11 - 40. 이진 탐색 트리(binary search tree)

Ch11 - 41. 이진 탐색 트리의 저장 과정

Ch11 - 39. TreeSet

▶ TreeSet이란?

▷ 이진 탐색 트리(binary search tree)로 구현

▷ 범위 탐색, 정렬에 유리

• 범위 : from ≤ 범위 < to
  

▶ 이진 트리(binary tree)란?

▷ 이진 트리는 노드가 최대 2개(0개 ~ 2개)의 하위 노드를 가짐

▷ 각 요소(node)가 나무(tree) 형태로 연결 - LinkedList의 변형

class TreeNode {
    TreeNode left; // 왼쪽 자식노드
    Object element; // 저장 객체
    TreeNode right; // 오른쪽 자식노드, 하위 최대 2개 노드를 가질 수 있으니까 왼쪽 오른쪽 다 있음
} 

▶ 이진 트리의 단점

▷ 데이터가 많아질수록, 추가/삭제 시간이 오래 걸림(비교 횟수 증가)

Ch11 - 40. 이진 탐색 트리(binary search tree)

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

▷ 이진 트리의 한 종류

▷ 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장

Ch11 - 41. 이진 탐색 트리의 저장 과정

▶ TreeSet이란?

▷ Set : 중복 허용X

▷ 데이터 저장 과정

boolean add(Object o) // 저장 할 객체(o) → 중복 체크 → 저장 실패 시, false 반환 

• HashSet은 equals() hashCode()로 비교
  
• TreeSet은 compare()를 호출하여 비교
  
  

▶ 실습

▷ TreeSet에 순서대로 7, 4, 9, 1, 5 저장