17.7 Exercises

Factual

1. Which of the following are valid 2-3 trees?

Problem 1

Only (a).

A 2-3 tree only allows up to 3 children, which means a node can only have at most 2 values. (b) has an extra value in the rightmost node.

A 2-3 tree must also be perfectly balanced. (c) is imbalanced.

A B-Tree node always has one more child than the number of values. So in a 2-3 tree, a node with 1 value has 2 children, and a node with 2 values has 3 children. (d) violates this with the node 21, which has one value but 3 children.

Procedural

1. Draw the 2-3 tree that results from inserting 1, 2, 3, 4, 5, 6, 7 in order.

2. Problem 1 of the Spring 2018 Midterm 2

Problem 1

Check your answers using this interactive visualizer.

Problem 2

Solutions and walkthrough are linked here and on the course website.