10. HashSet사용하기, TreeSet구현하기

Set은 주머니의 형태로 되어있다. 

Set은 객체를 중복해서 저장할 수 없고, 하나의 null값만 저장할 수 있다.

비선형 구조이기에 순서가 없으며, 인덱스도 존재하지 않는다.

그맇기에 값을 추가하거나 삭제할 때

Set 내부에 해당 값이 존재하는지 검색한 뒤 추가, 삭제해야하기에

속도가 List에 비해 느리다.

Set인터페이스를 구현한 클래스로는

HashSet과 TreeSet이 있다. 

HashSet의 경우 정렬을 해주지 않고,

TreeSet의 경우 자동정렬을 해준다.

 

1. HashSet 사용해보기

결과값

1-2. LinkedHashSet 사용해보기

결과값

중복된 값은 저장되지 않는 모습을 볼 수 있었다.

2. TreeSet 구현하기

TreeSet은 HashSet과 마찬가지로 Set인터페이스를 구현한 클래스이다.

객체를 중복해서 저장할 수 없고,

저장 순서가 유지되지 않는 Set의 성질을 그대로 가지고 있다.

TreeSet은 HashSet과 달리

이진 탐색 트리 구조로 이루어져 있다.

이진 탐색 트리는 추가와 삭제에는 시간이 걸리지만

정렬, 검색에 높은 성능을 보이는 자료구조이다. 

 

우선 node 클래스를 생성해주었다.

 

그다음 TreeSet의 기능을 구현할 

myTree 클래스를 구현하였다.

TreeSet을 구현하기 위해선

재귀함수를 사용해야 했다.

재귀함수란 특정 함수 내에서 자기 자신을 다시 호출하여

문제를 해결해나가는 함수이다. 

문제를 해결하기 위해 원래 범위의 문제에서

더 작은 범위의 하위 문제를 먼저 해결함으로써

원래 문제를 해결해나가는 방식이다.

 

일반 반복문을 통해 구현 가능한 기능은

재귀 함수를 통해 구현이 가능하며

반대로 재귀함수로 구현한 기능은

반복문으로 구현가능하다.

 

재귀함수는 함수 내에서 자기 자신을 계속 호출하는 방식이기에

함수 안에 반드시 중료 구간이 되는 코드를 구현해야 한다.

main 클래스로 돌아가 실행시켜보았다.

잘 정렬되어 트리 구조를 이루며

출력되는 모습을 볼 수 있었다.