다음 이진검색트리에서 28을 삭제한 후, 28의 오른쪽 서브트리에 있는… | [9급 지방직 컴퓨터일반] 20년 1회차 기출문제 상세 페이지
1[9급 지방직 컴퓨터일반] 20년 1회차
다음 이진검색트리에서 28을 삭제한 후, 28의 오른쪽 서브트리에 있는 가장 작은 원소로 28을 대치하여 만들어지는 이진검색트리에서 41의 왼쪽 자식 노드는?
1
13
2
17
3
32
4
37
해설
삭제·대치 후 41의 왼쪽 자식 노드는 37이다.
28의 오른쪽 서브트리(43을 루트로 하는 부분)에서 가장 작은 원소는 왼쪽 끝까지 내려간 30이다. 30이 28 자리로 올라가면, 30이 있던 자리(41의 왼쪽)에는 30의 오른쪽 서브트리인 37(왼쪽 자식 32)이 연결된다.
- 13은 루트 노드로 삭제 과정에서 위치가 바뀌지 않는다.
- 17은 28 자리에 들어온 30의 왼쪽 자식으로 그대로 남는다.
- 32는 37의 왼쪽 자식으로 남으므로 41의 직접 자식이 아니다.
내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.