[자료구조]트리(Tree)의 개념

트리

• 노드로 이루어진 자료구조이다.
• 그래프의 일종으로, 순환이 없는 연결 그래프이다.(Cycle 없음)
• 노드(Node)와 간선(Edge)으로 이루어져 있으며, 하나의 루트 노드를 갖는다.
• 모든 노드는 0개 이상의 자식 노드를 가진다.
• 계층적 관계를 나타내는 비선형 자료구조이다.
• 모든 자식 노드는 하나의 부모 노드를 가질 수 있다.
• 노드가 N개일 때, 간선은 N-1개 이다.

 

트리의 구조

트리의 구조는 아래와 같다.

트리의 구조

• 루트 노드(root node) : 부모 노드가 없는 최상위 노드.
• 리프 노드(leaf node) : 자식 노드가 없는 노드. ( = terminal node)
• 내부 노드(internal node) : 리프 노드가 아닌 노드.
• 부모 노드(parent node) : 노드 C가 노드 F를 가리킬 때, 노드 C를 노드 F의 부모 노드라고 한다.
• 자식 노드(child node) : 노드 C가 노드 F를 가리킬 때, 노드 F를 노드 C의 자식 노드라고 한다.
• 형제(silbling) : 부모 노드가 서로 같은 노드들. (노드 F와 노드 G)

 

기타 중요 개념

• 노드의 차수(degree) : 자식 노드의 개수. (노드 A의 차수는 2)
• 트리의 차수 : 트리에 속한 노드들의 차수 중 가장 큰 수. (위 트리의 차수는 2)
• 노드의 깊이(depth) : 루트 노드에서 해당 노드까지의 경로 길이. (노드 E의 깊이는 2)
• 트리의 깊이 : 트리에 속한 노드들의 깊이 중 가장 큰 수. 최대 레벨.(위 트리의 깊이은 2)
• 노드의 레벨(level) : 노드의 깊이 + 1 . 특정 깊이를 가지는 노드의 집합을 레벨이라고도 한다.
• 노드의 크기(size) : 자기 자신과 모든 자손 노드의 개수

 

트리의 종류

• 이진 트리(Binary Tree) : 모든 노드의 자식 노드가 최대 두 개인 트리
• 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있고, 마지막 노드는 왼쪽부터 있는 이진 트리
• 정 이진 트리(Full Binary Tree) : 모든 노드가 0개 혹은 2개의 자식 노드를 갖는 이진 트리
• 포화 이진 트리(Perfect Binary Tree) : 모든 내부 노드가 2개의 자식 노드를 갖는 이진 트리
• 사향 이진 트리(Skewed Binary Tree) : 모든 내부 노드가 한쪽 방향으로 1개의 자식 노드만을 가진 이진 트리