<보기>의 이진 검색 트리(binary search tree… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
<보기>의 이진 검색 트리(binary search tree)에서 노드를 삭제하는 과정에 대한 설명으로 가장 옳지 않은 것은? (단, 노드 명칭과 노드 키 값은 동일하다.)
<보기>
문제 이미지
1
루트 노드를 삭제하기 위해 오른쪽 서브트리의 최솟값을 갖는 노드로 대체할 수 있고, 이때의 전체 수행시간은 트리의 높이에 비례한다.
2
노드 12를 삭제하기 위해 노드 15에서 노드 12를 가리키는 포인터가 노드 5를 가리키도록 변경한다.
3
노드 25를 삭제하기 위해 노드 22로 대체하고, 노드 15에서 노드 25를 가리키는 포인터를 NULL로 변경한다.
4
노드 5를 삭제하기 위해 노드 12에서 노드 5를 가리키는 포인터를 NULL로 변경한다.
해설

노드 25를 노드 22로 대체할 때 노드 15의 포인터를 NULL로 바꾸는 설명이 옳지 않다.

자식이 둘인 노드 25는 왼쪽 서브트리 최댓값 22(또는 오른쪽 서브트리 최솟값 35)로 키를 대체한 뒤, 원래 22가 있던 자리를 지워야 한다. 즉 노드 20의 오른쪽 포인터를 NULL로 바꿔야 하며, 15에서 25를 가리키는 포인터를 NULL로 하면 20·22·35까지 트리에서 떨어져 나간다.

  • 루트 15 삭제: 오른쪽 서브트리 최솟값 20을 찾아 대체하는 과정은 한쪽 경로만 따라 내려가므로 수행시간이 트리 높이에 비례한다(옳음).
  • 노드 12 삭제: 자식이 5 하나뿐이므로 부모 15의 왼쪽 포인터가 5를 가리키게 하면 된다(옳음).
  • 노드 5 삭제: 단말 노드이므로 부모 12의 왼쪽 포인터를 NULL로 바꾸면 된다(옳음).

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기