Adding elements

Consider this 2-3 tree that was constructed by inserting [1, 2, 3, 4, 5, 6] in order. Draw the tree after inserting the element 7 by overstuffing the rightmost leaf node.

1

2 4

1

3

5 6

Case analysis

Let’s consider how insertion orders can affect the shape of the resulting 2-3 tree.

Give an insertion order for 1, 2, 3, 4, 5, 6, 7 that yields the tallest possible tree.

​

​

​

​

Give an insertion order for 1, 2, 3, 4, 5, 6, 7 that yields the shortest possible tree.

2

Fill factor

Consider this tree constructed by inserting [0, 4, 6, 1, 13, 18, 19, 20, 7, 8, 9, 22, 25].

• Give 4 numbers that, when inserted, maintain the current 2-3 tree height.
• Give 4 numbers that, when inserted, increase the current 2-3 tree height.

3

13

4 7

19 22

0 1

6

8 9

18

20

25

Height proof

Consider two 2-3 trees with 3 levels storing 7 elements each. Draw one additional node to show a 4-level tree with 15 elements using these two subtrees as children.

​

​

​

​

​

Give an exact expression (not asymptotic notation) describing the relationship between the size and the number of levels in a 2-3 tree.

​

A 2-3 tree with k levels must store at least elements.

… Therefore, a 2-3 tree storing N elements must always have a height in O(log N).

4

k = 3