| ①초기 상태 | 리프에 25 35 45 | 리프 노드가 꽉 참 |
| ② 리프 분할 | 25 / 35 45로 분리 | 리프 노드 Split |
| ③ 키 승격 | 35가 부모로 올라감 | 분할 기준 키 Promote |
| ④ 부모 초과 | 부모가 15 25 35 | 부모도 꽉 참 |
| ⑤ 내부 분할 | 25가 새 루트로 | 트리 높이 증가 |
| ⑥ 최종 구조 | 루트 25, 자식 15 / 35 | 균형 유지 완료 |
기출문제. 2025
63. 다음 데이터가 순서대로 삽입되어 만들어진 차수가 3인 B+-트리에 대해 적절하게 설명된 것을 모두 나열한 것으로 옳은 것은? (단, B+-트리가 생성될 때 첫 노드는 최대 3개 키 값을 저장한다. 이후 리프노드는 최소 2개, 최대 3개 키 값을 저장하고, 루트 노드와 내부 노드는 최소 1개, 최대 2개 키 값을 저장한다. 키 값 a의 왼쪽 서브트리에 있는 노드들의 모든 키 값들은 a보다 작거나 같다. 노드에 키의 개수가 짝수 m일 때, 중간 키 값은 m/2 번째 값으로 한다.)
69, 15, 110, 90, 20, 120, 40, 125
가. 전체 노드의 개수는 7개이다.
나. 루트 노드의 키 값은 69이다.
다. 가장왼쪽에있는리프노드에들어갈키값은15, 40이다.
라. 루트노드의레벨이1이라고할때, 트리의높이는3이다.
① 가, 다 ② 가, 나, 라
③ 나, 다, 라 ④ 가, 나, 다, 라
정답 : ② 가, 나, 라
해설 :
Step 1: 초기 삽입 (69, 15, 110)
첫 노드는 최대 3개까지 저장 가능하므로 분할 없이 채워집니다.
[ 15, 69, 110 ]Step 2: 90 삽입 (첫 번째 분할)
리프 노드 최대치(3개)를 초과하여 분할됩니다. 중간값 69가 부모로 올라가고, a <= 69 조건에 따라 69는 왼쪽 노드에 남습니다.
Step 3: 20, 120 삽입
각각의 리프 노드 여유 공간에 정렬되어 들어갑니다.
Step 4: 40 삽입 (두 번째 분할)
왼쪽 리프 [ 15, 20, 40, 69 ]가 넘쳐서 분할됩니다. 중간값 20이 부모 노드로 올라갑니다.
Step 5: 125 삽입 (세 번째 분할 및 루트 분할)
- 오른쪽 리프 [ 90, 110, 120, 125 ]가 분할되어 중간값 110이 부모로 올라갑니다.
- 이때 부모 노드가 [ 20, 69, 110 ]이 되어 **내부 노드 최대 키(2개)**를 초과합니다.
- 내부 노드에서도 중간값 69가 새로운 루트로 올라가며 트리의 높이가 높아집니다.
최종 트리 구조:
핵심 요약
- 루트 노드 키: 69 (1개)
- 리프 노드 개수: 4개
- 트리의 높이(Height): 3
- 전체 노드 개수 : 7
가. 전체 노드의 개수는 7개이다.
나. 루트 노드의 키 값은 69이다.
다. 가장왼쪽에있는리프노드에들어갈키값은15, 40이다. 틀림 (15,20)
라. 루트노드의레벨이1이라고할때, 트리의높이는3이다.
