2.4.2 트리 연산의 시간 복잡도

이번에는 트리 연산의 시간 복잡도에 대해 알아보겠습니다. 검색의 경우 이론적으로 매번 검색 범위가 절반으로 줄어든다고 할 수 있습니다. 그러므로 N개의 노드를 가지고 있는 BST에서 검색에 필요한 시간은 T(N) = T(N/2) + 1 수식으로 표현할 수 있습니다. 이 수식을 시간 복잡도로 표현하면 T(N) = O(log N)입니다.

그러나 여기에 함정이 있습니다. 삽입 함수를 잘 분석해보면 트리의 모양이 원소 삽입 순서에 따라 결정된다는 점을 알 수 있습니다. 그리고 검색 범위가 앞서 사용한 수식처럼 T(N/2) 형태로 줄어드는 것도 항상 성립하지는 않습니다. 그러므로 시간 복잡도가 O(log N)이라는 것도 항상 정확하다고 볼 수 없습니다. 이후 균형 트리 부분에서 이 문제와 해결책에 대해 좀 더 자세히 살펴보고, 더불어 시간 복잡도를 좀 더 정확하게 계산하는 방법도 알아보겠습니다.

일단은 C++를 이용하여 BST를 직접 구현해보겠습니다.