이진 탐색 트리 특징을 이용한 빠른 삽입, 탐색

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

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

---

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