안녕하세요. 바탕 국어연구소입니다.
한 세대에서 확인하는 데이터는 하나입니다. 비교를 통해 둘 중 하나를 선택하는 것이 아니라, 어느 쪽으로 갈지는 윗세대와의 비교에서 이미 정해지기 때문입니다.
지문은 입력되는 데이터가 뿌리 데이터와 비교되어 좌우 방향이 결정되고, 그 방향에 위치한 자식 세대 데이터와 비교되어 다음 방향이 결정되는 과정을 반복한다고 설명합니다. 즉 방향이 정해진 뒤에는 그 방향에 있는 자식 하나만 비교 대상이 되고, 반대쪽에 있는 자식은 확인하지 않습니다. 해설도 이렇게 CPU가 목표 데이터를 탐색할 때 세대별로 필수적으로 거쳐야 하는 하나의 데이터만 확인하게 된다고 풀이합니다.
<그림>에서 목표 데이터가 6인 경우로 보겠습니다.
1세대 : 뿌리 8과 비교합니다. 6은 8보다 작으므로 왼쪽으로 갑니다.
2세대 : 왼쪽에 있는 3과 비교합니다. 6은 3보다 크므로 오른쪽으로 갑니다. 이때 오른쪽 자식 세대의 10은 확인하지 않습니다.
3세대 : 3의 오른쪽 자식인 6을 확인합니다. 3의 왼쪽 자식 1은 확인하지 않습니다.
이렇게 세대마다 확인하는 데이터는 하나씩이고, 같은 세대의 반대쪽 데이터는 확인하지 않습니다. 이것이 지문에서 말하는 "불필요한 경로의 데이터를 확인하지 않을 수 있다"의 의미입니다. 학생이 생각하신 '최대 2'는 한 세대의 좌우 자식 데이터를 모두 비교하는 경우인데, 이진 탐색 트리에서는 윗세대와의 비교로 방향이 이미 정해지므로 그렇게 하지 않습니다. 따라서 ⑤는 적절한 선지입니다.