자료구조 27강 - 트리

계층구조(Hierarchy)의 공통점

 

• 하나의 근원(root)으로부터 파생됨
• 한 노드가 여러 개의 노드로 전파됨
• 순환하는 경로(cycle path)가 없음

 

 

트리

 

- 트리의 정의

 

1. 루트(root)라는 특별한 노드가 하나 있음
2. 모든 노드는 부모자식관계(parent-child relation)라는 1:1 관계에 재귀적으로 연결되어 있음
3. 순환하는 경로(cycle path)가 없음

 

- 트리의 용어

 

ⓞ Node(Vertex) : 하나의 정보의 단위, 저장단위

ⓞ Edge : 연결된 Node의 쌍

 

ⓞ Root Node : 트리의 최상위 노드, 부모 노드가 없는 노드

ⓞ Leaf Node : 자식 노드가 없는 노드

ⓞ Internal Node : Leaf Node가 아닌 모든 노드

 

ⓞ Parent Node : 연결된 한 쌍의 노드들 중에서

Root Node에 더 가까운 노드를 다른 노드의 Parent Node라고 한다

반드시 A는 B의 Parent Node라고 표현하며 A는 Parent Node는 틀린 표현이다

ⓞ Child Node : 연결된 노드들 중에서 Root Node에서 더 먼 노드

ⓞ Sibling Node : 같은 노드를 Parent Node로 공유하는 노드들

 

ⓞ Ancestor Node(조상 노드) : Root Node로부터 어떤 Node에 이르는 경로에 있는 노드들

ⓞ Descendent Node(후손 노드) : A가 B의 조상 노드이면 B는 A의 후손 노드

 

ⓞ Subtree(부분 트리) : 어떤 트리의 노드를 Root Node로 하며 트리의 정의를 만족시키는 Node와 Edge들의 집합

 

ⓞ Degree of a node : 한 노드가 갖는 자식 노드의 개수

ⓞ Degree of a tree : 한 트리에 속한 노드들의 Degree들의 최대 값

ex. Binary tree : 2 degree, Ternary tree : 3 degree, k-ary tree : k degree

 

ⓞ Depth of a node(노드의 깊이) : Leaf Node까지의 Maximum Distance로

Root Node의 Depth는 1, Child Node는 Parent Node의 Depth+1

ⓞ Depth(height) of a tree(트리의 깊이,높이) : 한 트리에 속한 노드들의 Depth들의 최대값

 

- 트리의 자료구조

 

ⓞ 노드

 

• 저장할 데이터
• 자식 노드의 수
• 자식 노드에 대한 포인터