✔ 트리
트리란?
- 노드와 엣지로 연결된 그래프의 특수한 형태
- 그래프의 형태이므로 그래프의 표현으로도 트리를 표현할 수 있음
- 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재함
- 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가짐
- 트리에서 임의의 두 개의 노드를 연결하는 경로는 유일
- 트리의 부분 트리 역시 트리의 모든 특징을 따름
트리의 구성 요소
- 노드 : 데이터의 index와 value를 표현하는 요소
- 엣지 : 노드와 노드의 연결 관계를 나타내는 선
- 루트 노드 : 트리에서 가장 상위에 존재하는 노드
- 부모 노드 : 두 노드 사이의 관계에서 상위 노드에 해당하는 노드
- 자식 노드 : 두 노드 사이의 관계에서 하위 노드에 해당하는 노드
- 리프 노드 : 트리에서 가장 하위에 존재하는 노드 (자식 노드가 없는 노드)
- 서브 트리 : 전체 트리에 속한 작은 트리
코딩 테스트에서의 트리
- 그래프로 푸는 트리 문제
- 노드와 엣지를 인접 리스트로 표현하고 DFS, BFS
- 트리만을 위한 문제
- 1차원 배열로 표현하고 이진트리, 세그먼트 트리 (Index Tree), 최소공통조사 (LCA)
더보기
Do it! 알고리즘 코딩테스트 with JAVA
'Coding Test > Java 알고리즘 개념' 카테고리의 다른 글
[트리] 이진 트리 (0) | 2023.08.06 |
---|---|
[트리] 트라이 (0) | 2023.08.06 |
[그래프] 최소 신장 트리 (0) | 2023.08.04 |
[그래프] 플로이드-워셜 (0) | 2023.08.04 |
[그래프] 벨만-포드 (0) | 2023.08.04 |