[코드잇-자료구조2 : 트리의 구조와 탐색] 1. 트리란?

본 게시물은 코드잇의(codeit) 자료구조 시리즈 강의 두번째 주제인 '트리의 구조와 탐색'을 듣고 정리한 게시물임을 알려드립니다.

- 강의 url : https://www.codeit.kr/topics/trees?mediumTypedId=UGxheWxpc3Q6NjZkZDU5YWI4OTg1YTI3ZWRkOTdlOWUz

트리의 구조와 탐색 - 알고리즘 · 자료구조 강의 | 코드잇

---

1. 계층적 관계

트리구조 : 계층적 관계를 저장하고 활용하기에 적합한 자료 구조

- 배열, 링크드 리스트는 선형적 자료구조로 계층적 관계를 나타내기에는 부적합함

- 해시 테이블도 데이터 관계를 저장하기에 부적절함

 

예시

 

- 상-하 관계가 있는 데이터간의 계층적 관계

 

2. 트리란?

우선 앞서 배웠던 선형적 자료구조의 일종인 '링크드 리스트'와 비교해서 설명한다.

링크드 리스트

 

링크드 리스트 : 여러 개의 데이터를 순서대로 저장해주는 선형적인 자료 구조

- 노드 : 데이터가 담겨지는 기본 단위

- 하나의 노드는 저장하려는 데이터와 다음 순서의 노드를 가리키는 레퍼런스를 갖는다. (순서 저장)

- head 노드 : 맨 앞에 있는 노드

 

트리

 

트리도 링크드 리스트와 똑같이 여러개의 노드로 이뤄져 있음

- 트리노드 : 기본적으로는 데이터를 저장하는 하나의 단위 

- 데이터 2를 저장하는 노드 A, 3을 저장하는 노드 B

- 링크드 리스트와 다르게 하위 순서인 '자식 노드'에대한 레퍼런스만 저장한다. 트리구조에서는 이 레퍼런스는 화살표로 나타낸다.

 

- 링크드 리스트에서의 'head node'에 해당하는 것이 트리 구조에서는 root 노드

 

3.  트리 용어 정리

root 노드(뿌리 노드)
- 트리의 시작 노드, 뿌리가 되는 노드

- 보통 트리를 표현할 때 위 그림처럼 가장 위에 root 노드를 놓는 방식으로 나타냄

부모 노드

- 특정 노드의 직속 상위 노드

- 노드 G, J, K가 있는 노란색 박스를 살펴보면 G가 J와 K의 부모 노드

 

자식 노드

- 특정 노드의 직속 하위 노드

- 부모 노드와 반대되는 개념으로, 노드 G, J, K가 있는 노란색 박스를 살펴보면 J와 K가 G의 자식 노드

 

형제 노드

- 같은 부모를 갖는 노드

- D와 E는 둘다 그 부모가 B일때, D와 E는 서로 형제 노드

 

leaf 노드 (잎/말단 노드)

- 자식 노드를 갖고 있지 않은, 가장 말단에 있는 노드

- 트리의 끝에 있다고 해서 root(뿌리) 노드와 반대되는 표현으로 leaf(잎) 노드라고 부름

- 위 그림에서 노란색 박스로 둘러싼 F가 leaf 노드

- F뿐만 아니라 D, H, I, J, K 모두 leaf 노드

 

깊이

- 특정 노드가 root 노드에서 떨어져 있는 거리

- 깊이는 해당 노드로 가기 위해서 root 노드에서 몇 번 아래로 내려와야 하는지를 나타냄

- 예를 들어 위 그림에서 root 노드의 자식 노드인 B와 C는 깊이가 1

- D, E, F, G는 깊이가 2이고, H, I, J, K는 깊이가 3

 

레벨 

- 레벨 = 깊이 + 1

- 레벨 1에 있는 노드들, 레벨 2에 있는 노드들… 이런식으로 특정 깊이인 노드들을 묶어서 표현할 때 사용하는 용어

 

높이

- 트리에서 가장 깊이 있는 노드의 깊이

- 위 그림의 트리에서는 H, I, J, K가 가장 깊이 있는 노드들이고 그 깊이는 모두 3 → 트리의 높이는 3

부분 트리 (sub-tree)

- 현재 트리의 일부분을 이루고 있는 더 작은 트리를 말한다.

- 위 그림의 트리는 root 노드가 A인 트리인데 이 트리를 좀더 작은 단위로 쪼개보면 더 작은 부분 트리인 '부분트리'들을 발견가능

 → ex. ‘C가 root 노드인 트리’ 등

 → C가 root 노드인 트리에서 C는 A의 오른쪽 자식이고, 그래서 노란색 큰 박스 안에 있는 부분 트리를 A의 “오른쪽 부분 트리”라고 한다.

- 특정 노드를 root 노드라고 생각하고 바라본다면 여러 가지 부분 트리들을 발견할 수 있으며, 하나의 전체 트리에 여러 부분 트리들이 존재하는 것

 

4. 트리의 활용

 

 

- 트리구조를 잘 활용하여 딕셔너리, 세트, 우선순위 큐 등의 추상자료형들을 구현할 수 있음

 

5. 이진트리

- 이진 트리 : 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리

 

 

6. [실습] 이진 트리 구현

7.  [실습] 이진 트리 만들어 보기

8. 이진 트리 종류

 

 트리에는 여러 종류가 있고, 우리는 이 중 하나인 '이진 트리'에 대해 배웠음. 그런데, 이진트리도 다시 여러 종류로 분류할 수 있음

 

정 이진 트리 (Full Binary Tree)

- 모든 노드가 2개 또는 0개의 자식을 갖는 이진 트리

 

완전 이진 트리 (Complete Binary Tree)

아래의 두 가지 조건을 모두 만족하는 이진 트리

① 마지막 레벨을 제외한 모든 레벨이 차 있음
→ 마지막 레벨 직전의 레벨까지는 모든 노드들이 다 채워져있음

② 마지막 레벨은 왼쪽에서 오른쪽으로 차 있음

 

(완전 이진 트리의 성질 : 높이)

- 완전 이진 트리 안에 저장된 노드가 n개라고 할 때, 높이는 항상 lg(n)에 비례한다.

 

증명

- h : 완전 이진 트리의 높이

- n : 그 노드의 수

즉, 노드 수가 n개인 완전 이진 트리의 높이 h는  h<= lg(n) 를 만족하는 정수 중 최대의 정수

따라서 완전 이진 트리의 높이 h는 노드 수인 n에 lg를 취한 값인 lg(n)에 비례해서 증가한다는 것을 알 수 있음

 

높이가 하나 더 증가할 때 : 노드수가 현재보다 최소 2배 이상이 되었을 때

 

h<= lg(n)에서 n이 2n이 되면 

lg(2n) = lg(n) + 1이고,

h+1 <= lg(n) + 1을 만족하므로,

최소한 현재 노드 수 보다 노드 수가 2배 이상이 되었을 때 높이도 하나 더 올라간다는 것을 알 수 있음

 

포화 이진 트리 (Perfect Binary Tree)

모든 레벨이 빠짐없이 다 노드로 채워져있는 이진 트리이며, 모든 레벨이 완벽하게 다 채워져 있기 때문에 영어로는 "perfect binary tree”라고 부른다.

- 포화 이진 트리는 기본적으로 정 이진 트리와 완전 이진 트리의 특성을 모두 갖는다.

 

 

9. [실습] 완전 이진 트리 배열로 구현하기

10. [실습] 완전 이진 트리 직접 구현하기

 

11. 트리 순회

 

순회

- 자료구조에 저장된 모든 데이터를 도는 것

- 트리에서는 선형관계가 없으므로 직관적으로 순서를 알기 어려울 수 있음

 

트리 순회

- 주로 재귀함수를 사용한다.

※ 선형적 자료구조의 순회에서는 반복문을 주로 사용했었음

 

이해를 돕기위한 예시 : 모든 노드를 출력하는 예시

 

- 위의 함수 traverse는 순회하고싶은 트리의 root 노드를 입력값으로 받는다.

 

(트리순회에서의 3가지 기본 동작) 

ㄱ. 재귀적으로 왼쪽 부분 트리를 순회하기

- traverse 함수의 파라미터로 루트 노드의 왼쪽 자식 노드를 넘겨서 호출

- 위에서의 호출을 재귀적으로 한다는 것은 traverse 함수 정의 부분 어딘가에

traverse(node.left_child)

이런식으로 파라미터를 바꿔서 traverse 함수 안에서 다시 traverse 함수를 또 호출해 준다는 말

 

ㄴ. 재귀적으로 오른쪽 부분 트리 순회

 

 

- ㄱ.과 마찬가지

 

ㄷ. 현재 노드 데이터를 출력한다.

- 파라미터로 root node를 받았으면 F를, 노드 B를 받았으면 B를 출력

 

(정리)

- 순서 조합에 따라 순회가 조금씩 달라짐

12. 트리 순회 대표 방식 1 : pre-order

13. 트리 순회 대표 방식 2 : post-order

14. 트리 순회 대표 방식 3 : in-order

15. [실습] in-order 순회 구현하기

16. 트리 퀴즈