Height Risk

BST 성능은 노드 수보다 높이 H에 먼저 묶인다

무작위 입력에서는 평균적으로 낮은 높이를 기대할 수 있지만, 정렬된 입력을 그대로 넣으면 BST가 연결 리스트처럼 기울어집니다.

균형에 가까운 입력

8
3
10
1
6
14
H ≈ log N 삽입·탐색·삭제가 평균적으로 짧은 경로에서 끝납니다.

정렬된 입력

1
→
3
→
6
→
8
→
10
→
14
H ≈ N 한쪽으로만 내려가므로 최악 시간복잡도 O(N)에 가까워집니다.
Hash

존재 여부만 필요

정렬 순서와 범위 질의가 없다면 해시가 더 단순합니다.

Balanced BST

정렬·범위 질의 필요

predecessor, successor, range query가 있으면 균형 트리를 우선 봅니다.

Plain BST

학습·소규모 구현

삭제 분기와 불변식 학습에는 좋지만 편향 테스트가 필요합니다.

판단 기준: 평균 O(log N)만 보고 BST를 고르면 안 됩니다. 입력 분포가 정렬될 수 있다면 높이 H를 먼저 의심해야 합니다.