다음과 같은 4개의 노드를 가진 2-3 트리에 키 값 6을 추가하였을 … | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 12년 1회차
다음과 같은 4개의 노드를 가진 2-3 트리에 키 값 6을 추가하였을 때, 트리의 전체 노드의 수는?
1
4개
2
5개
3
6개
4
7개
해설
키 6을 넣으면 분할이 루트까지 전파되어 높이가 늘고, 전체 노드는 7개가 된다.
6은 오른쪽 리프 [7, 9]에 들어가 [6, 7, 9]로 넘치므로 분할되고 가운데 키 7이 부모로 올라간다. 루트가 [2, 4, 7]로 다시 넘쳐 분할되며 4가 새 루트가 된다.
결과: 루트 [4] / 내부 노드 [2], [7] / 리프 [1], [3], [6], [9] → 1 + 2 + 4 = 7개.
- 4개: 삽입 전 노드 수 그대로이며, 리프가 넘쳐 분할되는 것을 반영하지 않았다.
- 5개: 리프 분할만 반영하고 루트 분할을 빠뜨린 경우다.
- 6개: 루트 분할은 반영했으나 새 루트 노드 생성을 세지 않은 경우다.
오류나 개정된 내용이 보이면 알려주세요
