자료 구조 - 트리와 이진 트리

1. 트리의 이해

1) 트리

• 비선형 자료구조 : 원소들 간에 1:다 관계를 가짐
• 계층형 자료구조 : 원소들 간에 계층관계를 가짐
• 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조

2) 트리 자료 구조의 예 - 가계도

• 가계도의 자료 : 가족 구성원
• 자료를 연결하는 선 : 부모-자식 관계 표현

(1) 철수의 자식

• 성호, 영주, 진호

(2) 성호, 영주, 진호의 부모

• 철수

(3) 같은 부모의 자식들끼리는 형제 관계

• 성호, 영주, 진호는 형제 관계

(4) 조상

• 현재 위치에서 연결된 선을 따라 올라가면서 만나는 사람들
• 수영의 조상 : 승원, 성호, 철수

(5) 자손

• 현재 위치에서 연결된 선을 따라 내려가면서 만나는 사람들
• 성호의 자손 - 승우, 승완, 수영, 수철
• 선을 따라 내려가면서 다음 세대로 확장
• 가족 구성원 누구든지 자기의 가족을 데리고 분가하여 독립된 가계를 이룰 수 있음

3) 주요 용어

(1) 노드 node

• 트리의 원소
• 트리 A의 노드 : A,B,C,D,E,F,G,H,I,J,K,L

(2) 루트 노드 root node

• 트리의 시작 노드
• 트리 A의 루트 노드 : A

(3) 간선 edge

• 노드를 연결하는 선, 부모 노드와 자식 노드를 연결

(4) 형제 노드

• 같은 부모 노드의 자식 노드들
• B,C,D는 형제 노드

(5) 조상 노드

• 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
• K의 조상 노드 : F,B,A

(6) 서브 트리 subtree

• 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
• 각 노드는 자식 노드의 개수 만큼 서브 트리를 가짐

(7) 자손 노드

• 서브 트리에 있는 하위 레벨의 노드들
• B의 자손 노드 : E,F,K,L

(8) 차수 degree

(8-1) 노드의 차수

• 노드에 연결된 자식 노드의 수
• A의 차수 = 3, B의 차수 = 2, C의 차수 = 1

(8-2) 트리의 차수

• 트리에 있는 노드의 차수 중에서 가장 큰 값
• 트리 A의 차수 : 3

(8-3) 자식 노드가 없는 노드

• 리프 노드 또는 단말 노드

(9) 높이

(9-1) 노드의 높이

• 루트에서 노드에 이르는 간선의 수, 노드의 레벨
• B의 높이 = 1, F의 높이 = 2

(9-2) 트리의 높이

• 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨
• 트리 A의 높이 = 3

(10) 포리스트 forest

• 서브트리의 집합
• 트리 A에서 노드 A를 제거하면, A의 자식노드 B,C,D에 대한 서브 트리가 생기고 이들의 집합은 포리스트가 됨

2. 이진트리의 이해

1) 이진 트리

• 트리의 구조를 일정하게 제한하여 정의하면 트리의 구현과 연산이 단순 명확
• 모든 노드의 차수를 2 이하로 제한한 것이 이진트리 (Binary tree)

(1) 이진 트리의 모든 노드는 왼쪽 자식과 오른쪽 자식 노드 만을 가짐

• 부모 노드와 노드 수와의 관계 1:2
• 공백 노드도 자식 노드로 취급
• 0<= 노드의 차수 <= 2

(2) 이진 트리의 기본 구조

2) 이진 트리의 서브 트리

• 노드의 왼쪽 자식 노드를 루트로 하는 왼쪽 서브트리
• 노드의 오른쪽 자식 노드를 루트로 하는 오른쪽 서브트리

3) 이진 트리의 특성

• n개의 노드를 가진 이진트리는 항상 (n-1)개의 간선을 가짐
• 루트를 제외한 (n-1)개의 노드가 부모드와 연결되는 한개의 간선을 가짐

(1) 높이가 3이면서 최소의 노드를 갖은 이진트리와 최대 노드를 갖는 이진 트리

3. 이진 트리의 종류

1) 포화 이진 트리 (Full Binary Tree)

• 모든 레벨에 노드가 포화 상태로 차있는 이진 트리
• 높이가 h일 때, 최대의 노드 개수인(2(승h+1)-1)의 노드를 가진 이진 트리 루트를 1번으로 하여
  2(승h+1) -1 까지 정해진 위치에 대한 노드 번호를 가짐

• 계산식

2) 완전 이진트리 (Complete Binary Tree)

• 높이가 h이고 노드 수가 n개 일때 (단, h+1 <= n < 2((승h+1)-1)), 포화 이진 트리의 노드 번호
  1번부터 n번까지 빈 자리가 없는 이진 트리

(1) 노드가 12개인 완전 이진 트리

3) 편향 이진 트리 (Skewed Binary Tree)

• 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리
• 왼쪽 편향 이진 트리 : 모든 노드가 왼쪽 자식 노드만을 가진 편향 이진 트리
• 오른쪽 편향 이진 트리 : 모든 노드가 오른족 자식 노드만을 가진 편향 이진 트리