[Data Structure] 이진 탐색 트리(Binary Search Tree)란?

 

안녕하세요 Foma 💻 입니다!

 

오늘은 트리 자료구조 중 효율적인 검색,삽입,삭제를 할 수 있는 이진 탐색 트리에 대해서 알아보겠습니다.

 

바로 시작할게요~

---

이진 트리(Binary Tree)란? 🤔

 

이진 탐색 트리는 이진 트리 자료구조로 되어있기 때문에 먼저 이진 트리가 뭔지에 대해 알아보겠습니다.

 

이진 트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.... - 위키 백과 -

 

즉, 노드마다 자식이 2개 이하인 트리를 말합니다.

 

아래 그림처럼 이루어진 트리를 말합니다. (자식이 없어도 되고, 하나여도 되고, 두 개여도 됩니다.)

 

출처:위키백과

---

이진 탐색 트리(Binary Search Tree)란? 🧐

 

이진 탐색 트리는 다음과 같은 속성이 있는 이진 트리 자료 구조이다.
✅  각 노드에 값이 있다.
✅  값들은 전순서가 있다.
✅  노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
✅  노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
✅  좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.   
- 위키 백과 -

 

즉, 간단하게 말해 이진 트리로 되어있는데 자식의 왼쪽 값이 부모보다 작고 오른쪽 값이 부모보다 크면 됩니다.

 

아래와 같은 그림으로 되어 있는게 바로 이진 탐색 트리에요!

 

출처: https://www.acmicpc.net/problem/18240

---

Time Complexity (시간복잡도)

 

실행 시간은 평균적으로 트리의 높이만큼 𝚯(log₂N)이 걸리지만

 

아래와 같이 데이터가 한 쪽으로 몰릴 경우(최악의 경우) O(N)의 시간복잡도를 갖게 됩니다.

 

---

Search(탐색)

 

[3,7,4,5,1,8,2,6]로 되어있는 이진 탐색 트리에서 탐색하는 과정은 아래와 같습니다.

 

1. 찾으려는 값이 있다면 위치를 반환한다.

 

2. 없다면 nil을 반환한다.

 

아래 그림에서 5를 찾으려면 어떻게 할까요?

 

 

루트 노드인 3보다 크니깐 오른쪽에 있겠죠? 7로 내려갑니다.

 

 

7보다 작으므로 왼쪽에 있겠죠? 4로 내려갑니다.

 

 

4보다 크므로 오른쪽으로 이동합니다.

 

5를 찾았으므로 위치를 반환합니다.

 

 

---

Insertion(삽입)

 

이진 탐색 트리를 삽입하는 과정은 어떻게 될까요?

 

1. 아무것도 없으면 그냥 삽입

 

2. 노드가 있다면 현재 숫자보다 크면 오른쪽,작으면 왼쪽으로 자식으로 내려갑니다.

 

3. 자식이 없으면 삽입합니다.

 

[3,7,4,5,1,8,2,6]을 삽입하는 과정을 보여드리겠습니다.

 

트리에 아무것도 없으니 3을 삽입해줍니다.

 

그 다음 숫자인 7입니다.

 

3보다 크기 때문에 오른쪽에 삽입합니다.

 

그 다음 숫자는 4입니다.

 

3보다 크니깐 오른쪽,7보다 작으니깐 왼쪽으로 삽입합니다.

 

 

그 다음 숫자는 5입니다.

 

3보다 크니깐 오른쪽,7보다 작으니깐 왼쪽,4보다 크니깐 오른쪽에 삽입합니다.

 

 

그 다음 숫자는 1입니다.

 

3보다 작으므로 왼쪽에 삽입합니다.

 

 

그 다음 숫자는 8입니다.

 

3보다 크니깐 오른쪽,7보다 크니깐 오른쪽에 배치합니다.

 

 

 

그 다음 숫자는 2입니다.

 

3보다 작으므로 왼쪽,1보다 크니깐 오른쪽에 배치합니다.

 

 

 

 

그 다음 숫자는 6입니다.

 

3보다 크니깐 오른쪽,7보다 작으니깐 왼쪽,4보다 크니깐 오른쪽,5보다 크니깐 오른쪽에 배치합니다.

 

---

Deletion(삭제)

 

삭제하는 과정은 탐색이나 삽입보다 살짝 더 복잡합니다.

 

총 3가지의 케이스가 있는데요.

 

1. 자식이 없는 경우

 

2. 자식이 한 개인 경우

 

3. 자식이 두 개인 경우

 

1. 자식이 없는 경우

 

먼저 자식이 없는 경우인 2를 삭제하려면 어떻게 해야할까요?

 

 

 

그냥 삭제해주면 됩니다.

 

 

2. 자식이 한 개인 경우

 

자식이 한 개인 경우인 4를 삭제하려면 어떻게 해야할까요?

 

삭제하고 해당 위치에 자식을 위치합니다.

 

 

3. 자식이 두 개인 경우

 

자식이 두 개인 경우인 7을 삭제하려면 어떻게 해야할까요?

 

방법은 2가지인데요.

 

1. 오른쪽 자식 중 가장 작은 값을 대체한다.

 

2. 왼쪽 자식 중 가장 큰 값을 대체한다.

 

저는 첫 번째 방법으로 오른쪽 자식 중 가장 작은 값인 8을 대체해 주었습니다.