Data Structures, Algorithms, & Applications in C++
Chapter 15, Exercise 57
The first two insertions yield the 2-3 trees shown below.
[20] [20, 40]
The next insert requires us to split the root. We get the following tree.
[30]
/ \
[20] [40]
Inserting 10 results in the tree
[30]
/ \
[10, 20] [40]
When 25 is inserted, a node splits and we
get the following tree.
[20, 30]
/ | \
[10] [25] [40]
The tree following the insertion of 28 is
[20, 30]
/ | \
[10] [25, 28] [40]
The insertion of 27 results in two node splits.
The resulting tree is
[27]
/ \
/ \
[20] [30]
/ \ / \
[10] [25] [28] [40]
When 32 is inserted, we get the following tree.
[27]
/ \
/ \
[20] [30]
/ \ / \
[10] [25] [28] [32, 40]
When 36 is inserted a node splits,
and we get the following tree.
[27]
/ \
/ \
[20] [30, 36]
/ \ / | \
[10] [25] [28] [32] [40]
When 34 is inserted,
we get the following tree.
[27]
/ \
/ \
[20] [30, 36]
/ \ / | \
[10] [25] [28] [32, 34] [40]
Two nodes split when 35 is inserted.
The resulting tree is shown below.
[27, 34]
/ | \
/ | \
/ | \
[20] [30] [36]
/ \ / \ / \
[10] [25] [28] [32] [35] [40]
The insertion of 8 gives the following tree.
[27, 34]
/ | \
/ | \
/ | \
[20] [30] [36]
/ \ / \ / \
[8, 10] [25] [28] [32] [35] [40]
When 6 is inserted a node splits
and we get the following tree.
[27, 34]
/ | \
/ | \
/ | \
[8, 20] [30] [36]
/ | \ / \ / \
[6] [10] [25] [28] [32] [35] [40]
When 2 is inserted
we get the following tree.
[27, 34]
/ | \
/ | \
/ | \
[8, 20] [30] [36]
/ | \ / \ / \
[2, 6] [10] [25] [28] [32] [35] [40]
When 3 is inserted three nodes split and
we get the following tree.
[27]
/ \
/ \
/ \
/ \
[8] [34]
/ \ / \
[3] [20] [30] [36]
/ \ / \ / \ / \
[2] [6] [10] [25] [28] [32] [35] [40]