[자료구조] 트리(Tree)

 

 

흔히 트리(Tree) 자료 구조를 계층적인 구조를 나타내기 위한 자료구조라고 한다.

트리(Tree)

트리는 해당 이미지와 같은 형태를 지니며, 노드(Node)들의 집합이라고도 볼 수 있다. 

이때, 구현 관점에서 보면 각 노드는 값과 다른 노드를 가리키는 래퍼런스로 구성이 되는데, 이때 이 래퍼런스는 간선(Edge)라고 볼 수 있다. 

 

트리에서의 높이(height)

트리에서 높이란 특정 노드에서 리프(Leaf)노드까지의 가장 긴 경로의 간선의 수를 의미한다. 

물론 높이 계산을 간선의 갯수로 하지 않고 노드의 갯수로 하는 경우도 있다고 한다. 아마도 구현하는 사람에 따라 달라질 수 있지 않나 싶다.

만약 노드의 갯수로 높이를 계산한다면 간선의 수로 카운트할때보다 +1을 해주면 된다.

예를 들어 위에 첨부한 이미지상에서 B의 높이는 2가 될것이고, 리프노드인 H나 I는 높이가 0이 될 것이다.

 

노드의 깊이(depth)

트리에서 깊이란 루트 노드에서 특정 노드까지의 경로의 간선의 수를 의미한다. 

그리고 전체 트리의 깊이란 트리에 있는 노드들의 깊이 중 가장 긴 깊이를 의미한다. 

예를 들어, 위에 첨부한 이미지를 기준으로 보면 D노드의 깊이는 2가 될것이고, 해당 전체 트리의 깊이는 3이 될 것이다. 

그리고 자세히 보면 트리의 높이는 곧 트리의 깊이가 같다는 것또한 확인할 수 있다.

 

트리의 특징

1. 루트노드는 하나만 존재한다.

 

2. 사이클이 존재하지 않는다.

 

3. 자녀 노드는 하나의 부모 노드만 존재한다. 

 

4. 데이터를 순차적으로 저장하지 않는 비선형, 계층적 자료구조이다. 

트리는 각 트리안에 자녀 노드들이 또 다른 서브트리를 생성하는 재귀적인 구조를 띈다.