(191117) 자료구조 - Tree

Tree 자료구조

트리.jpg

tree는 graph 자료구조의 한 종류이다 -> 사이클이 없는 연결 그래프 + 유향

  - 사이클이 없다 : 한 시작 정점과 종료 정점이 같지 않음 (즉, 끝에서 시작으로 못가)

  - 연결 그래프 : 모든 정점쌍에 항상 경로가 존재 (끊어진게 없다는 소리?)

  - 유향 그래프 : 루트 노드부터 자식노드로 ~

 

Base

- 그래프의 한 종류이기 때문에 마찬가지로 정점과 간선으로 구성

- 루트 노드가 있고 루트 노드는 0개 이상의 자식을 갖음(자식 노드도 마찬가지)

- 각 노드는 어떤 자료형으로도 표현 가능

- 계층 자료를 나타낼 때 사용 (디렉터리, 조직도 등!!)

 

용어

- 루트 노드(root node) : 부모가 없는 노드, 즉 트리는 하나의 루트 노드만 갖는다.

- 단말 노드 (leaf node, 잎 노드) : 자식이 없는 노드

- 내부 노드 (internal) : 단말 노드가 아닌 노드

- 형제 (sibling) : 같은 부모를 가지는 노드

- 노드의 레벨(level) : 특정 깊이를 가지는 노드의 집합

- 노드의 차수(degree) : 각 노드가 지닌 가지의 수

- 트리의 차수(degree of tree) : 트리의 최대 차수

- 높이 (height) : 트리의 최고 레벨(깊이)

- 하위 트리 (subtree)

 

특징

- 노드가 N개 -> 트리는 항상 (N-1)개의 간선을 가짐 (왜냐하면 사이클이 없으니까!)

- 임의의 두 정점 사이에 경로는 반드시 1개 (사이클이 없으니깐!!)

- 모든 자식 노드는 한 개의 부모 노드만 가짐

 

이진 트리의 종류 (트리의 종류는 이외에도 많다!!!!!!!!!!!!!!!!!)

이진 트리 (Binary Tree)

- 각 노드가 최대 2개의 자식만 갖는 트리

 

이진 탐색 트리 (Binary Search Tree) -> 다음 TIL에서 다룰 것!!

- 좌측 하위 트리 : 상위 노드보다 작거나 같은 값

- 우측 하위 트리 : 상위 노드보다 큰 값

- 하위 트리의 하위트리들도 모두 같은 특징

 

완전 이진 트리 (Complete binary tree)

- 이진 트리에서 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있음

- 마지막 레벨은 채워져 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함

- 배열을 사용해 효율적으로 표현 가능!! (위의 특징 때문인가..?)

 

전 이진 트리 (Full binary tree)

- 이진 트리에서 모든 노드가 0개 또는 2개의 자식을 갖음 (1개만 있는거 안됨!!)

 

포화 이진 트리 (Perfect binary tree)

- 완전 이진 트리 + 전 이진 트리

- 즉, 모든 말단 노드는 같은 높이 + 모든 내부 노드는 2개의 자식 + 모든 말단 노드는 동일 레벨

 

이진 트리의 순회 방법

위 3가지 방법은 깊이 우선 순회!?

1. 중위 순회(in-order)

2. 전위 순회(pre-order) - 루트 노드에서 시작한 깊이 우선 순회!!

3. 후위 순회(post-order)

4. 너비 우선 순회

 

트리의 구현 방법

그래프의 한 종류이므로 마찬가지로 인접 행렬과 인접 리스트를 이용 한다.

 

인접 행렬의 경우 1차원 배열에 자신이 부모 노드만 저장하는 방법 가능

(배열의 index는 각 정점을, element는 부모노드)

 

이진 트리의 경우 각 노드가 최대 2개의 자식을 가지므로 왼쪽 자식 / 오른쪽 자식으로 해서 좀 더 간단한 2차원 배열로 가능