다음 이진탐색트리(Binary Search Tree)에서 색인키 ‘20… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 15년 1회차
다음 이진탐색트리(Binary Search Tree)에서 색인키 ‘20’을 삭제한 후, 트리를 재구성한 것으로 옳은 것은?
문제 이미지
1
2
3
4
해설

자식이 둘인 20을 삭제하면 오른쪽 서브트리의 최솟값(중위 후속자) 24가 그 자리로 올라가, 24의 왼쪽에 9(5, 14), 오른쪽에 28이 있고 28의 오른쪽 자식이 32인 트리가 된다.

20의 오른쪽 서브트리(28, 24, 32)에서 가장 작은 값은 단말 노드 24이므로, 24를 20 자리로 옮기고 원래 24 노드를 지운다. 그 결과 28은 왼쪽 자식을 잃고 오른쪽 자식 32만 남는다.

  • 20 자리에 28, 28의 오른쪽에 32, 32의 왼쪽에 24를 둔 트리: 24가 28보다 작은데 28의 오른쪽 서브트리에 있어 이진탐색트리 조건을 어긴다.
  • 24의 오른쪽에 32, 32의 오른쪽에 28을 둔 트리: 28은 32보다 작으므로 32의 오른쪽 자식이 될 수 없다.
  • 20 자리에 32, 32의 오른쪽에 28, 28의 왼쪽에 24를 둔 트리: 28과 24가 32보다 작은데 32의 오른쪽 서브트리에 있어 이진탐색트리 조건을 어긴다.

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

이어서 풀어보기

[7급 국가직 자료구조론] 15년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기