CS학습
트리 Tree: 노드 기반의 계층적 데이터 구조
트리는 데이터를 계층적으로 표현하는 자료구조이다. 각 노드는 0개 이상의 자식 노드를 가질 수 있으며, 루트 노드에서 시작하여 자식 노드를 따라가면서 데이터를 탐색한다. 그래프의 특수한 형태로, 사이클이 없는 연결 그래프(acyclic connected graph)이다.
송민성4분 읽기
1. 개념
트리(Tree)는 노드(Node)라고 불리는 데이터의 집합으로 구성된다. 각 노드는 데이터를 저장하고, 다른 노드와의 연결 관계를 나타낸다. 특별히, 트리는 하나의 루트 노드(Root Node)를 가지며, 루트 노드는 부모 노드(Parent Node)가 없는 노드이다. 각 노드는 자식 노드(Child Node)를 가질 수 있으며, 자식 노드의 부모 노드는 해당 노드이다. 리프 노드(Leaf Node)는 자식 노드를 가지지 않는 노드이다.
- 노드(Node): 데이터를 저장하는 기본 단위
- 루트 노드(Root Node): 트리의 최상위 노드, 부모 노드가 없음
- 부모 노드(Parent Node): 자식 노드를 가지는 노드
- 자식 노드(Child Node): 부모 노드에 연결된 노드
- 리프 노드(Leaf Node): 자식 노드가 없는 노드
- 깊이(Depth): 루트 노드부터 특정 노드까지의 경로 길이
- 높이(Height): 루트 노드부터 리프 노드까지의 최장 경로 길이
2. 왜 사용하는가
트리는 계층적인 관계를 표현해야 하는 경우에 유용하다. 예를 들어, 파일 시스템, 조직 구조, DOM(Document Object Model) 등이 트리의 형태로 표현될 수 있다. 또한, 트리는 검색, 정렬, 데이터 압축 등 다양한 작업에 효율적으로 사용될 수 있다.
3. 동작 원리
트리의 기본적인 동작은 다음과 같다.
- 탐색(Traversal): 트리의 모든 노드를 방문하는 과정을 의미한다. 대표적인 탐색 방법으로는 깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS)이 있다.
- 삽입(Insertion): 트리에 새로운 노드를 추가하는 과정이다. 삽입 위치는 트리의 종류에 따라 달라질 수 있다.
- 삭제(Deletion): 트리에서 특정 노드를 제거하는 과정이다. 삭제 후 트리의 구조를 유지해야 한다.
4. 코드 예제
다음은 Python을 사용하여 트리를 구현하고, 깊이 우선 탐색을 수행하는 예제 코드이다.
python
class Node:
def __init__(self, data):
self.data = data
self.children = []
def dfs(node):
print(node.data)
for child in node.children:
dfs(child)
# 트리 생성
root = Node('A')
node_b = Node('B')
node_c = Node('C')
node_d = Node('D')
node_e = Node('E')
root.children = [node_b, node_c]
node_b.children = [node_d, node_e]
# 깊이 우선 탐색 수행
dfs(root)5. 시간 복잡도 또는 성능 특성
- 탐색: 트리의 높이에 따라 결정된다. 최악의 경우(skewed tree) O(n), 균형 트리(balanced tree)의 경우 O(log n)이다.
- 삽입/삭제: 삽입/삭제 위치에 따라 다르다. 균형 트리의 경우 O(log n), 최악의 경우 O(n)이다.
6. 실무 사용 사례
- 파일 시스템: 디렉토리와 파일을 트리 구조로 표현
- DOM (Document Object Model): 웹 페이지의 구조를 트리 구조로 표현
- 데이터베이스 인덱스: B-트리, B+트리 등을 사용하여 데이터 검색 속도 향상
- 의사 결정 트리: 머신러닝 모델에서 사용되는 트리 기반 알고리즘
- 라우팅 알고리즘: 네트워크 경로를 트리 구조로 표현
7. 주의할 점
- 트리의 종류에 따라 성능 특성이 달라진다. 예를 들어, 균형 트리는 검색, 삽입, 삭제 성능이 뛰어나지만, 구현이 복잡하다.
- 트리 구조를 사용할 때는 메모리 사용량을 고려해야 한다. 각 노드는 데이터를 저장하고, 자식 노드를 가리키는 포인터를 저장하므로, 노드 수가 많아지면 메모리 사용량이 증가할 수 있다.
- 재귀 함수를 사용할 때는 스택 오버플로우(Stack Overflow)를 방지하기 위해 재귀 깊이를 제한해야 한다.
8. 핵심 정리
트리는 계층적인 관계를 표현하는 데 유용한 자료구조이다. 트리의 종류에 따라 성능 특성이 달라지므로, 문제의 특성에 맞는 트리를 선택해야 한다. 트리는 파일 시스템, DOM, 데이터베이스 인덱스 등 다양한 분야에서 활용되고 있다.