TreeSet

이진 검색 트리는 루트에서 시작해서 2개의 부모를 가지는 자료구조이다.

루트가 아닌 노드는 부모 노드와 left, right라는 2개의 자식 노드를 가지게 된다.

 

이진 검색 트리의 특징

• 모든 노드는 최대 2개의 자식 노드를 가질 수 있다.
• 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식노드의 값은 부모노드의 값보다 커야한다.
• 노드의 추가 삭제에 시간이 걸린다. -> 순차적으로 저장하지 않기 때문에
• 검색과 정렬기능이 배열이나 링크드 리스트에 비해 뛰어나다.
• 중복된 값을 저장하지 못한다.

 

자바에서 제공하는 Treeset은 저장할 때 이미 정렬하기 때문에 값을 읽을 때 별도의 정렬을 할 필요가 없다.

public class Main {
    public static void main(String[] args) {
        TreeSet set = new TreeSet<>();
        Integer[] score = {70, 50, 100, 40, 60, 20, 30, 90};
        
        for(int i = 0; i < score.length; i++)
            set.add(score[i]);
        
        System.out.println("50보다 작은 값 :", + set.headSet(new Integer(50)));
        System.out.println("50보다 큰 값 :", + set.tailSet(new Integer(50)));
    }
}

결과

50보다 작은 값 : [10, 35, 45]

50보다 큰 값 : [50, 65, 80, 95, 100]

 

사진 출처 : Java의 정석 (남궁성 지음)

 

위의 사진과 같이 50보다 작은 값들은 50 노드의 왼쪽 자식 노드와 그 아래이고, 나머지 값들은 50 노드의 오른쪽 자식과 부모 클래스의 오른쪽 노드들이다.