[자료구조] 9-1. 이진 탐색 트리의 개념

자료구조는 자료를 효율적으로 관리하는 기법이다. 특히 자료를 관리한다는 것은 추가, 검색, 제거 등을 의미한다.

검색 연산은 다시 세 가지로 나눌 수 있다.

1. 임의의 원소 찾기

2. 가장 먼저/늦게 온 원소 찾기

3. 가장 큰/작은 원소 찾기가 있다.

그 중에서 우리는 임의의 원소를 찾는 연산에 집중할 것이다.

자료가 저장된 자료 구조에서 임의의 원소를 찾기 위해서는 먼저 자료구조를 정의해야 한다. 우리가 배운 것에는 크게 두 가지가 있다.

1. 정렬되지 않은 배열

추가: 맨 뒤에 그냥 쓰면 되니까 O(1)

검색: 처음부터 내가 원하는 원소를 찾아야 하므로 O(n)

제거: 제거하면 뒤에 있는 원소가 한 씩 이동해야 하므로 O(n)

2. 정렬된 배열

추가: 적절한 위치에만 들어갈 수 있기 때문에 O(n)

검색: 이진 탐색을 쓸 수 있으므로 O(log n)

제거: 제거하면 뒤에서 앞으로 땡겨와야 하기 때문에 O(n)

추가와 제거에 대한 시간을 줄일 방법을 고민해보자.

이진 탐색을 복습해보자. 배열의 중앙값을 찾아 배열을 반으로 나누고 재귀적으로 반복하면서 key 값을 검색한다.

예시의 경우, 인덱스 0부터 7까지 있으므로 mid=3이 된다.

mid값 3을 가지고 배열을 분할하고, 인덱스 4부터 7까지가 우리의 검색 대상이 된다.

다시 mid를 계산하면 (4+7)/2=5가 된다.

새로운 mid값으로 배열을 나누고, 우리가 찾는 6은 더 작으니까 왼쪽을 본다. 

그런데 이 배열은 왼쪽만 보면 원소가 하나인 배열이므로 mid는 4가 된다. 이 값과 우리가 원하는 6이라는 값을 비교해 배열에 포함되어있는지 결정한다.

최종적으로 6이 포함되어 있음을 확인하였다.

이진 탐색은 중앙값을 찾아 배열을 반으로 분할하는 과정을 반복한다. 결국 어떤 배열에 대해 중앙값을 찾으면 왼쪽과 오른쪽으로 나뉘게 된다.

그런데 만약 내가 찾는 key값이 mid보다 작으면 왼쪽이 새로운 배열이 되고 다시 분할을 시작한다.

mid가 key값보다 크다면 오른쪽 부분 배열이 새로운 배열이 되어 다시 분할한다.

배열을 2개의 부분 배열로 재귀적으로 분할하는 특징은 이진 트리와도 비슷하다.

- 분할 구조

배열: 왼쪽 부분 배열 / 중앙 / 오른쪽 부분 배열

이진 트리: 왼쪽 부분 트리 / 부모 노드 / 오른쪽 부분 트리

- 재귀 구조

배열: 각 부분 배열이 또 분할됨

이진 트리: 각 부분 트리가 또 분할됨

이러한 유사점 때문에 이진 탐색의 과정을 트리 형태로 표현할 수 있다.

예를 들어, 위의 배열을 mid값 5를 기준으로 왼쪽, 오른쪽 나눈다면 5를 루트 노드로 해서 분할하는 것이라고 할 수 있다.

다시 7을 기준으로 분할한다면, 7을 기준으로 서브 트리가 만들어진다.

6을 기준으로 한다면 6이 하나의 노드가 된다.

그래서 이진 탐색의 과정은 이진 트리와 유사한 구조를 갖는다고 표현할 수 있다.

이진 탐색 트리는 다음의 조건을 만족시켜야 한다.

1. 이진 트리여야 한다. 즉, 각 노드가 최대 2개의 차일드 노드를 갖는 트리여야 한다.

2. 모든 노드는 서로 다른 하나의 값만 가지고 있어야 한다.

3. 루트 노드 > 왼쪽 부분 트리

4. 루트 노드 < 오른쪽 부분 트리

5. 왼쪽과 오른쪽 모드 이진 탐색 트리여야 한다.

아까 배운 조건을 만족시키는지 확인해보자. 일단 모든 노드는 서로 다른 값을 저장하고 있다.

또한, 왼쪽의 모든 값들은 루트 노드보다 작다.

오른쪽은 루트 노드의 값보다 크다.

부분 트리는 모두 이진 탐색 트리이다. 왼쪽이 루트보다 작고 오른쪽이 루트보다 크며 각각 다른 값을 가지고 있으므로.

이진 탐색 트리는 모양이 매우 다양하다. 균형이 맞춰져있지 않아도 모두 이진 탐색 트리의 조건을 갖추고 있다.