Introduction

Tree는 Graph 자료구조의 한 부분입니다. 트리는 가계도, 조직도 등과 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조입니다. 그리고 트리는 한 개 이상의 노드로 이루어진 사이클이 없는 연결 그래프입니다.

트리는 이름 그대로 뿌리와 잎사귀를 가지고 있습니다. 하지만 우리가 상상하는 트리의 방향과는 반대입니다. 아래의 그림과 같이 뿌리가 위, 잎이 아래에 위치하고 있습니다.

Example

앞에서 언급한 것처럼 트리 자료구조는 디렉토리 구조에 실제로 사용됩니다. 최상위 디레곹리가 루트 노드이고, 그 아래에 하위 디렉토리가 존재하며, 이러한 하위 디렉토리는 더 깊은 수준의 디렉토리로 확장될 수 있습니다.

또한 인터넷 라우팅에 이 트리 자료구조가 사용될 수 있습니다. 라우팅은 데이터 패킷이 목적지로 전송되는 경로를 결정하는 과정입니다. 라우팅 테이블은 트리 자료구조로 구현될 수 있으며, 각 노드는 네트워크의 서브넷을 나타내고 자식 노드는 더 세분화된 서브넷을 나타냅니다. 이를 통해 데이터 패킷을 경로를 효율적으로 결정할 수 있습니다.

Terminology

루트 노드(root node)

• 부모가 없는 최상위 노드
• 트리의 시작점

자녀(child)노드