자료구조 Tree

나무를 거꾸로 뒤집어 놓은 모습. 가계도와 흡사

그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮음.

 

데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료 구조입니다.

데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조.

트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클X.

 

용어정리

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

출처 : 코드스테이츠

 

 

출처 :  코드스테이츠

루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결.

각 데이터: 노드(Node).

두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계.

위 그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node).

자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node).

 

깊이 (depth)

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

루트 노드는 지면에 있는 것처럼 깊이가 0.

depth 0- 루트

depth 1- A

depth 2- B,C

depth 3- D,E,F,G

 

레벨(Level)

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

depth가 0인 루트 A의 level은 1. depth가 1인 B와 C의 level은 2입니다. D, E, F, G의 레벨은 3입니다.

level 1 - A

level 2 - B,C

leve l3 - D,E,F,G

...

같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)

 

서브 트리(Sub tree)

트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 구조 갖춘 작은 트리: 서브 트리 

(D, H, I), (B, D, E)나 (C, F, G, J)와 같은 작은 트리도 서브 트리.

 

실사용 예제

-파일 시스템

모든 폴더는 하나의 폴더(루트 폴더, /)에서 시작되어, 가지를 뻗어나가는 모양새

제일 첫 번째 폴더에서 출발하여 도착하려는 폴더로 가는 경로는 유일.