BST의 최악의 경우의 예와 시간 복잡도

Summary: 이진 탐색 트리(BST)의 탐색·삽입·삭제 연산은 트리의 높이 h에 비례하는 O(h) 비용을 가진다. 트리가 균형을 이루면 h ≈ log n이어서 O(log n)이지만, 정렬된 데이터가 그대로 삽입되어 한쪽으로 치우친 편향 트리가 되면 h = n이 되어 O(n)으로 떨어진다. 이 글은 BST의 정의, 시간 복잡도 표기, 그리고 편향 트리에서 최악의 경우가 발생하는 과정을 정리한다.

BST이란?

이진 탐색 트리(BST)는 다음 조건을 만족하는 이진 트리다.

노드의 왼쪽 하위 트리에는 그 노드의 키보다 작은 키를 가진 노드만 존재한다.
노드의 오른쪽 하위 트리에는 그 노드의 키보다 큰 키를 가진 노드만 존재한다.
왼쪽 서브트리와 오른쪽 서브트리도 각각 BST 조건을 만족한다.
중복된 키를 가지지 않는다.

이 정렬 조건 덕분에 각 노드에서 키를 한 번 비교하면 다음에 내려갈 서브트리를 한쪽으로 정할 수 있다.

시간 복잡도란?

시간 복잡도는 알고리즘을 실행하는 데 걸리는 시간을 입력 길이의 함수로 정의한 것이다. 연산의 수가 증가하거나 감소할 때 실행 시간이 어떻게 변하는지에 대한 정보를 제공한다. 즉 절대적인 실행 시간이 아니라 입력 크기에 따른 증가 양상을 나타낸다.

시간 복잡도	의미
O(1)	입력 크기와 관계없이 일정
O(log n)	입력이 커져도 연산 수가 천천히 증가
O(n)	입력 크기에 비례해서 증가
O(n²)	입력 크기의 제곱에 비례해서 증가

Big O 표기법

Big O 표기법은 입력 데이터 크기 n과 연산 수 N 사이의 관계, 즉 시간 복잡도의 성장 속도를 O(n)과 같은 형태로 표현한 것이다. 여기서 O는 성장 속도를, n은 입력 길이를 가리킨다.

참고) 세타 표기법 (Θ)

세타 표기법은 알고리즘 실행 시간의 점근적 성장률을 나타낸다. 입력 크기가 n일 때 알고리즘의 실행 시간이 f(n)과 동일하다는 것을 의미한다. 예를 들어 Θ(n log n)은 입력 크기가 커질수록 실행 시간이 n log n과 동일하게 증가한다는 뜻이다.

이진 트리에서의 시간 복잡도

BST의 주요 연산은 탐색, 삽입, 삭제이며, 이 연산들의 시간 복잡도는 트리의 높이 h에 따라 결정된다. 즉 BST 연산의 시간 복잡도는 O(h)다.

평균: O(log n) — 트리가 균형을 이루면 h ≈ log n이다. 이 경우 삽입 과정도 log n 단계에서 끝난다.
최악: O(n) — 트리가 한쪽으로 치우치면 h = n이 된다. 리스트와 같은 구조가 되어 삽입에 n 단계를 거칠 수 있다.

연산 비용이 높이에 비례하므로, 트리의 높이가 n까지 커지는 상황이 곧 최악의 경우가 된다.