[알고리즘] 13. 트리

1. 트리(Tree) 개념

1) 트리 구조란?

• 회사 조직표나 컴퓨터의 폴더 구조처럼 상위 요소에서 하위 요소로 확장되는 구조.

 

2) 트리(Tree)

• 원소들 간에 일대다(1:n) 관계를 가지는 비선형 자료구조.

• 계층적인 관계를 가지는 자료구조로, 상위 원소에서 하위 원소로 확장되는 형태.

 

3) 루트 트리(Rooted Tree)

• 트리의 최상위 정점을 루트(Root) 라고 하며, 루트가 지정된 트리를 루트 트리라고 함.

• 루트 이외의 모든 정점들은 루트 아래 계층적으로 배치됨.

• 다양한 형태의 트리는 루트를 지정함으로써 루트 트리로 변형 가능.

• 루트 트리의 정의:

- 루트(Root) 노드: 트리의 최상위 정점.

- 서브 트리(Subtree): 루트 외의 나머지 노드들은 서로 분리된 집합(T1, T2, ..., Tm)으로 구성되며, 각 Ti는 다시 루트 트리가 됨.

 

 

2. 트리의 종류

1) 순서 트리(Order Tree)

• 정점의 순서에 따라 의미가 달라지는 트리.

• 왼쪽 자식과 오른쪽 자식의 위치에 따라 의미가 달라질 수 있음.

 

2) K진 트리(K-ary Tree)

• 모든 정점의 차수가 K 이하인 트리.

• K=2인 경우 이진 트리(Binary Tree) 라고 함.

 

3) 이진 트리(Binary Tree)

• 모든 노드가 최대 2개의 자식을 가질 수 있는 트리.

• 서브 트리 간의 순서가 존재하며, 구현이 용이함.

 

완전 이진 트리(Complete Binary Tree)

• 높이가 h일 때, 레벨 1부터 h-1까지 모든 정점이 2개씩 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리.

• 포화 이진 트리(Full Binary Tree)와 노드 번호가 일치함.

 

포화 이진 트리(Full Binary Tree)

• 높이가 h일 때, 레벨 1부터 h까지 모든 정점이 2개씩 채워진 트리.

 

편향 이진 트리(Skewed Binary Tree)

• 왼쪽 또는 오른쪽 자식만 가지는 트리.

 

 

3. 트리의 표현 방법

1) 이진 트리를 표현하는 방법

• 배열과 연결 리스트를 사용하여 표현 가능.

• 왼쪽 자식과 오른쪽 자식을 구분하여 저장해야 함.

 

2) 배열을 이용한 표현

• 노드 값을 1차원 배열에 저장하고, 자식 노드의 인덱스를 이용하여 관계를 나타냄.

• 부모와 자식 노드의 관계:

- 부모 노드 인덱스 = i/2

- 왼쪽 자식 노드 인덱스 = 2i

- 오른쪽 자식 노드 인덱스 = 2i+1

• 배열을 이동시키거나 크기를 미리 정해야 하는 불편함이 있음.

 

3) 연결 리스트를 이용한 표현

• 포인터를 이용하여 부모 노드가 자식 노드를 가리키는 방식.

• 각 노드는 왼쪽 포인터, 데이터, 오른쪽 포인터 로 구성됨.

• 새로운 정점 추가 및 삭제가 용이하여 배열보다 많이 사용됨.

---

이 내용은 휴넷사회복지평생교육원의 알고리즘 강의를 듣고 정리한 것입니다.