이산 수학 - 15 트리

트리의 개념

1. 트리의 정의

2. 노드의 종류

3. 트리의 용어

 

 

 

트리의 정의

- 루트 노드를 가지고 있고, 모든 노드들 사이에 단순 경로가 존재하는 비순환 연결 그래프

- 루트 노드 : 나무의 뿌리에 해당하는, 트리에 가장 높은 곳에 위치하는 노드

- 경로 : 노드에서 노드로 가는, 중복되지 않은 연결선들의 나열

- 단순 경로 : 시작과 끝노드가 중복되는것을 제외하고 노드가 중복되지 않는 경로

- 사이클 : 시작 노드와 끝 노드가 같은 경로

- 비순환 그래프 : 사이클이 존재하지 않는 그래프 -> 트리에는 루프가 없음

- 연결 그래프 : 서로 다른 모든 노드들 사이에 항상 경로가 있는 그래프

 

 

부모 노드

- 한단계 상위 노드

- 노드 A는 노드 B, C, D의 부모 노드

- 노드 B는 노드 E, F의 부모 노드

- 노드 D는 노드 G의 부모 노드

 

 

자식 노드

- 한단계 하위 노드

- 노드 B, C, D는 노드 A의 자식 노드

- 노드 E, F는 노드 B의 자식 노드

- 노드 G는 노드 D의 자식 노드

 

 

형제 노드

- 부모가 같은 노드

- 노드 B, C, D는 서로 형제 노드

- 노드 E, F는 서로 형제 노드

 

 

 

리프 노드

- 자식 노드가 없는 노드

- 노드 C, E, F, G는 리프 노드

 

중간 노드

- 루프 노드나 리프 노드가 아닌 노드

- 노드 B와 D는 중간 노드

 

조상 노드

- 루트 노드에서 임의의 한 노드에 이르는 경로에 포함된 모든 노드들

- 노드 A, B, E는 노드 H의 조상 노드

- 노드 A는 노드 D의 조상 노드

- 부모 노드는 조상 노드

- 루트 노드를 제외한 모든 노드는 조상 노드를 가짐

 

자손 노드

- 한 노드에서 임의의 리프 노드에 이르는 경로에 포함된 모든 노드들

- 노드 A의 자손 노드는 노드 B, C, D, E, F, G, H

- 자식 노드는 자손 노드임

 

 

서브 트리

- 임의의 한 노드를 루트 노드로 하는 트리

- 서브 트리의 개수 = 노드 개수

 

 

노드의 차수

- 노드의 차수 = 자식 노드의 개수

- A 노드 차수 = 3

- B 노드 차수 = 2

- C 노드 차수 = 0

- 트리에서의 노드의 차수 != 그래프에서의 노드의 차수

 

트리의 차수

- 각 노드의 차수의 최대값

- A 노드의 차수 = 3

- B 노드의 차수 = 2

- C 노드의 차수

=> 트리의 차수 = 3

- 트리의 차수 != 그래프의 차수

 

레벨

- 루트 노드는 레벨 0

- 자식 노드로 가면서 레벨이 한 단계 씩 증가

 

 

트리의 높이(또는 깊이)

- 트리의 최대 레벨

 

 

트리의 성질

1. 노드의 개수와 연결선 개수의 관계

2. 트리에 대한 정리

 

노드의 개수와 연결선의 개수 사이의 관계

- 트리의 노드의 개수를 v, 연결선 개수를 e라 하면

=> e = v - 1

 

 

2. 트리에 대한 정리

- n 개의 노드를 가지는 연결 그래프 T에 대해 다음은 동치임

- T는 트리이다.

- T의 연결선의 개수는 n - 1 이다.

- T에서 연결선을 하나 제거하면 단절 그래프가 된다.

- T의 임의의 한 노드에서 그 노드와 다른 노드로 가는 경로가 유일하게 존재한다.

 

 

 

 

이진 트리

1. 이진 트리의 정의

2. 이진 트리의 종류

3. 이진 트리의 표현

 

 

 

이진 트리 Binary Tree

- 차수가 2이하(자식 노드가 2개 이하)인 트리

 

 

이진 트리에 관한 정리

- 레벨 k에서 이진 트리가 가질 수 있는 최대 노드 수 = 2^k

- 높이가 m인 이진 트리가 가질수 있는 최대 노드 수 = 2^(m + 1) - 1

- 높이가 m인 이진 트리가 가질 수 있는 최소 노드 수 = m + 1

 

포화 이진 트리

- 모든 레벨에 노드가 꽉 차서 레벨을 늘이지 않는 이상 노드 추가가 더이상 불가능한 트리

- 높이가 h인 포화 이진 트리의 노드 수 = 2^(h + 1) -1

- 높이가 h인 포화 이진 트리의 리프 노드 수 = 2^h

 

 

 

완전 이진 트리

- 높이가 h일 때, 레벨 0 부터 레벨 h - 1까지의 노드로 이루어진 트리가 포화 이진 트리이고, 레벨 h에서는 왼쪽부터 노드가 채워진 트리

- 2^h <= 높이가 h인 완전 이진 트리의 노드 수 <= 2^(h + 1) - 1

 

편향 이진 트리 skwed binary tree

- 리프 노드를 제외한 모든 노드들이 왼쪽 자식 노드만을 가지고 있거나 아니면 모두 오른쪽 자식 노드만 가지고 있는 트리

- 높이가 h인 편향 이진 트리의 노드 수 = h + 1

 

배열을 이용한 구현

- 배열 : 같은 자료형을 가진 자료들을 메모리에 연속적으로 저장한 자료 구조

-> 인덱스(index)를 이용하여 저장된 자료에 접근 가능

 

 

배열을 이용한 이진 트리 구현

- 트리의 높이가 h면, 높 이가 h인 포화 이진 트리의 노드 번호를 배열의 인덱스로 사용하여 트리 표현

-> 인덱스 계산 편의성을 위해 루트 노드의 경우 인덱스 1을 사용

 

배열을 이용한 이진 트린 구현시 포화 이진 트리를 사용하는 경우의 장점

- 부모 노드의 인덱스가 n이면, 왼쪽 자식 노드의 인덱스는 2n, 오른쪽 자식 노드의 인덱스는 2n + 1

- 자식 노드의 인덱스가 이면 부모 노드의 인덱스 내림 (n/2) -> 내림(1.5) = 1, 내림(2.5) = 2

 

포화 이진 트리를 사용한 경우 단점

- 메모리 낭비가 발생

 

 

 

연결 리스트

- 데이터를 저장할때 다음 순서의 자료가 있는 위치(포인터)를 데이터에 포함시키는 방식으로 저장

 

연결 리스트를 이용한 구현

- 트리에서는 부모 노드와 자식 노드라는 관계가 존재

- 이를 위해 이중 연결 리스트를 사용

- 부모 노드를 나타내는 데이터에 자식 노드의 위치를 함께 저장

 

 

연결 리스트를 이용한 이진 트리 예시