다음 이진 탐색트리(binary search tree)에서 루트(roo… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 07년 1회차
다음 이진 탐색트리(binary search tree)에서 루트(root)노드가 삭제된 후의 상태는?
1
2
3
4
해설
루트 52를 삭제하면 오른쪽 서브트리의 최솟값인 54(중위 후속자)가 루트 자리로 올라간 트리가 된다.
자식이 둘인 노드를 삭제할 때는 오른쪽 서브트리의 가장 왼쪽 노드로 대체한다. 84 → 63 → 54로 내려가 54가 후속자가 되고, 54의 오른쪽 자식 58은 54가 있던 자리인 63의 왼쪽 자식으로 붙는다.
- 61을 루트로 한 트리는 후속자도 선행자(47)도 아닌 노드를 올리고 전체를 재배치한 형태라 삭제 연산의 결과가 아니다.
- 58을 루트로 한 트리도 후속자가 아닌 노드를 올리고 서브트리를 재구성해 삭제 연산의 결과와 다르다.
- 84를 루트로 한 트리는 오른쪽 서브트리에 84보다 작은 63·54 등이 있어 이진 탐색 트리 조건을 어긴다.
오류나 개정된 내용이 보이면 알려주세요




