차수(m)가 3인 공백 B-트리에 19, 18, 2, 15, 6, 13… | [7급 국가직 자료구조론] 20년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 20년 1회차
차수(m)가 3인 공백 B-트리에 19, 18, 2, 15, 6, 13, 7을 순서대로 삽입하여 구성한 B-트리에 대한 설명으로 옳은 것은?
1
트리의 높이(height)가 1이다.
2
15는 루트(root) 노드에 저장되어 있다.
3
3개의 자식(child) 노드를 가지는 노드가 존재한다.
4
6이 저장된 노드와 18이 저장된 노드는 형제(sibling) 관계이다.
해설
6이 저장된 노드와 18이 저장된 노드는 형제 관계이다.
차수 3인 B-트리는 노드당 키가 최대 2개이므로 키가 3개가 되면 가운데 키를 부모로 올려 분할한다. 2 삽입 때 18이, 6 삽입 때 6이 올라가 루트가 [6, 18]이 되고, 7 삽입 때 [7, 13, 15]에서 13이 올라가 루트 [6, 13, 18]이 다시 분할되면서 13이 새 루트가 된다.
최종 트리는 루트 13 아래 6과 18이 있고, 6의 자식은 2와 7, 18의 자식은 15와 19이다.
- 트리의 높이가 1: 루트 아래로 두 단계가 더 있는 3레벨 트리이므로 높이가 1이 아니다.
- 15가 루트에 저장: 루트에는 13만 있고 15는 리프에 있다.
- 자식 3개인 노드가 존재: 모든 내부 노드가 키 1개와 자식 2개만 가진다.
오류나 개정된 내용이 보이면 알려주세요