트리 구조는 계층적 관계를 표현하는 비선형 자료구조로, 루트 노드를 중심으로 자식 노드들이 분기되는 형태입니다. 사이클이 없고 한 방향으로만 확장되는 것이 특징입니다.
🌳 트리 구조의 기본 개념
- 트리(Tree): 그래프의 일종으로, 순환이 없는 연결 구조. 계층적 데이터를 표현하는 데 적합.
- 루트 노드(Root Node): 트리의 시작점이자 최상단 노드.
- 부모 노드(Parent Node): 자식 노드를 가지는 노드.
- 자식 노드(Child Node): 특정 부모를 가지는 하위 노드.
- 리프 노드(Leaf Node): 자식이 없는 말단 노드.
- 서브트리(Subtree): 특정 노드를 루트로 하는 하위 트리.
- 깊이(Depth): 루트에서 특정 노드까지의 거리.
- 높이(Height): 루트에서 가장 깊은 리프까지의 거리12.
🧩 트리 구조의 주요 특징
- 비선형 구조로, 배열이나 연결 리스트와 달리 복잡한 관계를 표현 가능.
- 사이클 없음: 노드 간 순환이 없어 탐색이 명확함.
- 계층적 표현: 조직도, 파일 시스템, 게임 AI 등에서 자주 사용됨.
- 경로 유일성: 루트에서 특정 노드까지의 경로가 하나뿐임13.
🌲 트리의 주요 종류
| 종류 |
설명 |
용도 |
| 이진 트리 |
모든 노드가 최대 2개의 자식 노드를 가짐 |
알고리즘 학습용 |
| 이진 탐색 트리(BST) |
왼쪽 자식 < 부모 < 오른쪽 자식 |
정렬된 탐색에 효율적 |
| 균형 트리(AVL, Red-Black) |
트리 높이를 균형 있게 유지 |
실무에서 성능 최적화 |
| 힙(Heap) |
최대/최소값 빠르게 찾음 |
우선순위 큐 구현 |
| 트라이(Trie) |
문자열 검색에 특화 |
자동완성, 사전 검색 등 |
Sources: 12
📁 활용 예시