차수가 3인 B-트리에 G를 삽입한 후 모습은? | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 15년 1회차
차수가 3인 B-트리에 G를 삽입한 후 모습은?
문제 이미지
1
2
3
4
해설

G를 넣으면 단말 노드가 넘쳐 중간 키 F가 부모로 올라가 루트가 [D, F], 자식이 [A, C]·[E]·[G]인 트리가 된다.

차수 3인 B-트리는 노드당 키를 최대 2개까지 가진다. G는 D보다 크므로 오른쪽 단말 [E, F]로 가서 [E, F, G]가 되어 넘치고, 분할로 E와 G가 나뉘며 F가 루트로 올라간다. 루트는 키가 1개뿐이었으므로 [D, F]로 수용된다.

  • 루트 [D, E], 단말 [A]·[C]·[F, G]인 트리: 삽입과 무관한 왼쪽 단말 [A, C]까지 쪼개져 있어 분할 결과가 아니다.
  • 루트 [C, F], 단말 [A, D]·[E]·[G]인 트리: 루트의 D가 아래로 내려가는 변화는 삽입 과정에서 일어나지 않는다.
  • 루트 [D, G], 단말 [A, C]·[E]·[F]인 트리: 분할 시에는 넘친 노드의 중간 키(F)가 올라가야 하며, G가 올라가면 F가 G보다 오른쪽 자리에 놓이는 모순도 생긴다.

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

이어서 풀어보기

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