트리
계층 구조를 갖는 자료구조
부모 노드 - 자식 노드의 관계
트리의 용어
Root : 위치 상 맨 위 노드. 즉, 부모가 없는 노드.
Internal node : 내부 노드. 자식이 적어도 하나 이상 있는 노드
External node(=Leaf) : 위치상 맨 끝 노드
Ancestors : 한 노드의 모든 상위 노드. 직속 상위+ root 까지의 모든 상위노드
Descendants : 한 노드의 모든 하위노드. 직속 하위 + leaf 까지의 모든 하위노드
Depth(깊이) : 한 노드의 조상 수. root = 0부터 시작해서 아래로 갈수록 1씩 늘어남.
Height(높이) : 트리의 노드 중 Depth(0~)의 최댓값
Subtree(부분트리) : 한 노드와 그 노드의 후손을 전부 포함하는 트리 요소. 부분집합처럼 생각하면 편함.
Degree(차수): 자식 노드의 개수
Level: 같은 Depth를 가진 노드들의 집합. 가로로 묶으면 됨
'Algorithm' 카테고리의 다른 글
| 알고리즘: 빅오 표기법(Big O notation) (1) | 2024.04.25 |
|---|---|
| 여러가지 트리 (0) | 2023.04.16 |
| 링크드 리스트(Linked List) (0) | 2022.12.23 |
| 배열 (0) | 2022.12.22 |
