차수가 3인 다음 B^{+}-트리에 키 값 1, 18, 19를 순차적으… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 14년 1회차
차수가 3인 다음 -트리에 키 값 1, 18, 19를 순차적으로 삽입할 때, 최종적인 -트리의 인덱스 노드(비단말 노드)들의 모습은? (단, 데이터 노드(단말 노드)는 최대 2개의 원소를 포함할 수 있으며, 데이터 노드의 분할 시 중간 위치의 값은 오른쪽 노드에 포함되도록 한다)
1
인덱스 노드: 루트 (18 : 22), 자식 (8 : 11), (19 : -), (41 : 58)
2
인덱스 노드: 루트 (18 : 22), 자식 (8 : 17), (19 : 22), (41 : 58)
3
인덱스 노드: 루트 (16 : 22), 자식 (8 : -), (17 : 18), (41 : 58)
4
인덱스 노드: 루트 (16 : 22), 자식 (8 : 11), (17 : 18), (41 : 58)
해설
최종 인덱스 노드는 루트 (16 : 22), 자식 (8 : -), (17 : 18), (41 : 58)이다.
1 삽입 시 (8, 11)이 넘쳐 (1)과 (8, 11)로 나뉘고 8이 인덱스 (16)에 올라가 (8 : 16)이 된다.
18 삽입 시 (16, 17)이 (16)과 (17, 18)로 나뉘고 17이 올라가 인덱스가 8, 16, 17로 넘치므로, 가운데 16이 루트로 승격해 루트는 (16 : 22), 왼쪽 인덱스는 (8), (17)로 갈린다.
19 삽입 시 (17, 18)이 (17)과 (18, 19)로 나뉘고 18이 올라가 인덱스가 (17 : 18)이 된다.
- 루트가 (18 : 22)라는 구성은 인덱스 분할 때 16이 루트로 올라가는 과정을 놓친 것이다.
- 자식이 (8 : 11)이라는 구성은 11이 데이터 노드 분할에서 인덱스로 올라간 적이 없으므로 틀렸다.
오류나 개정된 내용이 보이면 알려주세요
