다음은 노드의 차수가 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] 하나라는 점과 맞지 않는다.
오류나 개정된 내용이 보이면 알려주세요
