[자료구조] 13. 트리

1. 트리의 개념

트리의 특성

• 선형 자료구조: 배열, 리스트, 스택, 큐 등
• 트리(tree): 데이터를 계층적으로 저장하는 자료구조

 

트리의 특징

• 일대다 관계 표현
• 그래프 중에서 사이클을 포함하지 않는 연결 그래프
• 데이터 탐색, 삽입, 삭제에서 선형 구조보다 효율적

 

트리의 예시

• 가계도: 가족 구성원을 계층적으로 표현
• 기업 조직도: 부서와 직급 구조 표현
• 컴퓨터 디렉터리 구조: 폴더와 파일 체계 표현
• 결정 트리: 인공지능에서 의사결정을 위한 트리
• 운영체제 파일 시스템: 파일 저장 구조 표현
• 데이터베이스: 계층적 데이터 구성

 

 

2. 트리의 용어

트리의 구성 요소

• 루트 노드(root node): 트리의 최상위 노드 (부모 없음)
• 자식 노드(child node): 특정 노드의 하위 노드
• 부모 노드(parent node): 자식 노드를 가지는 노드
• 형제 노드(sibling node): 같은 부모를 가지는 노드

 

트리의 구조적 개념

• 리프 노드(leaf node): 자식 노드가 없는 노드
• 내부 노드(internal node): 리프 노드를 제외한 모든 노드
• 조상 노드(ancestor node): 루트에서 해당 노드까지 연결된 상위 노드
• 자손 노드(descendant node): 특정 노드에서 파생된 하위 노드
• 서브 트리(subtree): 특정 노드와 그 하위 노드로 이루어진 트리

 

트리의 속성

• 차수(degree): 특정 노드가 가지는 자식 노드 개수
• 트리의 차수: 트리 내에서 가장 큰 차수를 가진 노드의 차수
• 레벨(level): 루트에서 특정 노드까지의 깊이 (루트의 레벨은 0)
• 노드의 높이(height): 루트에서 해당 노드까지의 거리(간선 수)
• 트리의 높이: 트리 내 모든 노드의 높이 중 가장 큰 값
• 포리스트(forest): 트리에서 루트를 제거한 후 남은 서브 트리의 집합

 

 

3. 트리의 종류

일반적인 트리 구조

• 일반 트리(general tree): 자식 노드 개수 제한 없음
• 이진 트리(binary tree): 각 노드가 최대 2개의 자식 노드를 가짐

 

특수한 트리 유형

• 순서 트리(ordered tree): 형제 노드 간 순서가 중요한 트리
• 비순서 트리(unordered tree): 노드 간 순서가 중요하지 않은 트리
• 닮은 트리(similar tree): 구조는 같지만 데이터가 다른 트리
• 편향 트리(skewed tree): 한쪽(왼쪽 또는 오른쪽)으로 치우친 트리

 

 

4. 트리의 표현 방법

트리 표현 방식

• 집합 표현: {A, {B, {E, F}}, {C}, {D}}
• 중첩된 괄호 표현: A(B(E, F), C, D)

 

트리 표현 방식별 특징

• 가변적인 노드 구조: 노드마다 자식 개수가 다름
• 고정된 노드 구조: 일정한 포인터 개수로 표현
• 왼쪽-자식 오른쪽-형제 표현 (Left-Child Right-Sibling Representation)

- 왼쪽 포인터 → 첫 번째 자식 노드

- 오른쪽 포인터 → 다음 형제 노드

 

이진 트리 변환

• 일반 트리를 이진 트리로 변환하는 방법

- 부모 노드가 첫 번째 자식 노드를 가리킴

- 형제 노드끼리는 오른쪽 링크로 연결

- 모든 일반 트리는 이진 트리로 변환 가능

---

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