트리(Tree)
트리의 정의
- 사이클 없이 모든 정점이 연결되어 있는 그래프이다. (따라서 정점이 V개면 간선의 개수는 V-1개)
- 노드(정점)와 노드를 연결하는 링크(간선)들로 구성되어 있다.
- 보통 루트 노드가 존재하는 트리를 트리라 부르고 사용한다.
- Root(루트)라고 불리는 노드가 하나 존재한다.
- 루트 노드는 0개 이상의 자식 노드를 가진다.
- 나머지 노드들은 n(>=0)개의 서브 트리(부분집합)로 이루어져있다.
- 트리 안에 서브 트리가 있고, 서브 트리 안에 또 서브 트리가 있는 재귀적 자료구조이다.
위 이미지에서 루트 노드는 2이며, 7과 5를 자식 노드로 가진다.
각 7과 5노드를 시작으로 서브트리가 구성되어 있으며, 각 서브트리에서 7과 5는 루트 노드의 역할을 한다.
트리는 자료의 계층적 구조를 표현할 때 사용된다.
예를 들어 가계도, 회사의 조직도, 컴퓨터의 폴더 구조 등을 나타낼 때 사용할 수 있다.
트리 관련 용어
헷갈리는 용어들을 확실히 정리하자.
노드
단말 노드(leaf/terminal node)
: 자식이 없는 노드, 가장 끝 노드
(ex. H, I, J, F, G)
내부 노드(internal node)
: 단말 노드가 아닌 노드
노드의 크기, size
: 자신을 포함한 모든 자손 노드의 개수
(ex. 노드 C의 크기는 3)
노드의 차수, degree
: 노드가 가진 가지(자식노드)의 수
(ex. 노드 D의 차수는 2)
노드의 깊이, depth
: 루트에서부터 해당 노드에 도달하기 위해 거쳐야 하는 간선의 수, 해당 노드가 루트 노드로부터 얼마나 떨어져 있는지를 나타낸다.
(ex. 노드 A(루트 노드)의 깊이는 0, 노드 F의 깊이는 2)
노드의 높이, height
: 가장 깊은 노드와의 깊이 차이, 해당 노드가 트리의 가장 끝 노드로부터 얼마나 떨어져 있는지를 나타낸다.
(ex. 노드 J(가장 깊은 노드)의 높이는 0, 노드 C의 높이는 2, 노드 A의 높이는 3)
노드의 레벨, level
: 트리의 특정 깊이를 가지는 노드들의 집합으로, 루트 노드의 레벨을 1으로 시작한다.
(ex. 노드 B,C의 레벨은 2)
트리
트리의 차수, degree
: 트리를 구성하는 노드의 차수 중 최대 차수
트리의 높이, height
: 트리에서 가장 깊은 노드의 깊이 (=루트 노드의 높이)
(위 사진 속 트리의 높이는 3)
(트리의 깊이는 노드의 깊이와 같은 것을 의미하는 듯하다. 트리의 깊이 = 각 노드의 깊이를 의미한다.)