HeadingBST의 깊이가 일반적으로 O(lg(n))인 이유

Introduction to Algorithms 라는 책이 사용한 증명 내용에 추가적인 설명들을 더한 내용입니다.

일단 먼저 수학적인 분석을 위해서 트리의 높이를 수학적으로 정의하겠습니다.

트리의 높이를 $h_{tree}$​라고 정의했을 때,

$h$는 이렇게 정의할 수 있습니다.

$h_{tree} = 1 + max(h_{left-subtree},h_{right-subtree})$

트리의 왼쪽 부분 트리와 오른쪽 부분 트리의 중 큰 높이에 1을 더한 값이죠.

이 부분은 직관적으로 이해할 수 있죠?

이 부분을 조금 다르게 표현해 보겠습니다.

총 n 개의 노드를 갖는 트리의 높이를 $h_{n}$​이라고 할게요

이진 트리에서는 root 노드 하나가 있고,

왼쪽에는 root 노드보다 작은 데이터들이,

그리고 오른쪽에는 root 노드보다 큰 데이터들이 저장됩니다.

root 노드에 저장된 데이터가 임의로 정해졌다고 가정하고

모든 노드에서 $i$번째로 큰 데이터라고 할게요

그럼 왼쪽 부분 트리에는 노드가 $i-1$개,

그리고 오른쪽 부분 트리에는 $n-i$가 있을텐데요.

위에 있는 수학식을 조금 바꿔서 이렇게 나타낼 수 있겠죠?

$h_{n} = 1 + max(h_{i-1}, h_{n-i})$

왼쪽 항 $h_{i - 1}$​은 root 노드의 왼쪽 부분 트리의 높이,

그리고 오른쪽 항 $h_{n-i}$​ 은 root 노드의 오른쪽 부분 트리의 높이를 나타냅니다.

다음은 증명을 위해서 두 항에 지수 함수를 취해줍니다.

$Y_{n} = 2^{h_{n}} = 2^{1 + max(h_{i - 1}, h_{n - i})}$

이 값을 편하게 $Y_n$​ , 지수 높이(exponential height)라고 부를게요.

지수 함수에서 차수의 덧셈은 일반 항에서 곱셈으로 나타낼 수 있는데요.

가장 오른쪽 식을 조금 정리하면 이렇게 나타낼 수 있습니다.

$Y_n = 2 \times max(2^{h_{i - 1}}, 2^{h_{n - i}}) = 2 \times max(Y_{i - 1}, Y_{n - i})$

$Y_n$​ 을 또 다른, 더 작은 $Y$ 를 사용해서 나타냈습니다.

이제 이 지수 높이 $Y_n$​ 의 기댓값을 계산할게요.

기댓값은 대문자 알파벳 E를 써서 나타냅니다.

각 항을 E로 둘러싸고 기댓값을 구해볼게요.

$E[Y_n] = E[2 \times max(Y_{i - 1}, Y_{n - i})]$

여기서 오른쪽 항의 기댓값을 계산하면 됩니다.

여기서 $i$ 는 이진 트리 안에 있는 데이터 중

root 노드에 있는 노드가 $i$ 번째로 큰 노드라는 뜻이잖아요?

$i$ 를 임의로 골랐기 때문에

$n$ 개의 노드에서 임의로 하나의 노드를 고를 확률은 $\frac{1}{n}$​ 입니다.

그 다음에는 이렇게 식을 바꿔줄 수 있습니다.

$E[Y_n] = \sum_{i = 1}^{n} \frac{1}{n}E[2 \times max(Y_{i - 1}, Y_{n - i})] = \frac{2}{n}\sum_{i = 1}^{n}E[max(Y_{i - 1}, Y_{n - i})]$

뭘 했는지 설명드릴게요.

기댓값을 구하기 위해서는 특정 일이 일어날 확률$(i = \frac{1}{n}​)$ 곱하기

그 일이 일어났을 때의 높이의 기댓값의 합을 계산해야 합니다.

$(E[2 \times max(Y_{i - 1}, Y_{n - i}))$

$i$ 가 1 부터 n까지 돌면서 나올 수 있는 모든 값들을 더해줍니다.

그리고 기댓값 안에서 하는 상수 곱셈은 기댓값 밖으로 뺄 수 있기 때문에

중간 식에서 오른쪽 식으로 바꿔줄 수 있습니다.

다음에는 기댓값에서 $max$ 를 지워주고 조금 더 계산하기 편한식으로 바꿔줄게요.

== 대신 부등호를 쓸 건데요.

$E[Y_n] = \frac{2}{n}\sum_{i = 1}^{n}E[max(Y_{i - 1}, Y_{n - i})] \leq \frac{2}{n}\sum_{i = 1}^{n} (E[Y_{i - 1}] + E[Y_{n - i}])$

이렇게 표현할 수 있습니다.

이게 뭘 한 건지 예시를 통해 설명 드릴게요.

$max(10, 15)$이 식은 10과 15중 둘 중 더 큰 값을 선택하겠다는 의미인데요.

두 값 중 큰 값을 선택한 것은 항상, 두 값을 더한 값보다 작을 수 밖에 없잖아요?

식으로 나타내면

$max(10, 15) \leq 10 + 15$

이렇게 되는데요.

이 간단한 개념을 좀 더 어려운 수학식에 적용한 겁니다.

중간 식에서 어떻게 오른쪽 식으로 바꿨는지 보이시죠?

그냥 $max(10, 15) \leq 10 + 15$이거랑 똑같은 걸 해준 겁니다.

$\frac{2}{n}\sum_{i = 1}^{n} (E[Y_{i - 1}] + E[Y_{n - i}])$

이 식에 대해서 생각해봅시다.

이 식은 i를 1부터 n까지 돌면서 모든 값을 더해주는 건데요.

괄호 안에 들어가는 내용을 살펴볼게요.

$i = 1$일 때: $E[Y_{0}] + E[Y_{n - 1}]$

$i=2$일 때: $E[Y_{1}] + E[Y_{n - 2}]$

$i=3$일 때: $E[Y_{2}] + E[Y_{n - 3}]$

$\vdots$

$ i = n − 1$ 일 때: $E[Y_{n - 2}] + E[Y_{1}]$

$i = n$ 일 때: $E[Y_{n - 1}] + E[Y_{0}]$

이렇게 표현할 수 있습니다.

정확히는 $E[Y_0]$부터 $E[Y_{n-1}]$ 까지 더하는데

이게 왼쪽 항, 그리고 오른쪽 항 이렇게 두번 반복 되잖아요?

그렇기 때문에 이렇게 표현할 수 있습니다.

$\frac{2}{n}\sum_{i = 1}^{n} (E[Y_{i - 1}] + E[Y_{n - i}]) = \frac{2}{n}\sum_{i = 0}^{n-1} 2E[Y_i] = \frac{4}{n}\sum_{i = 0}^{n-1} E[Y_i]$

그리고 이걸 원래 식에 대입하면 이렇게 되죠.

$E[Y_n] \leq \frac{4}{n}\sum_{i = 0}^{n-1} E[Y_i]$

여기까지 오는데도 좀 벅찬데요.

여기서 좀 뜬금 없이 들릴 수 있는 내용을 증명할게요.

이게 어떻게 저희 증명에 맞는지 이해가 안 되실 수 있는데요 일단 한 번 보세요.

바로 이 식을 증명할 건데요.

$\sum_{i = 0}^{n - 1} \binom{i + 3}{3} = \binom{n + 3}{4}$

여기서 괄호는 조합(Combination)을 나타내는 식입니다.

C를 사용해서 나타낼 때도 있는데요.

위에 있는 경우의 수에서 아래 있는 숫자 만큼의 항목을 선택할 수 있는 경우의 수입니다.

그러니까

$\binom{4}{2}$ 이건 4 개 중 순서에 상관없이 2개를 선택할 수 있는 경우의 수입니다.

계산은 $\frac{4 \times 3}{2 \times 1}$​ 이렇게 해서 6이 되죠.

오른쪽 식에 대해서 먼저 생각해볼게요.

오른쪽 식은 총 $n + 3$개의 요소에서 순서에 상관 없이 4 개를 선택하는 경우의 수입니다.

이때, 선택한 4개의 요소 중 가장 큰 요소가

모든 요소 중 $i + 4$번째로 가장 큰 요소라고 할게요.

총 요소가 $n + 3$개가 있으니까

$i$ 는 0에서 $n - 1$까지가 될 수 있겠죠?

$i = 0$ 이면, 선택한 가장 큰 요소가 모든 요소 중 4 번째로 가장 크고,

$i = n - 1$ 이면, 선택한 요소가$n + 3$ 번째로 가장 큰 요소 (모든 요소중 가장 큰 요소)가 됩니다.

선택한 가장 큰 요소가 $i + 4$ 라는 건

나머지 요소들을 $i + 3$개 중에서 세 개를 선택해야된다는 말입니다.

$i$ 를 0부터 $n - 1$까지 돌면서 $i + 3$개의 요소들에서 세 개를 선택한 값을 더해주면

$n+3$ 개의 요소 중에서 4개의 요소를 선택하는 경우의 수를 구할 수 있는 거죠.

이걸 수학식으로 나타낸 게

바로 $\sum_{i = 0}^{n - 1} \binom{i + 3}{3} = \binom{n + 3}{4}$ 고요.

방금 증명한 식을 가지고 이번에는

$\frac{4}{n}\sum_{i = 0}^{n-1} E[Y_i] \leq \frac{1}{4}\binom{n + 3}{4}n4​$ 를 귀납적으로 증명하겠습니다.

먼저 위 식이 $n = 0$_$n = 1$_일 때 성립한다는 것을 보여주겠습니다.

$Y_0 = 0 = E[Y_0] \leq \frac{1}{4}\binom{3}{3} = \frac{1}{4}$

$Y_1 = 1 = E[Y_1] \leq \frac{1}{4}\binom{4}{3} = 1$두 경우 성립합니다

다음으로는 0에서 $n - 1$까지 명제가 성립한다는 가정하에,

$n$ 일 경우도 명제가 성립한다는 걸 보여주겠습니다.

$E[Y_n] \leq \frac{4}{n}\sum_{i = 0}^{n-1} E[Y_i]$

$\leq \frac{4}{n}\sum_{i = 0}^{n-1} \frac{1}{4}\binom{i + 3}{4}$ (귀납적으로 명제가 성립한다고 가정한다)

$= \frac{1}{n} \sum_{i = 0}^{n - 1}\binom{i + 3}{3}$( $\frac{1}{4}$ ​를 밖으로 빼냄)

$= \frac{1}{n}\binom{n + 3}{4}$ ($\sum_{i = 0}^{n - 1} \binom{i + 3}{3} = \binom{n + 3}{4}$ 이기 때문에)

= $\frac{1}{n} \times \frac{(n + 3)!}{4!(n - 1)!}​$

= $\frac{1}{4} \times \frac{(n + 3)!}{3!n!}​$

=$\frac{1}{4}\binom{n + 3}{3}$ ($n$의 경우에도 명제가 성립한다는 걸 증명했습니다)

이제

$E[Y_n]$에 대한 부등식을 구했는데요.

$\frac{1}{4}\binom{n + 3}{3}$보다 항상 작거나 같다는 결론이 나오죠?

$Y_n$는 우리가 처음에 지수 높이 함수라고 불렀는데요.

$2^{h_n}$​로 정의했었죠?

함수 $2^x$는 아래로 볼록한 함수 (convex function)이기 때문에 옌센 부등식(Jensen’s inequality)을 적용할 수 있습니다.

그럼 $E[Y_n]$에 대해서 다음과 같은 식을 세울 수 있죠.

$2^{E[h_n]} \leq E[2^{h_n}] = E[Y_n]$

이제 이걸 가지고:

$2^{E[h_n]} \leq E[Y_n] \leq \frac{1}{4}\binom{n + 3}{3}$이렇게 할 수 있고,

오른쪽 식을 정리하면

$2^{E[h_n]} \leq \frac{1}{4} \times \frac{(n + 3)(n + 2)(n + 1)}{6} = \frac{n^3 + 6n^2 + 11n + 6}{24}$​이 됩니다.

각 항에 로그 함수를 취하면 다시 이렇게 할 수 있습니다.

$\log_22^{E[h_n]} = E[h_n] \leq \log_2(\frac{n^3 + 6n^2 + 11n + 6}{24})$

오른쪽 식 로그 안에 있는 항 중 차수가 가장 큰 항이 $n^3$인데요.

이것의 로그를 취하면 $3\lg(n)$이잖아요?

그렇기 때문에 $n$개의 노드를 갖는 이진 탐색 트리의

높이 $h_n$​의 기댓값 $E[h_n]$ 은 _$O(\lg(n))$_이라고 할 수 있습니다.