트리(Tree)

트리 말그대로 나뭇가지를 생각하면 쉬운데요.

 

이게 트리라고 하는 건데 왜 나뭇가지라고 생각하기 편하면요.

 

제가 그려봤어요

나뭇가지 같죠?

그래서 tree라고 부르는 것 같아요.

 

뭐 암튼

 

트리(Tree)

트리란 자식노드와 부모노드로 이루어진 계층적인 구조를 가지면서 무방향 그래프의 일종이며 사이클이 없는 자료구조형입니다.

 

부모노드와 자식노드는 뭐냐면

N을 기준으로 보자면

H가 부모노드가 되며 O는 자식노드가 됩니다.

 

근데 저번 포스팅에 양방향 그래프와 단방향 그래프를 배웠는데

이거는 무방향 그래프죠?

방향 그래프는 direct graph라고 불리며 무방향 그래프는 undirected graph라고 불립니다.

위가 방향 그래프, 아래가 무방향 그래프

무방향은 말 그대로 방향이 없습니다.

 

트리를 설명할 때는 보통 무방향 그래프로 설명을 합니다.

 

tree의 특징은 아래와 같습니다.

 

1. 부모, 자식의 계층 구조를 가지며, 같은 경로 상에서 어떤 노드보다 위에있으면 부모, 그 아래에 있으면 자식노드가 됩니다.
2. V(정점) - 1 = E(간선)라는 특징을 가집니다. 간선 수는 (노드 수 - 1)입니다.
3. 두 노드 사이의 경로는 유일무이하게 존재합니다.
   한마디로 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있으며 단 하나밖에 존재하지 않습니다.\
4. Tree는 루트노드, 내부노드, 리프노드로 이루어집니다.

 

루트 노드

루트 노드는 가장 최상위에 있는 노드를 말합니다.

내부 노드

내부 노드는 루트노드와 리프노드 사이에 있는 노드를 말합니다.

리프 노드

리프 노드는 자식노드가 없는 노드를 말합니다.

 

 

트리는 높이와 깊이 서브트리로 구성을 그림으로 표현하면 아래와 같습니다.

 

깊이

트리에서 깊이는 각각의 노드마다 다릅니다.
루트노드에서 특정 노드까지 최단거리로 갔을 때의 거리를 뜻합니다.
예를 들어 M까지의 깊이는 2입니다.

높이

높이는 루트 노드부터 리프 노드까지의 거리중 가장 먼 거리를 의미합니다.
위 그림에서 보자면 높이는 3입니다.

서브트리

서브트리는 트리내의 하위 집합을 서브트리라고 하며, 트리 내의 트리 구조가 있는 것을 의미합니다.

 

레벨

레벨은 깊이랑 같은 의미이긴하지만
한 깊이의 표시라고 보면 되겠습니다.

네네

여담으로 위와 같이 트리를 모아놓은 집합을 forest라고합니다.

 

끄으읕