[자료구조] 트리(Tree)

 트리(tree)란 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있어서 트리 구조라고 부른다.

 

트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다. 따라서 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다.

 

 트리 구조는 계층적으로 표현이 되고 아래로만 뻗어나가기 때문에 사이클이 없다. 즉, 한 노드에서 시작해서 다른 정점들을 순회하고 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다.

 

 컴퓨터의 디렉토리 구조나 월드컵 대진표 등을 트리 구조의 예시로 들 수 있다.

 

 

 

 

구조와 특징

<출처> 나무위키

 

 트리 구조는 위 그림처럼 루트(root)라는 꼭짓점 데이터부터 시작하고 간선(edge)을 통해 여러 데이터와 연결한다. 각 데이터는 노드(node)라고 부르며 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 갖는다. 즉, A는 B와 C의 부모 노드이며, B와 C는 A의 자식 노드이다. 맨 아래에 자식이 없는 노드는 나무의 잎과 같다고 해서 리프 노드(leaf node)라고 부른다.

 

 트리 구조는 깊이와 높이, 레벨 등을 측정할 수 있다. 루트로부터 하위 계층의 특정 노드까지를 깊이(depth), 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level), 리프 노드를 기준으로 루트까지를 높이(heigth)이라고 표현한다.

 

 위 그림에서 D, H, I 노드를 크게 보면 하나의 트리 구조 형식을 갖추고 있는데, 이렇게 루트로부터 뻗어나오는 큰 트리의 내부 안에 다시 트리 구조를 갖춘 작은 트리를 서브 트리(sub tree)라고 한다. 즉, B와 D, E 노드나 C와 F, G 노드도 서브 트리이다.

 

 

 

트리(그래프) - 나무위키