무작위 입력
높이가 낮게 유지될 가능성이 있지만 최악 보장은 없습니다.
BST 높이 성능 기준
삽입 순서가 정렬돼 있으면 일반 BST는 연결 리스트처럼 기울어집니다. 평균 `O(log N)`만 믿지 말고 입력 분포와 균형 유지 필요성을 함께 판단합니다.
정렬된 입력
높이 `H`가 `N`에 가까워져 삽입과 탐색이 선형 비용으로 악화됩니다.
균형 유지
AVL, Red-Black Tree처럼 회전 규칙을 두면 최악 높이를 제어합니다.
존재 여부만 필요
정렬 순서가 필요 없다면 해시 셋이 더 단순하고 평균 조회 비용도 낮습니다.
범위 질의가 필요
정렬 순회와 predecessor, successor가 필요하면 균형 BST를 우선 검토합니다.
학습·소규모 구현
일반 BST는 삭제 분기와 불변식 학습에는 좋지만 편향 테스트를 함께 둡니다.