1. Tree의 정의

---

• 자료구조 Tree는 그래프의 여러 구조 중 단뱡향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부른다.

• 트리는 그래프의 한 종류이다.(그래프의 범위 안에 트리가 있음)

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

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

• 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클(cycle)이 없다. 여기서 사이클이란 시작 노드에서 출발해 다른 노드를 거쳐 시작 노드로 돌아올 수 있다면 사이클이 존재한다고 표현한다. 따라서 트리는 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)라고 할 수 있다.

2. Tree의 구조

---

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

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

• 아래 그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node)이며, 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node)라고 부른다.

3. Tree의 특징

---

1) 깊이(depth)

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

• 루트 노드는 지면에 있는 것처럼 깊이가 0이며, 아래 그림에서 루트 A의 depth는 0이고, B와 C의 깊이는 1이다. D, E, F, G의 깊이는 2다.

2) 레벨(Level)

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

• depth가 0인 루트 A의 level은 1이며, depth가 1인 B와 C의 level은 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다. 이때 B는 D의 height + 1 을, C는 G의 height + 1 을 높이로 가진다. 따라서, 루트 A의 높이는 3이다.

4) 서브 트리(Sub tree)

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

• (D, H, I)로 이루어진 작은 트리도 서브 트리이고, (B, D, E)나 (C, F, G, J)도 서브 트리입니다.

4. Tree의 실사용 예제

---

• 대표적인 트리의 예제는 컴퓨터의 티렉토리 구조가 있다.

• 어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더나 다운로드 폴더 등에서 다른 폴더에 진입하고, 또 그 안에서 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾는다.

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