[Java] TreeSet 범위 탐색, 정렬

목차

• TreeSet의 특징
• 이진 탐색 트리의 특징
• TreeSet 데이터 저장과정
• TreeSet 예제

 

TreeSet - 범위 탐색, 정렬

• 이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리(from ~to)
• 이진 트리는 모든 노드가 최대 2(0 ~ 2)개의 하위 노드를 갖음.
• 각 요소(node)가 나무(tree) 형태로 연결(LinkedList의 변형)

 

 

남궁성 유튜브 출처: https://www.youtube.com/watch?v=_4EF-26Ke3o&list=PLW2UjW795-f6xWA2_MUhEVgPauhGl3xIp&index=130

 

 

class TreeNode {
    TreeNode left; // 왼쪽 자식노드
    Object element; // 저장할 객체(데이터를 저장)
    TreeNode right; // 오른쪽 자식노드
}

 

 

 

이진 트리의 종류

 

이진 탐색 트리(binary search tree)

• 부모보다 작은 값은 왼쪽 큰 값은 오른쪽에 저장
• 트리가 커질수록, 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)

 

 

TreeSet 데이터 저장과정 

• set은 중복을 허용하지 않기 때문에 같은 것이 있는지 비교를 해봐야 한다.
• 루트부터 트리를 따라 내려가며 값을 비교, 적으면 왼쪽, 크면 오른쪽에 저장

 

boolean add(Object o)

1. equals( )

2. hashCode( )

 

TreeSet에 7, 4, 9, 1, 5의 순으로 데이터를 저장했을 때

 

 

 

TreeSet 주요 생성자와 메서드

컬렉션에 있는 메서드들은 제외했다. TreeSet이 가지고 있는 특별한 메서드

 

 

 

예제

public class TreeSetEx1 {

    public static void main(String[] args) {

        Set set = new TreeSet(); // 범위 검색
        //Set set = new HashSet(); // 정렬 필요

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

[2, 7, 21, 28, 32, 33]

 

HashSet과 달리 List로 변환해 sort( )로 정렬할 필요가 없다.

 

public class TreeSetEx2 {

    public static void main(String[] args) {

        TreeSet set = new TreeSet(); // 범위 검색에 유리(from ~ to)

        String from = "b";
        String to = "d";

        set.add("abc");
        set.add("alien");
        set.add("bat");
        set.add("car");
        set.add("Car");
        set.add("disc");
        set.add("dance");
        set.add("dZZZZZ");
        set.add("dzzzzz");
        set.add("elephant");
        set.add("elevator");
        set.add("fan");
        set.add("flower");

        System.out.println(set);
        System.out.println("range search : from " + from + " to " + to);
        System.out.println("result1 : " + set.subSet(from, to)); // b ~ czzzzzzz.. 까지
        System.out.println("result2 : " + set.subSet("b", "e")); // b ~ czzzzzzz.. 까지
        System.out.println("result3 : " +set.subSet(from, to + "zzz")); // b ~ dzzzz 까지 그래서  dzzzzz는 안나왔음
    }
}

[Car, abc, alien, bat, car, dZZZZZ, dance, disc, dzzzzz, elephant, elevator, fan, flower]
range search : from b to d
result1 : [bat, car]
result2 : [bat, car, dZZZZZ, dance, disc, dzzzzz]
result3 : [bat, car, dZZZZZ, dance, disc]

 

 

public class TreeSetEx3 {

    public static void main(String[] args) {

        TreeSet set = new TreeSet(); // 범위 검색에 유리(from ~ to)
        int[] score = {80, 95, 35, 45, 65, 10, 100};

        for (int i = 0; i < score.length; i++) {
            set.add(new Integer(score[i]));
            //set.add(score);
        }
        System.out.println("50보다 작은 값: " + set.headSet(new Integer(50)));
        System.out.println("50보다 큰 값: " + set.tailSet(new Integer(50)));
        System.out.println("50 이랑 가까운 높은값: " + set.higher(50));
        System.out.println("50 이랑 가까운 작은값: " + set.lower(50));
        System.out.println("40과 80 사이의 값: " + set.subSet(40, 80));
    }
}

50보다 작은 값: [10, 35, 45]
50보다 큰 값: [65, 80, 95, 100]
50 이랑 가까운 높은값: 65
50 이랑 가까운 작은값: 45
40과 80 사이의 값: [45, 65]

 

 

 

트리 순회(tree traversal)

이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.

전위, 중위 후위 순회법이 있으며, 중위 순회하면 오름차순으로 정렬된다.