2.1 트리의 기본 구성 요소
트리는
순환이 없는 그리고
연결된 특별한 종류의 그래프야. 트리에서는 모든 노드 쌍 사이에 유일한 경로가 있어서 구조가
계층적이야.
트리의 기본 구성 요소:
1. 노드:
- 데이터를 포함하는 트리의 기본 요소.
- 예를 들어, 다이어그램에서 각 원이 노드를 나타내.
2. 루트:
- 부모 노드가 없는 노드. 트리의 시작점이야.
- 예를 들어, 다이어그램의 상단 노드.
3. 리프:
- 자식 노드가 없는 노드. 트리의 "끝"에 위치해.
- 예를 들어, 다이어그램의 하단에 있는 노드들.
4. 엣지:
- 노드 간의 연결. 부모-자식 관계를 정의해.
- 예를 들어, 다이어그램에서 노드를 잇는 선들.
5. 서브트리:
- 노드와 그 자손들로 구성된 트리의 부분 집합.
- 예를 들어, 한 노드에서 나오는 트리의 가지.
트리의 중요한 특성:
1. 트리의 높이:
- 루트에서 가장 먼 리프까지의 경로 길이.
- 예를 들어, 다이어그램에서의 레벨 수.
2. 노드의 깊이:
- 루트에서 특정 노드까지의 경로 길이.
- 예를 들어, 루트에서 특정 노드까지의 레벨 수.
2.2 이진 트리
다양한 종류의 트리가 있어. 간단한 것부터 시작해 보자.
이진 트리는 각 노드가 두 개 이하의 자식 노드를 가지는 트리야. 이들을 왼쪽과 오른쪽 자손이라고 부르지.
이진 트리의 예:
특별한 유형의 이진 트리:
완전 이진 트리:
마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 왼쪽에 위치해.
완벽한 이진 트리:
모든 내부 노드는 정확히 두 개의 자식 노드를 가지고, 모든 리프는 동일한 레벨에 있어.
균형 잡힌 이진 트리:
어떤 노드의 서브트리 높이 차이가 1을 초과하지 않아야 해.
이진 탐색 트리:
어떤 노드에 대해서도, 그 노드의 왼쪽 서브트리는 더 작은 값의 노드만 포함하고, 오른쪽 서브트리는 더 큰 값의 노드만 포함해.
2.3 n-ry 트리
n-ry 트리는 각 노드가 n 이하의 자식 노드를 가질 수 있는 트리야.
특별한 유형의 n-ry 트리:
1. Ternary Tree (삼진 트리):
각 노드가 세 개 이하의 자식 노드를 가질 수 있어.
2. k-ary Tree (k-ary 트리):
각 노드가 k 이하의 자식 노드를 가질 수 있어.
3-ary 트리 예시 (각 노드가 세 개 이하의 자식 노드를 가짐):
2.4 트리의 사용 예시
1. 파일 시스템
트리의 적용: 운영 체제에서 파일과 폴더의 계층적 구조 표현.
루트 노드는 루트 디렉터리를 나타내고, 내부 노드들은 폴더, 리프는 파일이야. 작업에는 파일과 폴더의 생성, 삭제, 이동이 포함돼.
2. 의사 결정 트리
트리의 적용: 분석과 머신 러닝에서의 의사 결정.
내부 노드는 질문이나 조건을, 가지는 가능한 답변을, 리프는 최종 결정이나 행동을 나타내. 예를 들어, 증상을 바탕으로 한 의료 진단.
3. XML/HTML 문서
트리의 적용: XML 또는 HTML 형식의 구조화된 데이터 표현.
루트 노드는 전체 문서를, 내부 노드는 태그와 요소, 리프는 텍스트 노드와 속성을 나타내. 이는 문서의 내용을 파싱하고 조작하는 데 도움을 줘.
4. 조직 구조
트리의 적용: 조직 및 회사의 계층 구조 표현.
루트 노드는 CEO를, 내부 노드는 매니저와 부서를, 리프는 직원을 나타내. 이는 조직 구조를 시각화하고 관리하는 데 도움이 돼.
5. 체스 게임
트리의 적용: 게임에서의 가능한 이동 표현.
루트 노드는 게임의 초기 상태를, 내부 노드는 가능한 이동을, 리프는 게임의 최종 상태를 나타내. 이는 체스 프로그램에서 전략을 계획하고 결정을 내리는 데 도움이 돼.
GO TO FULL VERSION