자료구조 트리. Tree

트리. Tree

자료구조에서 트리는 나무를 거꾸로 표현한 것 처럼 생겼다고 해서 트리라고 이름이 지어졌다.

트리는 뿌리(root)인 노드를 Level 1로 지칭하며 시작하며 뿌리 노드를 기준으로

자식 노드를 연결시켜 가지처럼 뻗어나가는 구조이다.

트리는 여러가지 종류가 있는데 대표적으로 Binary Tree, Normal Tree가 있다.

여기서 Binary Tree는 탐색, 힙 등 광범위하게 사용된다.

배우기 전에 용어를 정리해보자.

Root, 뿌리.

뿌리(Root)는 트리의 최상위에 존재하는 노드이며 Level은 1로 고정이다.

위 Tree에서 시초가 되는 '2'노드가 Root, 뿌리 노드이다.

(위 그림에서 '2'노드가 두번 나오는데, 가장 상위에 있는게 뿌리 노드이다.)

Child, 자식

Child, 자식노드는 어떠한 노드에 종속되어 있는 노드로

뿌리 노드를 기준으로 자식노드는 '7', '5'노드이다.

Parant, 부모

Parant, 부모노드는 자기 자신 노드 아래에 자식 노드가 있다면

해당 노드는 부모 노드가 된다.

예를 들어 '9' 노드의 부모는 '5'이다.

* 같은 부모를 가진 노드의 집합을 형제 노드라고도 칭한다.

Degree, 차수

Degree, 차수는 해당 노드에 연결된 자식 노드의 개수를 뜻한다.

트리에서 가장 큰 차수가 트리의 차수가 된다.

Level(Depth), 깊이, 레벨

Level, 혹은 Depth은 트리의 깊이 혹은 레벨을 뜻 한다.

위 그림에서는 최대 4 Level 혹은 4 Depth을 가지고 있다. 

트리의 최상 지점부터 1Level, 1 Depth으로 시작한다.

Height, 높이

트리에서 최대 Level 혹은 Depth을 의미한다.

해당 트리는 4의 높이를 가진다.