[자료구조] Map 과 배열을 이용한 트리 구현

 목  차

• 트리의 정의와 주요 특성
• 배열을 사용한 트리 구현
• Map을 사용한 트리 구현

 
 

---

 

  트리의 정의와 주요 특성

 
노드는 부모가 있고, 자식이 왼쪽과 오른쪽에 있다.
노드의 구성은 아래 이미지를 참고하면 된다.
 

노드

 
 
이런 노드들이 모여서 트리가 되는 것인데,
부모를 타고 계속 올라가서 더 이상 부모가 없는 노드를 루트노드 라고 한다.
자식을 타고 계속 내려가서 더이상 자식이 없는 노드를 리프노드 라고 한다.
 
그리고 루트노드의 인덱스가 i 일 때, 왼쪽 자식의 노드는 i * 2, 오른쪽 자식의 노드는 i * 2 + 1 이다.
반대로 부모 노드는 Math.floor(i / 2) 이다. Math.floor 메서드는 내림을 해주는 메서드이다. 즉, 9.8을 9로 만들어 준다.
 
 

---

 

  배열을 사용한 트리 구현

 
배열을 사용하여 트리를 구현하면 인덱스를 통해서 빠르게 접근이 가능하다.
 
완전 이진 트리와 같은 트리 유형에서 배열을 사용하여 트리를 구현하는 게 효율이 좋다.
그 이유는 배열에는 기본값이 있는데 완전 이진 트리가 아니라면 메모리 낭비가 심해진다. 
 
아래와 같은 경우가 바로 그 예시인데, 실제로 값이 들어 있는 건 5개이지만 완전 이진 트리의 형태로 구현을 하면 값이 있든 없든 모든 노드는 오른쪽 왼쪽 자식 노드를 가지게 된다. 
 

 
 
그럼 어느 경우에 배열을 사용하여 트리를 구현할까?
바로 세그먼트트리이다. 세그먼트트리는 완전 이진 트리를 구현해야 하며, 값이 없는 노드들도 꼭 기본값을 가지고 있어야 한다.
 
세그먼트트리의 특징은 '리프노드'가 존재한다. 그래서 나는 리프노드가 존재할 때 배열을 사용해서 트리를 구현하면 좋다고 생각한다.
 
 
 

---

 

  Map을 사용한 트리 구현

 
Map을 사용해서 트리를 구현하면 완전 이진 트리가 아닐 때 메모리를 절약할 수 있다.
 
위에서 본 것과 같은 구조의 트리를 Map으로 트리를 구현해 보자. 빈 노드가 없이 필요한 노드만 딱딱 사용하고 있다.
하지만 배열과 다르게 접근하는 방법이 다소 차이가 있으므로 완전 이진 트리에서는 비효율적이다.
 

 
 
그래서 리프노드가 제공되지 않고 루트노드 먼저 입력이 들어오거나 제공된다면 Map을 활용하여 트리를 구현하는 게 좋다고 생각한다.
물론 상황마다 다르겠지만 말이다.
 
 
 

---

 
 
백준 1991 트리순회 문제는 랭크가 낮은 문제였지만 소득을 많이 안겨준 문제였다.