트리 구조 예시
- 파일 시스템
- DOM(Document Object Model)
- 검색 엔진이나 데이터베이스도 트리에 기반해서 구현(탐색 트리)
트리 구성 요소
뿌리(Root), 가지(Branch), 잎(Leaf) 세 가지 요소 구성
뿌리, 가지, 잎 모두 노드이다.
루트는 가장 위의 노드, 가지는 루트와 잎 사이 모든 노드, 잎 노드는 단말 노드라고 부른다.
관계
- 1은 2, 3의 부모
- 2, 3은 형제
- 2, 3은 1의 자식
경로(Path)
경로: 한 노드에서 다른 노드까지 이르는 길 사이에 있는 노드들의 순서
2에서 8까지의 경로?
2 -> 5 -> 8
길이(Length)
경로는 길이라는 속성을 가진다.
길이: 출발 노드에서 목적지 노드까지 거쳐야 하는 노드의 개수
2, 5, 8 경로의 길이는 2이다.
깊이(Depth)
노드의 깊이: 루트 노드에서 해당 노드까지 경로의 길이
트리의 깊이: 노드의 깊이 중 가장 큰 값
- 루트의 깊이 = 0
- 노드 8의 깊이 = 3
레벨(Level)
레벨: 깊이가 같은 노드의 집합을 일컫는 말
- 레벨 2: 깊이가 2인 노드 집합(4, 5, 6)
차수(Degree)
노드의 차수: 해당 노드의 자식 노드 개수
트리의 차수: 트리 내에 있는 노드 중 가장 큰 차수가 트리의 차수
nakkim.hashnode.dev로 이사합니다