[자료구조] Tree

Tree란?

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

Tree의 특징

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

Tree와 관련된 용어

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
• 내부(internal) 노드: 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이
• 서브 트리(sub-tree) : 트리 내의 하위 집합

 

참조

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html