23.01.31

학습

• 항해99 알고리즘 모의고사 진행.
• 그리디 알고리즘 학습
• TreeSet 학습
  - TreeSet은 Set이지만 순서를 가진다.
  - 이진 탐색 트리(binary search tree)로 구현, 볌위 탬색과 정렬에 유리
  - 이진 트리는 모든 노드가 최대 2개의 하위 노드를 가진다.
  

• 범위 검색과 정렬에 유리한 컬랙션 클래스
• HashSet보다 데이터 추가, 삭제에 시간이 더 걸린다.
• 다음과 같은 구조로 구성된다. 부모의 자식은 최대2개를 가진다.

노드의 구성은 다음과 같다

class TreeNode {
	TreeNode left;   //왼쪽 자식노드
    Object;          //저장할 객체
    TreeNode right;  //오른쪽 자식노드
}

LinkedList와 유사한 구조를 가진다.

이진 탐색 트리(binary search tree)

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

데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)
boolean add(Object o) → compare()를 호출
TreeSet에 7,4,9,1,5의 순서로 데이터 자장하면, 아래의 과정을 거친다.
(루트부터 트리를 따라 내려가며 값을 비교. 작으면 왼쪽, 크면 오른쪽에 저장)

1. 7저장
2. 4와 7비교 → 4 7 저장
3. 9와 7비교 → 4 7 9 저장
4. 1과 7비교 → 1과4비교 → 1 4 7 9저장
5. 5와 7비교 → 5와4비교 → 1 4 5 7 9 저장

비교회수가 점점 늘어는 형식이다.

실습 코드를 작성해보면 다음과 같다. 무작위로 숫자를 TreeSet에 넣어주면 다음과같이 정렬이되어서 저장된다.

public class Ex11_13 {
    public static void main(String[] args) {
        Set set = new TreeSet();

        for (int i = 0; set.size() <6 ; i++) {
            int num = (int)(Math.random()*45)+1;
            set.add(num);
        }
        System.out.println(set);
    }
}


실행결과
[11, 19, 26, 32, 38, 45]