트리 (Tree)

🦌 크리스마스 D-10 기념으로 트리에 대해서 알아보자 🎅🏻 물론 크리스마스 트리 말고 ,,  자료구조 트리이다 ^_^ 트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다. 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1이다. 부모-자식 관계로 이루어져 있다. 트리 내에 하위 트리가 있고, 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 하다.

🦌 크리스마스 D-10 기념으로 트리에 대해서 알아보자 🎅🏻 

물론 크리스마스 트리 말고 ,,  자료구조 트리이다 ^_^ 

 

목차

1. 트리 (Tree)란 ?
2. 이진 탐색 트리 (Binary Search Tree)
3. 트리의 순회 (Tree Travelsal)

 

---

트리 (Tree)란 ?

트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다. 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1이다. 부모-자식 관계로 이루어져 있다. 트리 내에 하위 트리가 있고, 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 하다. 컴퓨터의 directory 구조가 트리 구조의 대표적인 예이다.

 

❄️ 루트 노드 (root node) : 부모가 없는 최상위 노드

❄️ 단말 노드 (leaf node) : 자식이 없는 노드

❄️ 크기 (size) : 트리에 포함된 모든 노드의 개수

❄️ 깊이 (depth) : 루트 노드부터의 거리 (= 간선의 수)

❄️ 높이 (height) : 깊이 중 최댓값

❄️ 차수 (degree) : 각 노드의 (자식 방향) 간선 개수 (= 하위 트리 개수)

 

 

---

이진 탐색 트리 (Binary Search Tree)

이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종이다.

 

🔔 이진 탐색 트리의 특징 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

 

이진 탐색 트리가 이미 구성되어 있다면 데이터를 조회하는 방법은 다음과 같다.

 

🔔 루트 노드부터 방문하여 탐색을 진행한다.

🔔 현재 노드와 찾고자 하는 값을 비교한다.

🔔 원소를 찾았다면 탐색을 종료한다.

 

 

---

트리의 순회 (Tree Traversal)

트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을 의미한다.

대표적인 트리 순회 방법은 다음과 같다.

 

🎄 전위 순회 (pre-order traverse) : 루트를 먼저 방문한다.

    • 노드 - 왼쪽 자식 - 오른쪽 자식 순

🎄 중위 순회 (in-order traverse) : 왼쪽 자식을 방문한 뒤에 루트를 방문한다.

    • 왼쪽 자식 - 노드 - 오른쪽 자식 순

🎄 후위 순회 (post- order traverse) : 오른쪽 자식을 방문한 뒤에 루트를 방문한다.

    • 왼쪽 자식, 오른쪽 자식, 노드 순

 

 

전위 순회 : A - B - D - E - C - F - G

중위 순회 : D - B - E - A - F - C - G

후위 순회 : D - E - B - F - G - C - A

 

 

 

---

Reference

[자료구조] 트리 (Tree)