트리 (Tree, Data Tree)

 

트리(Tree)

 

트리는 노드들의 계층적 구조로, 한 노드가 여러 자식 노드를 가질 수 있는 비선형 데이터 구조이다. 최상위에 있는 노드를 루트라 하고, 자식이 없는 노드를 리프 노드라 한다.

 

주요 용어:

1. 노드(Node) - 트리의 기본 요소로 데이터와 자식 노드들의 참조를 포함
2. 루트(Root) - 트리의 최상위 노드
3. 부모-자식(Parent-Child) - 두 노드의 직접적인 연결 관계
4. 리프(Leaf) - 자식이 없는 말단 노드
5. 높이(Height) - 루트에서 가장 먼 리프까지의 거리
6. 깊이(Depth) - 특정 노드까지 루트로부터의 거리

장점:

1. 계층적 데이터 표현에 적합
2. 빠른 검색과 삽입 가능 (구현에 따라 O(log n))
3. 동적인 크기 조절 가능
4. 자연스러운 재귀적 구조

단점:

1. 구현이 복잡할 수 있음
2. 균형 유지가 어려울 수 있음
3. 메모리 사용량이 큼 (포인터 저장)

예시

HTML DOM(문서객체모델)

네트워크 라우팅

추상구문트리