1. 트리 구조 / 토폴로지 (Tree Topology, Tree Structure, Tree Data Structure)
ㅇ 1 이상의 노드로 구성된 유한 집합
- 마치 나무 가지 처럼 계층적(Hierarchical)으로 연결되는 논리적/수학적 구조(체)
2. 트리의 용도
ㅇ 데이터의 포함 관계, 계층 관계 등을 나타내는데 유용
- 족보 상의 조상-자손 관계를 나타내는 가계도, 조직 체계도 등
ㅇ 데이터의 분류 등
ㅇ 데이터의 저장 구조로써의 파일시스템 등
ㅇ 데이터의 정렬 및 탐색 용도 등
ㅇ 네트워크 형상 표현 등
- 통신 네트워크에의 트리 구조 적용 : 트리형 토폴로지 (Tree Topology)
. 망형(Mesh Topology), 링형(Ring Topology)에 비해 장애 확산방지 및 고립에 유리함
- 例) 이더넷 스위치 연결 등
3. 트리의 정의
ㅇ 반드시 루트(Root)라는 특별한 노드가 하나 있어야 함
ㅇ 나머지 노드들은 다시 각각 독립된 부분 트리 (subtree, 서브트리)가 됨
- 즉, 재귀적(순환적)인 방법으로 트리를 정의할 수 있음
* 재귀적으로 정의된(recursively defined) 자기 참조(self-referential) 자료 구조 임
4. 트리의 특징
ㅇ 자료의 단순 나열이 아닌 연관 관계(계층 관계, 포함 관계 등)를 표현 ☞ 관계 (Relation) 참조
- 노드 간에 부모 자식 관계를 갖음
. 나무나 족보 처럼 노드 사이의 관계가 계층적(Hierarchy) 관련성을 갖음
. 트리는 조상과 자손 처럼 포함 관계 등을 효율적으로 표현할 수 있음
ㅇ 트리는 그래프의 일종
- 트리는 정점(노드) 및 선분(가지)으로 형성되는 그래프의 특수한 경우
. 서로 독립된 노드들이 선분에 의해서 연결된 계층형 자료구조
- 즉, 순환 루프를 포함하지 않는 연결 그래프의 일종
ㅇ 단순 순환(Loop) 없이, 연결된 무방향 그래프 구조임
- 모든 노드 쌍 간에 유일한 단순 경로 만 존재함
. 즉, 임의 노드들 간에 연결은 하나의 경로로 만 가능
ㅇ 그래프 및 트리 구조는 비선형 자료구조에 속함
- 노드들의 속성을 선형 자료구조로 표현할 수 없는 경우에 사용됨
5. 트리의 표현 및 구현
ㅇ 트리의 표현 방법
- 거꾸로 세운 나무 형상, 중첩된 괄호(Nested Parenthesis), 중첩된 집합(Nested Set),
들여쓰기(Indentation) 표현법 등
ㅇ 트리의 구현 방법
- 통상, 연결 리스트 구조를 이용하여 재귀적으로 구현
- 자료 저장 구조로써 트리 구현법
. 왼쪽 자식-오른쪽 형제 표현법(Left Child-Right Sibling Representation,LC-SR)
.. 왼쪽 링크에 자식을 놓고, 오른쪽 링크에 형제 노드를 놓는 표현 방법
.. 각 노드 마다 2개의 포인터를 갖고 표현 가능
.. 이는, LC-RS Binary Tree 라 하여, 범용 트리를 이진 트리로 변환 가능한 표현법 임
6. 트리의 종류
※ ☞ 트리 종류 참조
- 순서트리, 이진트리, 이진탐색트리, 균형트리 등
7. 트리의 용어들
※ ☞ 트리 용어 참조
- 노드, 부 트리 갯수, 깊이, 차수, 단말노드, 자식, 부모, 루트 등
8. 트리의 연산
ㅇ 트리의 생성
- 例) createTree(data, leftChild, rightChild)
. 데이터값을 탑재하고, 왼쪽,오른쪽 자식 노드를 취하는/초기화하는 트리의 생성
ㅇ 트리의 순회 ☞ 트리 순회 (Tree Traversal) 참조
- 일정 순서로 트리 내 모든 노드를 방문하는 것
- 방문 순서에 따른 구분 : 전위 순회 (Preorder), 중위 순회 (Inorder), 후위 순회 (Postorder)