11 (5) TreeSet

TreeSet - 범위 검색과 정렬에 유리

- 이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리.

- 이진 트리는 모든 노드가 최대 2개의 하위 노드를 가지고 있다

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

이진 탐색 트리(binary search tree)

- 부모보다 작은 값을 왼쪽 큰 값은 오른쪽에 저장

※이진 트리에는 부모보다 작은 값, 큰값의 왼쪽 오른쪽 구분이 없다(자식 2개만 있으면 이진 트리)

- 데이터가 많아질수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)

- TreeSet - 데이터 저장과정 boolean add(Object o)

※TreeSet에 7,4,9,1,5의 수선로 데이터를 저장하면, 아래의 과정을 거친다.

(루트부터 트리를 ᄄᆞ라 내려가며 값을 비교, 작은면 왼쪽, 크면 오른쪽에 저장)

 

 

 

 

TreeSet - 주요 생성자와 메서드

 

 

 

 

 

 

class Test 변경

>> 클래스 자체에 비교기준을 만들어 준다

 

TreeSet은 비교기준이 필요하다

1) 저장하는 객체가 Comparable을 가지거나

2) TreeSet(new TestComp());처럼, TreeSet이 어떤 정렬기준을 갖는다

 

 

 

 

TreeSet - 범위 검색 subSet( ), headSet( ), tailSet( )

 

 

TreeSet - 트리 순회(전위, 중위, 후위)

- 이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.

- 전위 중위 후위 순회법이 있으며, 중위 순회하면 오름차순으로 정렬된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

출처 : 남궁성의 정석코딩 - YouTube

남궁성의 정석코딩