Chapter 11) 컬렉션 프레임워크 - TreeSet

◇ 이진 트리란?

이진 트리는 LinkedList 처럼 여러 개의 노드가 서로 연결된 구조

• 각 노드에 최대 2개의 노드를 연결할 수 있다.
• 루트 노드에서부터 시작해서 계속 확장해나갈 수 있다.
• 위 아래로 연결된 두 노드를 '부모-자식' 관계(상대적)에 있다고 한다.
  • 위의 노드는 부모 노드
  • 아래 노드는 자식 노드

class TreeNode{
    TreeNode left; // 왼쪽 자식 노드
    Object element; // 현 노드 데이터
    TreeNode right; // 오른쪽 자식 노드
}

 

◇ TreeSet이란?

이진 검색 트리(Binary Search Tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스

검색 효율이 뛰어난 자료구조다.

현재 TreeSet은 이진 검색 트리의 성능을 향상시킨 '레드-블랙 트리(Red-Black-Tree)'로 구현되어 있다.

• Set 인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않음
• 정렬된 위치에 저장하므로 저장순서를 유지하지 않는다.
• 부모 노드의 왼쪽에는 부모노드의 값보다 작은 값의 자식노드를 저장한다.
• 부모 노드의 오른쪽에는 부모노드의 값보다 큰 값의 자식노드를 저장한다.
• TreeSet에 저장되는 객체는 Comparable을 구현하거나 TreeSet에 Comparator를 제공해서 두 객체를 비교할 방법을 알려줘야 한다. => 그렇지 않으면 객체 저장 시 예외 발생.

import java.util.*;

public class Main {

    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(new Integer(num));
        }
        
        // 이미 정렬된 구조이기 때문에 따로 정렬하지 않아도 된다.
        System.out.println("set = " + set);
    }
}