[자료구조] 트리

트리는 계층적 구조를 표현하는데 적합한 자료구조이다. 또한 트리로 표현한 후에 데이터들을 탐색했을 때 효율적인 문제들이 존재한다. 따라서 이번에는 트리의 기본적인 구조를 알아보도록 한다.

---

트리의 기본

[그림 1]은 트리를 나타낸 것이다. 트리는 노드들이 간선으로 연결되어 있으며 마치 나무를 뒤집어 놓은 듯한 느낌을 받을 수 있다. 트리는 그래프의 한 종류라고 할 수 있다. 하지만 그래프와 달리 순환되는 구조를 갖고있지 않다. 왜냐하면 트리는 N개의 노드와 N-1개의 간선으로 이루어져 있기 때문에 하나의 노드를 시작으로 탐색을 진행했을 때 다시 처음 위치로 돌아오지 못한다.

그림 1 트리

트리를 구성하는 용어들

트리의 구조를 파악하는 사용되는 용어들이 존재한다.

• 루트 노드 : 노드 A처럼 트리에서 최상위에 존재하는 노드이며 0개 이상의 자식 노드를 갖고있으며 부모 노드가 존재하지 않는다.
• 단말 노드 : 노드 D, E, F처럼 트리에서 최하위에 존재하는 노드이며 부모 노드는 존재하지만 자식 노드가 존재하지 않는다.
• 내부 노드 : 노드 A, B, C처럼 단말 노드를 제외한 노드이다.
• 노드의 깊이 : 루트에서 어떠한 노드까지 이동할 때 거쳐야 하는 간선의 수를 말한다.
• 노드의 크기 : 자신을 포함한 모든 자손 노드의 개수를 말한다.
• 노드의 레벨 : 루트 노드가 0레벨 부터 시작되며 트리의 특정 깊이를 가지는 노드의 집합을 말한다.
• 노드의 차수 : 특정 노드의 부트리의 개수를 말한다. 노드 A의 차수는 2이며 노드 C의 차수는 1이다.
• 트리의 높이 : 루트 노드에서 가장 깊숙이 있는 노드의 깊이를 말한다. 위의 트리에서는 높이가 2가 된다.