Skip to main content

트리맵


트리맵(TreeMap) 이란?​



트리맵은 Java에서 사용하는 자료구조 중 하나이다.

위 이미지를 참고해보면 트리맵은 Map 인터페이스를 상속한 SortedMap의 구현 클래스로 표현되어 있다.


Map​

Map은 key-vaule 형식으로 데이터를 저장하는 자료구조로써 C++의 Map이나 Python의 Dictionary와도 비슷한 자료구조이다.

Map은 다음과 같은 큰 특징을 가진다.

  1. Key는 중복일 수 없다.
  2. Key와 Value 중 하나만 존재하지 않는다. (Key와 value는 쌍으로 존재한다.)
  3. Value는 중복값을 가질 수 있다.

SortedMap​

SortedMap은 데이터의 값이 Key 값에 따라 정렬이 되는 자료구조이다.

SortedMap은 Map 인터페이스를 상속 하기 때문에 SortedMap을 구현하는 클래스는 Map 인터페이스에서 제공하는 모든 메소드도 모두 구현해야 하며, 대표적인 구현 클래스가 오늘 다뤄볼 TreeMap이다.


TreeMap​

트리맵은 SortedMap의 대표적인 구현 클래스로써 정렬의 기준이 되는 Comparator에 따라 데이터 추가/삭제에 따라 Data의 순서를 정렬한다.

트리맵은 이진탐색트리, 구체적으로는 레드-블랙트리 자료구조로 이루어져있으며 Key와 Value의 쌍으로 이루어진 데이터를 저장한다. Map과 Tree를 결합한 자료구조이기 때문에 Map의 장점인 빠른 검색과 Tree의 장점인 정렬과 범위검색의 장점을 모두 가지게 된다.

기본적인 트리맵의 정렬 기준은 숫자 -> 알파벳 대문자 -> 알파벳 소문자 -> 한글 이다.


트리맵의 특징​


  • 트리맵은 레드블랙트리의 구조로 이루어져 있다.
  • 트리맵은 Map 인터페이스와 동일하게 중복을 허용하지 않고 null 값을 허용하지 않는다.
  • 데이터의 추가/삭제가 있을 때 정렬되면서 추가/삭제가 이루어진다.

트리맵의 구조​


트리맵은 레드블랙트리 데이터 구조를 기반으로 하기 때문에 위와 같은 노드 구성을 띄게된다.

  • 3개의 변수 (Key, Value , boolean Colour)
  • 3개의 참조 (Entry left = Left, Entry right = Right, Entry parent = Parent)

또한 기본적으로는 다음과 같은 특징을 갖게 된다.

  • 왼쪽 요소는 부모 요소보다 작은 값을 가지게 된다.
  • 오른쪽 요소는 부모 요소보다 크거나 같은 값을 가지게 된다.
  • 객체의 논리적인 비교는 구현된 Comporable 인터페이스나 compareTo 메소드에 의해 반환되는 value 값에 따라 진행된다.

시간복잡도​

  • 트리맵은 삽입, 삭제, 검색에 모두 O(logn)O(logn)의 시간복잡도를 가진다.
  • 트리맵에 n개의 요소를 삽입 할 경우 O(nlogn)O(nlogn)의 시간복잡도를 가진다.

코드로 보는 트리맵​


1. TreeMap 선언​

TreeMap<Integer,String> map1 = new TreeMap<Integer,String>(); // TreeMap생성 (key:Integer, value:String)
TreeMap<Integer,String> map2 = new TreeMap<>(); // 타입 파라미터 생략 가능

Comparator을 추가하여 선언하는 경우는 다음과 같다.

import java.util.Comparator;
import java.util.Set;
import java.util.TreeMap;

// s1와 s2의 길이에 따른 정렬
TreeMap<String,Integer> treemap = new TreeMap<String, Integer>(
        new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s1.length().compareTo(s2.length());
            }
        }
);

2. TreeMap 값 추가​

// TreeMap생성
TreeMap<Integer,String> treemap = new TreeMap<Integer,String>();

// put 메소드로 값 추가
treemap.put(1, "자료구조");
treemap.put(2, "알고리즘");
treemap.put(3, "네트워크");

3. TreeMap 값 삭제​

// TreeMap생성 및 초기값 설정
TreeMap<Integer, String> treemap = new TreeMap<Integer,String>(){{
    put(1, "자료구조");//값 추가
    put(2, "알고리즘");
    put(3, "네트워크");
}};

treemap.remove(1); //key값 1 제거
treemap.clear(); //모든 값 제거

4. TreeMap 출력​

// TreeMap생성 및 초기값 설정
TreeMap<Integer, String> treemap = new TreeMap<Integer,String>(){{
    put(1, "자료구조");//값 추가
    put(2, "알고리즘");
    put(3, "네트워크");
}};

System.out.println(treemap); // 전체 출력 : {1=자료구조, 2=알고리즘, 3=네트워크}
// {1=자료구조, 2=알고리즘, 3=네트워크}

System.out.get(1); // key값이 1인 value 출력
// 자료구조

System.out.println(treemap.firstKey())); // 최소 key(1) 출력
// 자료구조

System.out.println(treemap.firstKey())); // 최대 key(3) 출력
// 네트워크

트리맵의 장단점​


장점​

  • Map의 장점인 빠른 검색과 Tree의 장점인 정렬, 범위검색의 장점을 모두 갖고 있다.
  • 정렬된 상태로 데이터를 조회하는 경우가 많다면 효율적인 자료구조이다.

단점​

  • 이진탐색트리와 동일하게 데이터를 저장하며 정렬하기 때문에 저장시간이 길다는 단점이 있다.

면접에 나올 수 있는 질문​


Q. 트리맵은 어떤 특징을 가지고 있는가?

A. 트리맵은 Key값을 정렬 할 수 있다는 특징을 가지며 Map의 장점인 빠른 검색과 Tree의 장점인 범위검색의 장점을 가지고 있다.


Q. HashMap과 비교했을 때 TreeMap의 차이점은?

A. 이상적으로는 O(1)O(1)의 시간복잡도를 가지는 HashMap이 평균적으로 더 빠른 자료구조이지만, 데이터를 조회할 때 정렬하는 과정이 필요하다.
따라서 정렬된 상태로 데이터를 조회하는 경우가 빈번하거나 범위 검색이 필요한 경우에는 TreeMap의 사용이 유리하다.


참고​



기여자​



Jongminfire
📦