비선형 구조 - Tree

Tree

- 나무를 거꾸로 뒤집어 놓은 듯한 모습

- 그래프의 여러 구조 중 단방향 그래프의 한 구조

 

- 데이터가 바로 아래에 있는 하나 이상의 데이터에 한 개의 경로와 하나의 방향만으로 연결된 계층적 자료 구조

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

- 트리 구조는 계층적으로 표현이 되고 아래로만 뻗어나가기 때문에 사이클(clycle)이 없음

- 사이클이란? 시작 노드에서 출발해 다른 노드를 거쳐 시작 노드로 돌아올 수 있다면 사이클이 존재한다고 표현

- 따라서 트리는 사이클(clycle)이 없는 하나의 연결 그래프(Connected Graph)라고 할 수 있음

 

 

Tree의 구조와 특징

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

- 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가짐

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

 

1. 깊이(depth)

- 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있음

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

- 위 예시는 루트 A의 depth는 0이고, B와 C의 깊이는 1임. D, E, F, G의 깊이는 2임

 

2. 레벨(Level)

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

- depth가 0인 루트 A의 레벨은 1

- depth가 1인 B와 C의 레벨은 2임. D, E, F, G의 레벨은 3

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

 

3. 높이(Height)

- 리프 노드를 기준으로 루트까지의 높이(height)를 표현 할 수 있음

- 리프 노드와 직간접적으로 연결된 노드의 높이를 표현

- 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가짐

- 트리 구조의 높이를 표현할 때 각 리프 노드의 높이를 0으로 놓음

- 위 그램에서 H, I, E, F, J의 높이는 0, D와 G의 높이는 1, B와 C의 높이는 2

 

4. 서브 트리(Sub Tree)

- 트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에 트리 구조를 갖춘 작은 트리를 말함

 

용어 정리 

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

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

- 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 가까운 노드

- 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드

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

 

 

Tree의 실사용 예제

- 가장 대표적인 예제는 컴퓨터의 디렉토리 구조

- 하나의 폴더 안에 여러 개의 폴더가 있고, 또 그 여러 개의 폴더 안에 또 다른 폴더나 파일이 있음

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

- 트리의 다른 예시로는 월드컵 토너먼트 대진표, 가계도, 조직도 등