트리란?
하나의 노드를 가리키는 간선이 하나밖에 없는 구조로 일종의 방향그래프이다.
용어
- 노드 : 각 정점
- 간선 : 노드와 노드를 잇는 선
- 리프노드(leaf node) : 자식이 없는 노드
- 레벨(level) : 루트로부터 몇번째 깊이인지 표현하는 용어, 루트가 level 1
특징
- 루트노드를 제외한 모든 노드는 반드시 하나의 부모 노드를 가진다.
- 노드가 n개인 트리는 반드시 n-1개의 간선을 가진다.
- 루트노드에서 특정 정점으로 가는 경로는 유일하다.
트리의 종류
- 이진트리 : 각 노드가 최대 2개의 자식을 가지는 트리
- 완전 이진트리 : 마지막 레벨을 제외한 모든 노드가 채워진 트리
- 포화 이진트리 : 마지막 레벨까지도 모든 정점이 채워짐
- 편향 트리 : 한쪽방향으로 노드가 채워지는 트리
성장하는 개발자가 되겠습니다~