[자료구조] Tree & Graph

2023.01.15

💡 Tree

자료구조 Tree는 이름 그대로 나무의 형태를 가지고 있다. 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습을 가지고 있다. 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부른다.

트리의 구조와 특징

트리 구조는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다. 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다. 위 그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node)이다. 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node)라고 부른다.

깊이 (depth)

트리구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다.

A의 깊이: 0, B C의 깊이: 1, D E F G 의 깊이: 2

레벨 (Level)

트리구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현할 수 있다.

A의 깊이: 1, B C의 깊이: 2, D E F G 의 깊이: 3

같은 레벨에 나란히 놓여진 노드를 형제노드라고 한다.

높이 (Height)

트리구조에서 리프 노드를 기준으로 루트까지의 높이를 표현할 수 있다.

서브트리 (Sub tree)

트리구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브트리라고 부른다.

트리는 계층구조로 최상위 루트노드가 존재하며 단방향 그래프이다. 
루트라는 하나의 꼭짓점 데이터를 시작으로 여러개의 데이터를 간선으로 연결한다. 
Cycle이 없는 하나의 연결Graph

용어정리

노드 (Node) : 트리구조를 이루는 모든 개별 데이터

루트 (Root) : 트리구조의 시작점이 되는 노드

리프 (Leaf) : 트리구조의 끝 지점이고, 자식노드가 없는 노드

트리의 실사용 예제

폴더 디렉토리 구조, 월드컵 토너먼트 대진표, 가계도, 조직도 등