Tree

• 트리는 자식노드와 부모노드로 이루어진 계층적인 구조를 가지며, 무방향 그래프의 일종이자 사이클이 없는 자료구조를 의미한다.
• 비선형 자료구조로 계층적 관계를 표현한다.
• Tree로 이루어진 집합을 숲(forest)이라고 한다.

Tree의 특징

• 그래프의 한 종류이다. ‘최소 연결 트리’ 라고도 불린다.
• 계층 모델이다.
• 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다.
  • loop나 circuit이 없다. 당연히 self-loop도 없다.
  • 즉, 사이클이 없다.
• 노드가 N개인 Tree는 항상 **N-1개의 간선(edge)**을 가진다
• 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있으며, 하나밖에 없다.

Tree와 관련된 용어

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
• 내부(internal) 노드: 단말 노드가 아닌 노드