다음 이진 검색 트리에서 노드 이동 또는 포인터 변경의 횟수를 최소화하… | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 24년 1회차
다음 이진 검색 트리에서 노드 이동 또는 포인터 변경의 횟수를 최소화하면서 노드를 삭제하는 과정의 설명으로 옳지 않은 것은?
1
노드 8을 삭제하려면 노드 15에서 노드 8을 가리키는 포인터를 NIL(또는 NULL)로 변경한다.
2
노드 25를 삭제하려면 그 자리에 노드 30을 놓는다.
3
노드 50을 삭제하려면 노드 40이 노드 60을 직접 가리키도록 포인터를 변경한다.
4
노드 60을 삭제하려면 그 자리에 노드 55 또는 노드 66을 놓는다.
해설
옳지 않은 설명은 노드 25를 삭제할 때 그 자리에 노드 30을 놓는다는 것이다.
25는 왼쪽 자식 20과 오른쪽 자식 30을 모두 가지므로, 그 자리에는 왼쪽 서브트리의 최댓값 20이나 오른쪽 서브트리의 최솟값 27이 와야 한다. 30을 올리면 30의 왼쪽에 있던 27·29와 20을 함께 재배치해야 해 이동 횟수가 최소가 되지 않는다.
- 노드 8 삭제: 자식이 없는 리프이므로 부모 15의 해당 포인터만 NIL로 바꾸면 된다.
- 노드 50 삭제: 오른쪽 자식 60 하나만 가지므로 부모 40이 60을 직접 가리키게 하면 된다.
- 노드 60 삭제: 자식이 둘이므로 선행자 55나 후계자 66을 그 자리에 놓는다.
오류나 개정된 내용이 보이면 알려주세요