빈 이진 탐색 트리에 1, 2, 3, …, 1000의 순서로 값을 삽입했다(균형을 잡는 조작은 하지 않는다). 이 트리에서 1000을 찾을 때, 루트부터 비교하기 시작하여 찾을 때까지 비교하는 노드의 수는?

정답: C. 1,000

오름차순으로 삽입하면 새 값은 매번 그때까지의 최댓값의 오른쪽 자식이 되므로, 트리는 오른쪽으로만 뻗은 한 줄(높이 999)이 됩니다. 1000은 맨 아래에 있으므로 1, 2, …, 1000의 1,000개 노드와 비교하게 되며, 연결 리스트를 앞에서부터 따라가는 것과 같은 O(n)입니다. 균형 잡힌 트리라면 단의 수는 약 log₂ 1000 ≈ 10이므로, AVL 트리나 레드-블랙 트리처럼 삽입이나 삭제 때마다 모양을 정돈하는 균형 이진 탐색 트리를 사용하면 최악에도 O(log n)을 유지할 수 있습니다.