다음은 차수가 3인 B+ 트리(tree)의 초기 상태이다. 이 트리에 … | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 17년 1회차
다음은 차수가 3인 B+ 트리(tree)의 초기 상태이다. 이 트리에 색인키 'F', 'I', 'J'를 순서대로 삽입한 후의 모습은? (단, 단말 노드는 최대 2개의 원소를 포함할 수 있으며, 단말 노드의 분할 시 중간 위치의 값은 오른쪽 노드에 포함되도록 한다)
1
2
3
4
해설
삽입 후 트리는 루트 G, 그 아래 D·I, 다시 그 아래 C·E·H·K, 단말 노드 [A B][C][D][E F][G][H][I J][K L]인 높이가 한 단계 늘어난 구조가 된다.
F는 단말 [D E]에 들어가 [D E F]로 넘치므로 [D][E F]로 분할되고 E가 부모 [C D]로 올라간다. 부모 [C D E]도 넘쳐 D가 루트로 올라가 루트는 [D G]가 된다. I는 단말 [H]에 들어가 [H I]가 된다.
J는 [H I]에 들어가 [H I J]가 되어 [H][I J]로 분할되고 I가 부모 [H K]로 올라간다. [H I K]는 [H][K]로 나뉘며 I가 루트로 올라가고, 루트 [D G I]도 넘쳐 G를 새 루트로 하여 [D][I]로 분할된다.
- 루트가 G 하나이고 내부 노드가 [C E], [I K]로 남은 그림은 내부 노드 분할을 반영하지 않아 차수 3(키 최대 2개) 조건과 맞지 않는다.
- 단말에 [H I][J]가 생긴 그림은 중간값을 왼쪽 노드에 둔 것으로, 중간값을 오른쪽 노드에 포함한다는 조건에 어긋난다.
- 단말은 [I J][K L]인데 그 위 내부 노드를 J로 둔 그림은, 오른쪽 단말의 첫 키 K가 구분 키가 되어야 하므로 틀렸다.
오류나 개정된 내용이 보이면 알려주세요




