[JAVA] TreeSet과 이진 탐색 트리

 

📑 TreeSet이란?

 

TreeSet은 이진 탐색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다. 이진 탐색 트리는 정렬, 검색, 범위검색에 높은 성능을 보이는 자료구조이며 TreeSet은 이진 탐색 트리의 성능을 향상시킨 '레드-블랙-트리'로 구현되어 있다.

 

Set 인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다. 이진 트리는 링크드 리스트처럼 여러 개의 노드가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며 '루트'라고 불리는 하나의 노드에서부터 시작해 계속 확장해나갈 수 있다. 

 

 

class TreeNode {
TreeNode left; //왼쪽 자식 노드
Object element; // 객체 저장하기 위한 참조 변수
TreeNode right; //오른쪽 자식 노드
}

 

위의 코드는 데이터를 저장하기 위한 Object타입의 참조변수 하나와 두 개의 노드를 참조하기 위한 두 개의 참조변수를 선언했다. 

 

 

 

📑 이진 탐색 트리(binary search tree)

 

이진 탐색 트리는 부모노드의 왼쪽에는 부모노드의 값보다 작은 값의 자식노드를 오른쪽에는 큰 값의 자식노드를 저장하는 이진틔이다. 예를들어 데이터를 5,1,7 순서로 저장한 이진 탐색 트리는 왼쪽 마지막 값에서부터 오른쪽 값까지 값을 '왼쪽노드 -> 부모 -> 오른쪽노드' 순으로 읽어오면 오름차순으로 정렬된 순서를 얻을 수 있다. 

 

TreeSet은 이처럼 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위 검색 ( 3과 7사이의 범위에 있는 값)이 매우 빠르다. 트리는 데이터를 순차적으로 저장하는 것이 아니라 저장 위치를 찾아서 저장하고, 삭제하는 경우 트리의 일부를 재구성해야 하므로 링크드 리스트보다 데이터/추가 삭제 시간은 더 걸리다. 대신! 배열이나 링크드 리스트에 비해 검색과 정렬 기능이 뛰어나다. 

 

 

📌 모든 노드는 최대 두 개의 자식노드를 가질 수 있다.
📌 왼쪽 자식노드의 값은 부모 값보다 작고 오른쪽 자식노드의 값은 부모노드의 값보다 커야한다.
📌 노드의 추가 삭제에 시간이 걸린다. (반복 비교로 자리를 찾아서 저장)
📌 검색과 정렬에 유리하다.
📌 중복된 값을 저장하지 못한다.

 

 

TreeSet은 저장할 때 이미 정렬하기 때문에 읽어올 때 따로 정렬할 필요가 없다.

 

package part_11;

import java.util.Set;
import java.util.TreeSet;

public class Ex11_13_TreeSet {
    public static void main(String[] args) {
        Set set = new TreeSet();
        for(int i=0;set.size()<6;i++){
            int random = (int) ((Math.random() * 45) + 1);
            set.add(random);
        }
        System.out.println("set = " + set);
        
        //이전 HashSet과는 다르게 정렬하는 코드가 빠진다.
    }
}

 

 

hadSet메서드와 tailSet 메서드 이용시, TreeSet에 저장된 객체 중 지정된 기준 값보다 큰 값, 작은 값의 객체를 얻을 수 있다. 

 

package part_11;

import java.util.TreeSet;

public class Ex11_14_TreeSet2 {
    public static void main(String[] args) {
        TreeSet set = new TreeSet();
        int[] score = {80, 95, 50, 35, 45, 65, 10, 100};

        for (int i = 0; i < score.length; i++) {
            set.add(score[i]);
        }

        System.out.println("50보다 작은 값 : " + set.headSet(50));
        System.out.println("50보다 큰 값 : "+set.tailSet(50));
        

    }
}