차수가 3인 다음 B^{+}-트리에 키 값 1, 18, 19를 순차적으… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 14년 1회차
차수가 3인 다음 B+B^{+}-트리에 키 값 1, 18, 19를 순차적으로 삽입할 때, 최종적인 B+B^{+}-트리의 인덱스 노드(비단말 노드)들의 모습은? (단, 데이터 노드(단말 노드)는 최대 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이 데이터 노드 분할에서 인덱스로 올라간 적이 없으므로 틀렸다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 14년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기