🔧변경내용🔨

제목	날짜	내용
발행일	23.03.15

📌들어가기에 앞서

해당 포스터는 자료구조 학습 내용 중 Tree 기초이론에 대한 내용을 정리한 것입니다.

📖 Tree의 정의

• 자료구조 Tree는 이름 그대로 나무의 형태를 가지고 있다.

• 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습

• 그래프의 여러 구조 중 단방향 그래프의 한 구조로,

• 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아다고 해서 트리 구조라고 부른다.

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

• 데이터를 순차적으로 나열시킨 선형 구조가 아니다

• 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조

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

• 여기서 사이클이란

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

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

---

📖 Tree의 구조와 특징

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

• 각 데이터를 노드(Node)라고 한다.

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

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

  • B와 C는 A의 자식 노드(Child Node).

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

• 자료구조 Tree는 깊이와 높이, 레벨 등을 측정할 수 있다.

깊이 (depth)

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

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

  • 위 그림에서 루트 A의 깊이는 0이고,

  • B와 C의 깊이는 1이다.

  • D, E, F, G의 깊이는 2이다.

레벨(Level)

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

  • 깊이가 0인 루트 A의 level은 1

  • 깊이가 1인 B와 C의 level은 2

  • D, E, F, G의 레벨은 3

• 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node) 라고 한다.

높이(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입니다.

서브 트리(Sub tree)

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

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

자료구조는 자료의 집합을 구조화하고, 이를 표현하는 데에 초점이 맞춰져 있다.

용어정리

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

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

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

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

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

---

📖 Tree의 실사용 예제

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

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

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

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

• 위 그림처럼, 제일 첫 번째 폴더에서 출발하여 도착하려는 폴더로 가는 경로는 유일하다.

• 사용자들이 편하게 사용하기 위한 파일 시스템 등에서는 트리 구조를 이용해 만들어져 있습니다.

트리의 다른 예시

• 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등

---

📚 레퍼런스

코드스테이츠 수업자료