Sample Solutions to Quiz 2 B+ Trees
Marking scheme (3 marks):
Deduct 1.5 for each error. Then, see if the rest of their diagram would be OK.
Deduct 1.0 for smaller errors (like leaving off the last key if it doesn’t matter for
the last split).
Deduct 3.0 for a 3-level B+ tree or an unbalanced tree (one path longer than the
other). This would be a major error … unless it was for the very last step, in
which case -1.5.
Deduct 0.5 if they copied up from the left, rather than from the right. In other
words, when splitting 4-keys with a 5th, if they have 3 keys to the left, and 2 keys to the right, but copied up the first key of the right child, that’s 2.5/3.0. The rest must be consistent; they can’t mix and match; otherwise, -1.5, plus deductions for any other kinds of errors.
Deduct 0.5 if they copied up from the left, rather than from the right. In other words, when splitting 4-keys with a 5th, if they have 3 keys to the left, and 2 keys to the right, but copied up the middle key (last one on the left), that’s 2.5/3.0. In this case, they must have consistently used <= for the left child, and > for the right child; if not, automatically -1.5 The rest must be consistent after that; they can’t mix and match; otherwise, -1.5, plus deductions for any other kinds of errors.
The 3 versions of this quiz question start on the next page. I’m keeping them on 1 page each to make them more readable.
1
Version 1 of the Quiz: 23, 12, 17, 65, 3, 90, 27, 7, 8, 9
The first 4 keys fit in the empty root node:
12, 17, 23, 65
Insert 3. This causes the first split. (OK to add 90 to right child)
17
3, 12
17, 23, 65
If they got the above step right; they’re guaranteed to get at least 1.0 marks out of 3.0.
Insert 90 and 27. This causes the second split. (OK to add 7 and 8 to leftmost child)
17,27
3,12 17,23 27,65,90
Insert 7, 8, and 9. This causes the third split.
8, 17, 27
3,7 8,9,12 17,23 27,65,90
2
Version 2 of the Quiz: 36, 12, 20, 48, 7, 17, 18, 4, 79, 19, 64
The first 4 keys fit in the empty root node:
12, 20, 36, 48
Insert 7. This causes the first split. (OK to add 17 and 18 to left child)
20
7, 12
20,36,48
If they got the above step right; they’re guaranteed to get at least 1.0 marks out of 3.0.
Insert 17, 18, and 4. This causes the second split. (OK to add 79 and 19 to right and center children, respectively)
12, 20
4,7 12,17,18 20,36,48
Insert 79, 19, and 64. This causes the third split.
12, 20, 48
4,7 12,17,18,19 20,36 48,64,79
3
Version 3 of the Quiz: 16, 12, 24, 55, 27, 61, 38, 29, 37, 25
The first 4 keys fit in the empty root node:
12, 16, 24, 55
Insert 27. This causes the first split. (OK to add 61 to the right child, but not both 61 and 38 yet)
24
12,16
24,27,55
If they got the above step right; they’re guaranteed to get at least 1.0 marks out of 3.0.
Insert 61 and 38. This causes the second split. (OK to add 29 and 37 to the centre child)
24, 38
12,16 24,27 38,55,61
Insert 29, 37, and 25. This causes the third split.
24, 27, 38
12,16 24,25 27,29,37 38,55,61
4