다음은 노드의 차수가 5인 B-트리의 현재 상태를 표현한 것이다. 현 … | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 19년 1회차
다음은 노드의 차수가 5인 B-트리의 현재 상태를 표현한 것이다. 현 상태에서 값 9를 삭제하였을 때, 결과 트리에 존재하는 노드 수를 종류별로 옳게 나타낸 것은? (단, n-노드란 (n - 1)개의 키를 저장한 노드를 의미한다)

2-노드  3-노드  4-노드  5-노드
문제 이미지
1
2  6  1  0
2
2  4  1  1
3
0  2  3  1
4
0  3  1  2
해설

값 9를 삭제한 결과 트리는 2-노드 0개, 3-노드 3개, 4-노드 1개, 5-노드 2개이다.

차수 5인 B-트리에서 루트 외 노드는 키를 최소 2개 가져야 한다. [9, 10]에서 9를 지우면 [10]만 남아 언더플로가 생기고, 왼쪽 형제 [5, 6]도 최소 개수라 빌려올 수 없으므로 부모 키 8을 내려 [5, 6, 8, 10]으로 합병한다.

그러면 부모 [3, 8]이 [3]으로 언더플로가 되고, 형제 [19, 22]도 최소라 루트 키 15를 내려 [3, 15, 19, 22]로 합병하며 이것이 새 루트가 된다.
결과: 루트 [3, 15, 19, 22] 아래 [1, 2], [5, 6, 8, 10], [16, 18], [20, 21], [24, 25, 26]이다.

  • 2-노드 2개·3-노드 6개·4-노드 1개 구성은 합병 없이 9만 지운 상태처럼 노드 수를 센 것으로, 합병 후 전체 노드는 6개뿐이다.
  • 2-노드 2개·3-노드 4개·4-노드 1개·5-노드 1개 구성은 키 1개짜리 노드가 남는다고 본 것으로, 합병 후에는 키 1개 노드가 없다.
  • 3-노드 2개·4-노드 3개 구성은 키 2개 노드([1, 2], [16, 18], [20, 21])가 3개, 키 3개 노드는 [24, 25, 26] 하나라는 점과 맞지 않는다.

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

이어서 풀어보기

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