트리 왜함?

• 실제로 필드에서 트리를 구현하지는 않음
• 트리를 활용한 기술, 라이브러리, 자료 구조를 많이 사용하여 문서를 일거나 소스코드를 따라갈때 잘 이해가 된다.

1. 트리 정의

• 노드(node)들의 집합
• 각 노드는 값(value)과 다른 노드들을 가리키는 레퍼런스들로 구성

2. 트리 관련 주요 용어

1) 간선(edge)

• 노드와 노드를 연결하는 선
• 구현 관점에서는 레퍼런스를 의미
• link, branch 라고도 함

2) 루트노드

• 트리의 최상단에 있는 노드
• 트리의 시작점

3) 자녀 노드

• 모든 노드는 0개이상의 자녀노드를 가진다.

4) 부모노드

• 자녀노드를 가지는 노드

5) 형제 노드

• 같은 부모를 가지는 노드들

6) 조상 노드

• 부모 노드를 따라 루트 노드까지 올라가며 만나는 모든 노드

7) 자손 노드

• 자녀 노드를 따라 내려가며 만날 수 있는 모든 노드

8) 내부 노드

• 자녀노드를 가지는 노드

9) 외부 노드

• 자녀 노드가 없는 노드
• terminal node, leaf node 라고도함

10) 경로(path)

• 한 노드에서 다른 노드사이의 노드들의 시퀀스
• ex) 2에서 7로의 경로 : 2-5-7

11) 경로의 길이

• 경로에 있는 노드들의 수
• ex) 2에서 7로의 경로 길이 : 3

12) 노드들의 높이

• 노드에서 리프 노드까지의 가장 긴 경로의 간선 수
• 리프 노드의 높이 : 0
• 엣지 수인지 노드 수인지 잘 파악해야한다. 노드 수 일경우 n+1

13) 트리의 높이

• 루트 노드의 높이

14) 노드의 깊이(depth)

• 루트노드에서 해당 노드까지의 경로의 간선 수

15) 트리의 깊이

• 트리에 있는 노드들의 깊이 중 가장 긴 깊이
• 트리 높이 = 트리 깊이

16) 노드의 차수(degree)

• 노드의 자녀 노드 수

17) 트리의 차수

• 트리 에 있는 노드들의 차수 중 가장 큰 차수

18) 두 노드 사이의 거리

• 두 노드의 최단 경로의 간선 수

19) 노드의 레벨

• 노드와 루트 노드 사이의 경로에서 간선의 수
• 루트 노드의 레벨 : 0

20) width

• 임의의 레벨에서 노드의 수

21) 노드의 크기

• 자신을 포함한 자손 노드의 수

22) 트리의 크기

• 트리의 모든 노드 수

23) 서브 트리

• 각 노드의 자녀 노드들을 재귀적으로 서브트리를 구성

3. 트리 구조의 주요 특징

• 루트 노드는 하나만 존재
• 사이클이 존재하지 않음
• 자녀 노드는 하나의 부모 노드만 존재
• 데이터를 순차적으로 저장하지 않는 비선형(nonlinear) 구조 <-> linked list, stack, queue는 데이터를 순차적으로 저장하는 선형 구조
• 트리에 서브트리가 있는 재귀적 구조
• 계층적 구조

4. 이진 트리

1) 특징

• 각 노드의 자녀 수가 최대 두 개인 트리
• 왼쪽 자녀 노드 | 오른쪽 자녀 노드

2) 형태에 따른 이진 트리의 종류

• full binary tree(정 이진 트리) : 모든 노드는 자녀 노드가 없거나 두개 인 트리
• complete binary tree(완전 이진 트리) : 마지막 레벨을 제외한 모든 레벨에서 노드가 빠짐없이 채워져 있고 마지막 레벨은 왼쪽부터 빠짐없이 노드가 채워져있는 트리
• perfect binary tree(포화 이진 트리) : 모든 레벨에서 노드가 빠짐없이 채워져 있는 트리
• degenerate binary tree(변질 이진 트리) : 모든 부모 노드는 하나의 자녀 노드만 가지는 트리
• left/right skewed binary tree : 모든 부모노드가 한쪽 자녀 노드만 가지는 트리(왼쪽 or 오른쪽)
• balanced binary tree(균형 이진 트리) : 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1인 트리

5. 이진 탐색 트리

1) 정의

• 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값을 가진다.
  2) 이진 탐색 트리의 최소값
• 트르의 가장 왼쪽에 존재
  3) 이진 탐색 트리의 최대값
• 트리의 가장 오른쪽에 존재
  4) 중위 순회(inorder traversal)
• 재귀적으로 왼쪽 서브 트리 순회
  -> 현재 노드 방문 (e.g. 값 출력)
  -> 재귀적으로 오른쪽 서브 트리 순회
• 순서대로 방문하게 되는 특징이 있다.
• 일반적인 트리에서도 쓸수 있다.
  5) 전위 순회(preorder traversal)
• 현재 노드 방문 (e.g. 값 출력)
  -> 재귀적으로 왼쪽 서브 트리 순회
  -> 재귀적으로 오른쪽 서브 트리 순회
  6) 같은 값을 가질수없다?