Read the sections in Chapter 16 in L&C on 2-3 trees and 2-4 trees (which
we called 2-3-4 trees) and answer the questions below:
Show the 2-3-4 tree you get from inserting the values below in
the order shown:
5 10 25 9 12 4 6 18 8 11 2 16 7 20
Show the red-black tree corresponding to your tree from (1). Use the
correspondence we discussed in class to construct your red-black tree
directly from the finished 2-3-4 tree.
Show the 2-3-4 tree corresponding to the red-black tree from HW 12
(that is, the answer to question 13.5). Again, construct the 2-3-4 tree
directly from the finished red-black tree using the correspondence we
discussed in class.
In general a 2-3-4 tree will have a smaller height than the
corresponding red-black tree. Does this mean that the 2-3-4 tree is
more efficient to search in? Explain.