[자료구조] 트리(Tree)

트리(Tree)란?

트리는 관계를 계층적으로 표현하는 비선형(데이터가 여러 방향으로 연결된 계층 구조) 자료구조이다.

트리는 몇가지 특징을 가진다.

1. 사이클이 없음
2. 루트 노드가 존재
3. 계층 구조를 가짐(즉, 부모 - 자식 관계가 존재)
4. N개의 노드와 N-1개의 간선으로 이루어져 있음

즉, 위 특징을 모두 만족하는 그래프는 트리라고 할 수 있다.

트리(Tree)와 그래프(Graph) 차이

	트리(Tree)	그래프(Graph)
구조	계층 구조를 가지는 그래프의 특수한 형태	정점(Vertex)과 간선(Edge)으로 이루어진 일반적인 자료구조
루트	부모 → 자식 관계	관계만 존재
루트	항상 존재	없음
사이클	없음	있을 수도 있음
간선 수	N개의 노드 → N-1개의 간선	제한 없음
연결성	항상 하나로 연결	여러 컴포넌트 가능

트리의 장단점

장점

• 데이터의 계층적 표현
• 빠른 탐색 -> 이진 탐색 트리(BST)의 경우 평균 탐색 시간: O(log n)
• 효율적인 삽입/삭제

단점

• 복잡한 구조
• 포인터 관리 등으로 인한 메모리 사용량 증가
• 균형이 깨질 경우 성능 저하

정리

트리는 데이터를 계층적으로 관리 및 빠른 탐색과 삽입/삭제를 위해 만들어진 자료구조이다.

실제로 파일 시스템, HTML DOM 구조 등 계층 구조가 필요한 곳에 많이 사용되고,

Heap, Trie, B-Tree 등 많은 알고리즘의 기반이 된다.