[자료구조] 트리 (Tree)

1. 트리(Tree)

개요

• 노드와 링크로 구성된 자료 구조
• 계층적 구조를 나타낼 때 사용할 수 있음

 

트리의 구조

출처 : www.geeksforgeeks.org

• 노드(Node):  자료 값을 담고 있는 단위
• 에지(Edge): 노드 간의 연결선. (=간선, link, branch)
• 루트 노드(Root): 부모가 없는 노드, 트리의 최상단에 위치
• 잎새 노드(Leaf): 자식이 없는 노드
• 내부 노드(Internal): 잎새 노드를 제외한 모든 노드
• 부모(Parent): 직접 연결된 두 노드 중 상위의 노드
• 자식(Child):  직접 연결된 두 노드 중 하위의 노드
• 형제(Sibling): 같은 부모를 가지는 노드
• 깊이(Depth): 루트에서 어떤 노드까지의 간선의 수. 루트의 깊이는 0.
• 레벨(Level): 트리의 특정 깊이를 가지는 노드 집합
• 높이(Height): 트리에서 가장 큰 레벨 값. 리프 노드에서부터 0이며, 루트 노드의 높이가 가장 높음.
• 크기(Size): 자신을 포함한 자식 노드의 개수 
• 차수(Degree): 각 노드가 지닌 가지의 수

 

트리의 특징

• 하나의 노드에서 다른 노드로 이동하는 경로는 유일
• 노드가 N개인 트리의 Edge 수는 N-1개 
• 사이클이 존재하지 않음
• 모든 노드는 서로 연결되어 있음

2. 이진 트리(Binary Tree)

개요

• 각 노드는 최대 2개의 자식을 가질 수 있음
• 자식 노드는 좌우를 구분함

이진 트리의 종류

1) 포화 이진 트리(Perfect Binary Tree)

모든 레벨의 노드들이 꽉 채워져 있는(자식을 둘 씩 가지는) 트리

2) 완전 이진 트리(Complete Binary Tree)

마지막 레벨을 제외한 나머지 노드들이 모두 채워져 있는 트리

3) 균형 이진 트리(Balanced Binary Tree)

모든 노드에 대해서, 좌우 서브 트리의 높이의 차이가 1 이내인 트리

 

이진 트리의 특징

• 포화 이진 트리의 높이가 h 일 때, 노드의 수는 2^(h + 1) - 1 개 
• 포화(or 완전) 이진 트리의 노드가 N 개일 때, 높이는 logN
• 이진 트리의 노드가 N 개일 때, 최대 가능 높이는 N

이진 트리의 순회(Traversal)

• 모든 노드를 한번씩 방문하는 연산
• 종류: 전위 순회, 중위 순회, 후위 순회, 레벨 순회

전위 순회(PreOrder)

방문 순서: 현재 노드 → 왼쪽 노드 → 오른쪽 노드

중위 순회(InOrder)

방문 순서: 왼쪽 노드 → 현재 노드 → 오른쪽 노드

후위 순회(PostOrder)

방문 순서: 왼쪽 노드 → 오른쪽 노드 → 현재 노드