문제
다음 중 이진 탐색 트리(Binary Search Tree)의 특성으로 가장 옳지 않은 것은?
① 왼쪽 서브트리의 모든 노드 값은 루트보다 작다 ② 오른쪽 서브트리의 모든 노드 값은 루트보다 크다 ③ 중위 순회 시 항상 오름차순으로 정렬된 결과를 얻는다 ④ 모든 연산의 시간 복잡도가 항상 O(log n)으로 보장된다
정답
4번
해설
이진 탐색 트리에서 트리가 편향된 경우(한쪽으로만 치우친 경우) 탐색, 삽입, 삭제 연산의 시간 복잡도는 O(n)이 될 수 있다. 균형이 잘 맞춰진 경우에만 O(log n)이 보장된다. ① ② ③은 이진 탐색 트리의 기본 특성으로, 왼쪽은 작은 값, 오른쪽은 큰 값을 가지며, 중위 순회 시 정렬된 순서로 출력된다.