이진 탐색트리(binary search tree) T에서 k보다 큰 키… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 07년 1회차
이진 탐색트리(binary search tree) T에서 k보다 큰 키들의 개수를 찾는 클래스 함수 numGreaterThan(T, k)을 작성한다고 가정하자. 트리에 포함된 모든 키들은 상이하고, 각 노드 x는 링크 필드인 left 및 right와 데이터 필드인 data를 가지며, 추가적으로 하나의 데이터 필드 numDesc를 포함한다. numDesc는 x를 루트(root)로 하는 부분 트리에 포함된 모든 키들의 개수로 초기화되어 있다. 아래 코드에서 밑줄 친 부분에 해당되는 문장은 무엇인가?int numGreaterThan(T, k)
{
if (T == NULL) return 0;
else if (T.key <= k) return numGreaterThan(T.right, k);
else return _________________________________;
}
1
T.right.numDesc - 1
2
numGreaterThan(T.left, k) + 1
3
T.right.numDesc + numGreaterThan(T.left, k) - 1
4
T.right.numDesc + numGreaterThan(T.left, k) + 1
해설
빈칸에는 T.right.numDesc + numGreaterThan(T.left, k) + 1이 들어간다.
T.key > k이면 오른쪽 부분 트리의 키는 모두 T.key보다 커서 그 개수 numDesc가 전부 포함되고, T 자신도 1개로 더해진다. 왼쪽 부분 트리는 k보다 큰 키가 일부만 있을 수 있어 재귀로 센다.
- 오른쪽 부분 트리 개수에서 1만 빼는 식: 루트와 왼쪽 부분 트리를 모두 빠뜨린다.
- 왼쪽 재귀 결과에 1만 더하는 식: 오른쪽 부분 트리 전체를 빠뜨린다.
- 오른쪽 개수와 왼쪽 재귀 결과에서 1을 빼는 식: 루트 T를 더해야 할 자리에서 오히려 1을 뺀다.
오류나 개정된 내용이 보이면 알려주세요