트리 Tree
트리의 개념과 특징
- DAG(Directed Acyclic Graphs) 방향성 있는 비순환 그래프
- loop x, circuit x
- 노드(node 혹은 vertex)와 링크(link 혹은 edge)의 집합
- 트리에서 한 노드에서 다른 노드로 가는 경로(path)는 유일하다.
- N개의 노드를 가지는 나무는 N-1개의 링크를 가진다.
- 종류 : 이진트리(binary tree), B 트리, 힙(heap), 세그먼트(segment) 등등
트리의 기본 구조
- 루트 Root : 트리의 제일 위에 있는 노드
- 경로 Path : 트리 내에서 연결된 노드를 통해 이동할 때의 이동 경로(path는 오직 하나)
- 자식 노드 children, 부모 노드 parent : 직접 연결되어 있으면서 아래에 있다면 자식, 위에 있다면 부모 노드
- 형제 노드 sibling : 같은 부모 노드를 갖는 경우
- 잎 노드 leaf or terminal : 자식이 없는 노드
- 내부 노드 internal : 자식이 하나라도 있는 노드
- 레벨 level : 뿌리(0 level)부터 시작하여 경로가 증가할 때마다 늘어남
- 높이 height : 나무의 노드들 중에 가장 높은 레벨