다음 키값을 순서대로 삽입하여 B－트리를 구성할 때, 노드 오버플로(o… | [7급 국가직 자료구조론] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 25년 1회차
다음 키값을 순서대로 삽입하여 B－트리를 구성할 때, 노드 오버플로(overflow)로 인한 노드 분할 횟수는? (단, 차수는 3이다)1, 5, 7, 11, 13, 15, 17, 19
1
1
2
2
3
3
4
4
해설
차수 3인 B-트리(노드당 키 최대 2개)에 차례로 넣으면 7, 13, 17 삽입 때 분할이 일어나고 17에서는 루트까지 연쇄 분할되어 총 4회이다.
7 삽입: [1, 5, 7] 오버플로 → 5를 올려 분할 (1회)
13 삽입: [7, 11, 13] 오버플로 → 11을 올려 루트 [5, 11] (2회)
17 삽입: [13, 15, 17] 오버플로 → 15를 올려 루트 [5, 11, 15]가 다시 오버플로 (3회) → 11을 올려 새 루트 생성 (4회)
19 삽입: [17, 19]로 들어가 분할 없음
- 1회: 7 삽입 때의 첫 분할만 센 값이다.
- 2회: 13 삽입까지의 분할만 센 값이다.
- 3회: 17 삽입 때 루트로 번지는 연쇄 분할을 빠뜨린 값이다.
오류나 개정된 내용이 보이면 알려주세요