×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,238,771명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

이진 탐색 트리에 대해 자세히 알아보자.




이진 탐색 트리의 기본 알고리즘



insert(number X, node N)

if X가 노드 N에 있는 숫자보다 작다면

if N의 왼쪽 자식이 없다면

X를 포함하는 새 노드를 만든 뒤, N의 왼쪽 자식으로 만든다.

else

insert(X, N의 왼쪽 자식)


else X가 노드 N에 있는 숫자보다 크다면

if N의 오른쪽 자식이 없다면

X를 포함하는 새 노드를 만든 뒤, N의 오른쪽 자식으로 만들기

else

insert(X, N의 오른쪽 자식)



이 이론적 알고리즘을 생각하고 이진 탐색 트리를 어떻게 하면 더 빠르게 삽입, 탐색을 가능하게 할 지 생각해보자.

 



이진 탐색 트리 예시


일단 이진 탐색 트리를 하나 두고 생각해보자.


다음과 같이 이진 탐색 트리가 구성되어있다.


이때 9를 삽입하려 한다.


삽입 과정은 다음과 같다.

1. 9가 7보다 크니 오른쪽으로 간다.

2. 노드가 존재하므로 확인한다. -> 9가 8보다 크니 오른쪽으로 간다.

3. 노드가 존재하므로 확인한다. -> 9는 14보다 작으니 왼쪽으로 간다.

4. 노드가 없으니 그 위치에 삽입한다.

이번에는 10을 삽입해보자.


삽입 과정은 다음과 같다.

1. 10이 7보다 크니 오른쪽으로 간다.

2. 노드가 존재하므로 확인한다. -> 10이 8보다 크니 오른쪽으로 간다.

3. 노드가 존재하므로 확인한다. -> 10이 14보다 작으니 왼쪽으로 간다.

4. 노드가 존재하므로 확인한다. -> 10이 9보다 크니 오른쪽으로 간다.

5. 노드가 존재하지 않으므로 9의 오른쪽에 10을 삽입한다.





방금 9와 10을 삽입할 때를 자세히 보면 다음과 같은 사실을 알 수 있다.

1) 9가 삽입될 뻔한 위치8의 오른쪽이 없었다면 삽입될 수 있었고, 14의 왼쪽이 없었기에 삽입되었다.


2) 10이 삽입될 뻔한 위치14의 왼쪽이 없었다면 삽입될 수 있었고, 9의 오른쪽이 없었기에 삽입되었다.


즉, 이러한 예시로 부터 다음과 같은 사실을 알 수 있다.







이진 탐색 트리의 기정 사실


삽입 하려는 값이 있을 경우

그 값보다 작으면서 가장 가까운 값

그 값보다 크면서 가장 가까운 값이 있는 두개의 노드 중 한 군데에 들어간다.


지금부터 작으면서 가장 가까운 값은 min으로, 크면서 가장 가까운 값은 max로 생각한다.



a와 c가 이진 탐색 트리를 이루고 있다.

b가 삽입될 때 min = a, max = c

결국 min의 오른쪽 혹은 max의 왼쪽에 달려야 하는데 min의 오른쪽은 이미 존재, 따라서 무조건 max의 왼쪽에 삽입



a와 b가 이진 탐색 트리를 이루고 있다.

c가 삽입될 때 min = b, max = X

결국 min의 오른쪽 혹은 max의 왼쪽에 달려야 하는데 min의 오른쪽이 비었으니 삽입.

이때 max는 없다. 왜냐면 c보다 크면서 가까운 값은 없기 때문이다.


c와 b가 이진 탐색 트리를 이루고 있다.

a가 삽입될 때 min = X, max = b

결국 min의 왼쪽 혹은 max의 오른쪽에 달려야 하는데 min의 왼쪽이 비었으니 삽입.

이때 min은 없다. 왜냐면 a보다 작으면서 가까운 값은 없기 때문이다.




예제 이진 탐색 트리 분석


가장 첫번째에 있었던 트리를 보면 다음과 같다.


결국 아래와 같은 방식으로 계속해서 이진 탐색 트리가 형성되고 있었던 것이다. 


이 내용을 기반으로 이진 탐색 트리 문제를 풀며 확인해보자.


문제와 함께 다루어야 이 과정을 이해하기가 쉬워진다.


문제는 다음 링크에서 다룰 예정이다.


(문제를 다루기 전, 앞의 내용을 이해하고 오면 코드 해석이 더 빨라진다.)


문제

 

[2957번] 이진 탐색 트리 :: http://www.crocus.co.kr/640

반응형
  1. ㄹㅇ 2021.07.20 22:54

    선생님은 알고리즘 마스터이십니다. 감사합니다.