[자료구조] 트리(Tree)

트리(Tree)

트리는 연결리스트를 기반으로 한 새로운 데이터 구조이다. 연결리스트에서 노드의 연결이 1차원이었다면 트리에서 노드의 연결은 2차원이다.

 

트리는 사진과 같이 최상위 노드(A)가 있고 그 아래 하위 노드(B, C) 그 아래 또 다른 하위 노드(D, E, F, G)가 있는 부모(parent)와 자식(child) 형태이다.

 

트리 관련 용어

• 노드(node) : 트리의 구성 요소 (ex : A, B, C, D, E, F, G, H, I, J)
• 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 노드 (ex : A)
• 단말 노드(terminal/leaf node) : 아래로 또 다른 노드가 연결되어 있지 않은 노드 (ex : F, G, H, I, J)
• 비단말 노드(nonterminal/internal node) : 단말 노드를 제외한 모든 노드 (ex : A, B, C, D, E)
• 간선(edge) : 노드와 노드를 연결하는 연결선
• 형제(sibling) : 같은 부모를 가지는 노드 (ex : B-C 형제, D-E 형제, F-G 형제, H-I 형제)
• 깊이(depth) : 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 (ex : H의 depth는 3)
• 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합 (ex : Level1 = B, C)
• 차수(degree) : 자식 노드의 개수 (ex : C의 degree = 2, F의 degree = 0)

 

트리의 종류

💡 이진 트리(Binary Tree)

이진 트리의 조건은 아래와 같다.

⭐ 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다. (최대 두 개의 서브 트리를 가질 수 있다)
⭐ 나뉘어진 두 서브 트리도 모두 이진 트리여야 한다. (이때 서브 트리는 공집합일 수 있다)

 

• 이진 트리(Binary Tree)

이진 트리

 

• 공집합(empty set) 노드로 채워진 이진 트리

노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면 공집합 노드가 존재하는 것으로 간주한다.

공집합 노드 덕분에 서브 트리가 하나인 노드 B와 C도, 단말 노드인 D와 E도 모두 이진 트리가 된다.

 

💡 완전(Complete) / 전(Full) / 포화(Perfect) 이진 트리

• 완전 이진 트리(Complete Binary Tree)

완전 이진 트리는 노드가 왼쪽 먼저 채워져야 한다.

1) 완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.

2) 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

3) 마지막 레벨 h에서 (1 ~ 2h-1)개의 노드를 가질 수 있다. (h = 트리의 높이)

4) 완전 이진 트리는 배열을사용해 효율적으로 표현 가능하다.

 

• 전 이진 트리(Full Binary Tree)

전 이진 트리는 자식이 없거나 2명(?)이어야 한다. (외동이면 안댐)

1) 전 이진 트리는 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.

 

• 포화 이진 트리(Perfect Binary Tree)

1) 포화 이진 트리는 모든 레벨이 노드로 꽉 차 있는 트리를 뜻한다.

2) 전 이진 트리와 같이 모든 노드가 0개 혹은 2개의 자식 노드를 가져야 한다.

3) 모든 말단 노드가 동일한 깊이 또는 레벨을 갖는다.

4) 트리의 노드 개수가 정확히 2^h-1개여야 한다. (h = 트리의 높이)

 

💡 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리는 기존 이진 트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 과정을 간단히 보자면

1. 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료한다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행한다.

이진 탐색 트리

1) 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.

2) 부모의 키가 왼쪽 자식 노드의 키보다 크다.

3) 부모의 키가 오른쪽 자식 노드의 키보다 작다.

4) 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리여야 한다.

 

트리는 언제 사용될까?

📂 파일 시스템

https://raptor-hw.net/xe/know/166820

우리가 사용하는 운영체제(Windows, Linux 등)의 디렉터리 구조는 트리로 이루어져 있다.

 

🏆 대진표

https://m.news.zum.com/articles/46170169

대진표도 마찬가지로 트리 구조이다.

 

👍이 외에도 트리는 회사 조직도, DOM, DBMS 등등 여러가지로 많이 쓰인다👍

 

실습

트리를 대표하는 이진 트리로 실습할건데 이진 트리 역시 배열 기반과 연결 리스트 기반 구현 방식이 있다!

하지만! 트리를 표현하기에는 연결 리스트가 더 유연하기 때문에 연결 리스트에 대해서만 포스팅하도록 하겠다!

- 트리(Tree) 실습(feat. 배열)

- 트리(Tree) 실습(feat. 연결 리스트)

- 트리(Tree) 실습(feat. 이진 트리 순회)

 

References

📚 윤성우의 열혈 자료구조 : C언어를 이용한 자료구조 학습서

📄 https://code-lab1.tistory.com/8

📄 https://code-lab1.tistory.com/10

📄 https://jud00.tistory.com/15#comment16725556

📄 https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

📄 https://wonit.tistory.com/196