[이코테] 트리(Tree) 자료구조란? 이진 탐색(Binary Search)란? 이진 탐색 트리(Binary Search Tree)란? 트리 순회란?🤔

 

 

hackerrankn challenges Day22 강의 수강 도중

이진 트리(Binary Tree)에 대한 코딩이 이루어지는데

이해가 어려워 유튜브를 통해 트리 자료구조에 대한 강의를 찾아보았다.

 

필자는 이전에 학교 '자료구조' 수업에서 트리에 대해

학습한 적이 있으나 기억이 가물가물해 추가 공부하고

학습 내용을 포스팅한다.

 

필자가 수강한 강의 내용은 링크 설정해 두었으니

글자를 클릭하길 바란다.

(강의 : 유튜브 '나동빈'님 이코테 '트리'편)

 

 

 

---

 

그럼 강의 내용을 차근차근 정리해보자.

 

🤔 우선 트리(Tree)란 무엇일까?

 

출처 : 유튜브 나동빈님 강의 캡쳐

 

트리란 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 잇는 자료구조이다.

 

✅ 용어

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

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

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

✔ 깊이(depth) : 루트 노드부터의 거리

✔ 높이(height) : 깊이 중 최댓값

✔ 차수(degree) : 각 노드의 (자식 방향) 간선 개수

 

기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개 이다. (트리의 특징 ❗❗)

 

 

 

용어 개념과 필자가 첨부한 사진을 함께 보면

어렵지 않게 이해가 될 것이다.

 

 

 

 

 

🤔 그럼 이진 탐색 트리(Binary Search Tree)란 무엇일까?

출처 : 유튜브 나동빈님 강의 캡쳐

 

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

 

🤔이진 탐색이란❓❓ 

이진 탐색 알고리즘이란 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다.

리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 

없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다.

 

출처 : 이진 탐색  - 나무위키

 

 

즉, 이진 탐색 트리는 이진 탐색을 위한 트리라고 생각하면 된다.

 

 

---

 

🤔 다음으로 이진 탐색 트리가 데이터를 조회하는 과정에 대해 살펴보자.

설명을 위한 트리 이미지는 유튜브 나동빈님 강의에서 가져왔다.(출처표기)

 

✔ 이진트리

출처 : 유튜브 나동빈님 강의 캡쳐

 

찬고자 하는 원소 : 37

 

✅ 순서

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

1) 현재 노드와 찾는 원소 37을 비교한다. 

2) 찾는 원소가 더 크므로 오른쪽 방문

 

 

출처 : 유튜브 나동빈님 강의 캡쳐

 

2. 현재 노드와 값을 비교한다.

1) 현재 노드와 찾는 원소 37을 비교

2) 찾는 원소가 더 작으므로 왼쪽 방문

 

 

출처 : 유튜브 나동빈님 강의 캡쳐

 

3. 현재 노드와 값을 비교한다.

1) 현재 노드와 찾는 원소 37을 비교

2) 원소를 찾았으므로 탐색 종료

 

 

---

 

 

🤔 다음으로 트리 순회에 대해 알아보자.

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

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

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

 

출처 : 유튜브 나동빈님 강의 캡쳐

 

 

---

 

오늘은 자료구조에서 트리와

이진 탐색 트리, 이진 탐색,

이진 탐색 트리의 데이터 조회 방법, 

트리 순회 등에 대해 알아보았다.

 

포스팅을 보다가 궁금한 점이 있으면

언제든 댓글 달아주길 바란다.