Algorithm&Data structure/Data structure(JS)
트리 (Tree, Data Tree)
bright jazz music
2024. 12. 11. 20:37
트리(Tree)
트리는 노드들의 계층적 구조로, 한 노드가 여러 자식 노드를 가질 수 있는 비선형 데이터 구조이다. 최상위에 있는 노드를 루트라 하고, 자식이 없는 노드를 리프 노드라 한다.
주요 용어:
- 노드(Node) - 트리의 기본 요소로 데이터와 자식 노드들의 참조를 포함
- 루트(Root) - 트리의 최상위 노드
- 부모-자식(Parent-Child) - 두 노드의 직접적인 연결 관계
- 리프(Leaf) - 자식이 없는 말단 노드
- 높이(Height) - 루트에서 가장 먼 리프까지의 거리
- 깊이(Depth) - 특정 노드까지 루트로부터의 거리
장점:
- 계층적 데이터 표현에 적합
- 빠른 검색과 삽입 가능 (구현에 따라 O(log n))
- 동적인 크기 조절 가능
- 자연스러운 재귀적 구조
단점:
- 구현이 복잡할 수 있음
- 균형 유지가 어려울 수 있음
- 메모리 사용량이 큼 (포인터 저장)
예시
HTML DOM(문서객체모델)
네트워크 라우팅
추상구문트리