📝 트리의 정의
그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조로 서로 다른 두 노드간의 연결이 하나뿐인 그래프이다.
🎯 트리의 특징
- DAG(Directed Acyclic Graph), 방향성이 있는 비순환 그래프의 한 종류이다.
- 일반적으로 대상 정보의 각 항목들을 계층적으로 구조화할 때 사용하는 비선형 자료구조이다. ex) OS-FileSystem의 디렉터리 구조, 조직도
- 트리의 구조는 데이터를 저장 하는 것 보다 효과적으로 데이터 탐색을 하기 위해 사용된다.
- 트리는 부모(parent)와 자식(child)의 계층적인 관계로 표현된다.
- 트리는 사이클이 불가능하고 자체 간선도 불가능하다.
- 트리에서 루트노드를 제외한 모든 노드는 단 하나의 부모노드를 가진다.
- 트리내에 또 다른 트리가 있는 재귀적 자료구조이다.
트리 순회
트리의 각 노드를 체계적인 방법으로 탐색하는 과정을 의미한다.
노드를 탐색하는 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나뉜다.
1) 전위 순회 (Preorder)
- 루트노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 순회
- 깊이 우선 순회라고도 한다.
2) 중위 순회 (Inorder)
- 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 의 순서로 순회
- 대칭 순회라고도 한다.
3) 후위 순회 (Postorder)
- 왼쪽 서브트리 -> 오른쪽 서브트리 -> 노드 의 순서로 순회
이진 트리 (Binary Tree)
- 트리 자료구조의 여러 가지 유형 중 가장 기본이 되는 트리는 이진 트리(Binary Tree) 구조이다.
- 이진 트리는 2개 이하의 자식노드를 가진다. 자식노드가 없거나 1개의 자식노드만 가질 수도 있다.
- 2개의 자식노드 중에서 왼쪽의 노드를 Left Node라고 하고, 오른쪽의 노드를 Right Node라고 한다.
이진 트리 종류
1) 편향 이진 트리 (Skewed Binary Tree)
- 편향 이진 트리는 하나의 차수로만 이루어져 있는 경우를 의미한다.
- 배열(리스트)와 같은 선형 구조로 'Leaf Node'(가장 하위 노드) 탐색 시 데이터를 전부 탐색해야 한다는 단점이 있어 효율적이지 못하다.
✔ 이를 보완하기 위해 높이 균형 트리라는 것이 있다.
2) 포화 이진 트리 (Full Binary Tree)
- 포화 이진 트리는 'Leaf Node'를 제외한 모든 노드의 차수가 2개로 이루어져 있는 경우를 의미한다.
- 포화 이진 트리는 해당 차수에 몇 개의 노드가 존재하는지 바로 알 수 있어 노드의 개수를 파악할 때 용이한 장점이 있다.
3) 완전 이진 트리 (Complete Binary Tree)
- 포화 이진 트리와 같은 개념으로 트리를 생성하지만, 모든 노드가 왼쪽부터 차근차근 생성되는 이진 트리를 의미한다.
✔ 힙(Heap)은 완전 이진 트리의 일종이다
참고자료
도라에몽 암기빵